Контактное число шаров и сферические коды

Сей­час, читая этот текст или ска­чи­вая фильм, вы, возможно, исполь­зо­вали реше­ние задачи о кон­такт­ном числе шаров в восьмимер­ном про­стран­стве. Удив­лены?

В конце фильма рас­ска­зы­ва­ется, какое при­ме­не­ние нахо­дит эта извест­ная кра­си­вая матема­ти­че­ская задача в тех­нике.

Как много оди­на­ко­вых шаров можно рас­по­ложить вокруг одного фик­си­ро­ван­ного?

Рас­смот­рим плос­кий слу­чай. В нали­чии име­ется  много оди­на­ко­вых монет и такая же монетка, лежащая рядом. Как много оди­на­ко­вых монет  можно положить на стол вокруг одной такой же, так чтобы они все каса­лись цен­траль­ной?

Шесть монет могут быть рас­по­ложены с  цен­трами в верши­нах пра­виль­ного шести­уголь­ника.

Но может быть можно рас­по­ложить большее число монет?

Одна монета  «занимает» угол в 60°. Поде­лим пол­ный угол в 360° на тот угол, меньше кото­рого одна монета занимать не может, и полу­чим ровно шесть. Т.е. больше чем шесть монет уложить вокруг одной того же ради­уса нельзя.

Это можно было пока­зать и чуть по-другому. На окруж­но­сти цен­траль­ной монеты рас­смот­реть дугу, кото­рую занимает одна монета, касающа­яся цен­траль­ной. Поде­лить длину всей окруж­но­сти на длину рас­смот­рен­ной дуги и уви­деть, что места хва­тает ровно на шесть таких дуг.

Най­дено рас­по­ложе­ние шести монет и пока­зано, что больше шести монет не могут касаться одной того же размера. Именно так реша­ется большин­ство экс­тремаль­ных задач — задач на нахож­де­ние мак­симума или минимума. При­во­дится некая кон­струкция, а затем дока­зы­ва­ется, что она наи­лучшая с точки зре­ния усло­вий задачи.

В нашем при­выч­ном трёхмер­ном про­стран­стве задача ока­за­лась намного слож­нее.

Как много оди­на­ко­вых бильярд­ных шаров можно рас­по­ложить в  про­стран­стве вокруг одного фик­си­ро­ван­ного того же ради­уса?

Две­на­дцать шаров могут рас­по­лагаться  в верши­нах ико­саэдра. При таком рас­по­ложе­нии  шары даже не касаются друг друга. Рас­по­ложе­ние шаров настолько сво­бодно, что  их можно катать по внут­рен­нему шару.

Можно ли рас­по­ложить более 12 шаров? Этот вопрос был пред­ме­том  знаме­ни­той дис­кус­сии, состо­явшейся в 1694 году между шот­ланд­ским уче­ным Дэви­дом Грегори и Иса­а­ком Нью­то­ном. Именно Исаак Нью­тон, изу­чая вопросы аст­ро­номии, уста­но­вил, что 12 шаров могут рас­по­лагаться в верши­нах ико­саэдра. Дэвид Грегори обобщил оценку сверху на коли­че­ство монет, рас­по­лага­емых вокруг одной фик­си­ро­ван­ной. Он посчи­тал площадь сфе­ри­че­ской шапочки, занима­емой одним шаром, и поде­лил площадь сферы цен­траль­ного шара на полу­чен­ную площадь шапочки. Про­ве­дите рас­чет, и вы уди­ви­тесь, что ответ будет почти 15. Так как это число ока­за­лось меньше 15, то это дока­зы­вало, что 15 шаров нельзя рас­по­ложить вокруг одного фик­си­ро­ван­ного. Однако, что даже 13 шаров нельзя рас­по­ложить, Грегори не смог дога­даться.

Только через 200 лет появи­лось пер­вое дока­за­тельство того, что кон­такт­ное число шаров в трёхмер­ном про­стран­стве равно 12.

Задача о кон­такт­ном числе шаров решена ещё в 4-мер­ном, 8-мер­ном и 24-мер­ном про­стран­ствах. Кон­такт­ное число шаров равно соот­вет­ственно 24, 240 и 196560. Шары рас­по­лагаются в верши­нах минималь­ных век­то­ров шахмат­ной решётки, решётки Кор­ки­на—­Зо­ло­та­рёва и решётки Лича. Послед­нее про­движе­ние в этой задаче — реше­ние в четырёхмер­ном слу­чае — полу­чено рос­сийским матема­ти­ком Олегом Муси­ным.

Рас­смот­рен­ная кра­си­вая и, каза­лось бы, чисто матема­ти­че­ская задача о кон­такт­ном числе шаров явля­ется част­ным слу­чаем задачи о сфе­ри­че­ском коде и имеет много важ­ных при­ложе­ний в тех­нике при пере­даче информации на рас­сто­я­ния. В част­но­сти, код, исправ­ляющий ошибки, исполь­зующий реше­ние задачи о кон­такт­ном числе шаров в восьмимер­ном евкли­до­вом про­стран­стве, при­ме­ня­ется в модемах.

При пере­даче информации на рас­сто­я­ния, напри­мер с Земли на спут­ник, воз­ни­кают огра­ни­че­ния на мощ­ность пере­да­ва­емого сиг­нала. Матема­ти­че­ски эти огра­ни­че­ния озна­чают, что пере­да­ва­емые сиг­налы являются точ­ками сферы евкли­дова про­стран­ства неко­то­рой размер­но­сти.

Каж­дому шару из задачи о кон­такт­ном числе шаров  соот­вет­ствует сфе­ри­че­ская шапка на цен­траль­ном шаре и точка каса­ния. Эти точки назы­ваются алфа­ви­том. В кон­крет­ный момент времени задача состоит в пере­даче точек каса­ния из неко­то­рых шапок на другую сферу. Набор шапок, из кото­рых пере­даются сиг­налы, обра­зует так назы­ва­емое слово. Однако при пере­даче могут воз­ни­кать искаже­ния. Если шапки довольно большие, то при искаже­ниях точка  все­гда будет попа­дать внутрь той шапки, где была. Тогда пере­да­ва­емую точку можно одно­значно вос­ста­но­вить, поскольку шапки не пере­се­каются. Соот­вет­ственно можно  вос­ста­но­вить само слово — набор шапок, из кото­рых пере­да­ва­лись точки.

Если известно, что искаже­ния при пере­даче маленькие, то можно рас­смат­ри­вать шапки меньшего размера.

Жела­ние пере­да­вать как можно больше раз­ной информации, т.е. иметь как можно больше раз­ных слов, при­во­дит к задаче: рас­по­ложить  как можно больше сфе­ри­че­ских шапок задан­ного размера на сфере.

В пере­воде на язык шаров это при­во­дит к сле­дующей задаче. Как много оди­на­ко­вых шаров могут касаться шара другого ради­уса?

Нерешён­ные задачи

Несмотря на большое при­клад­ное зна­че­ние задачи о сфе­ри­че­ском коде, её реше­ние извест­нио лишь в небольшом числе част­ных слу­чаев как в трёхмер­ном про­стран­стве, так и в про­стран­ствах большей размер­но­сти. Точ­ное реше­ние в общем слу­чае или хоть в какой-нибудь бес­ко­неч­ной серии слу­чаев пока не най­дено.

Лите­ра­тура

Кон­вей Дж., Слоэн Н. Упа­ковки шаров, решетки и группы. — М. : Мир, 1990.

Leech J. The problem of the thirteen spheres // Mathematical Gazette. — 1956. — V. 40. — P. 22—23.

Левен­штейн В. И. О гра­ни­цах для упа­ко­вок в n-мер­ном евкли­до­вом про­стран­стве // Доклады Ака­демии наук СССР. — 1979. — Т. 245. — С. 1299—1303.

Odlyzko A. M., Sloane N. J. A. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions // Journal Comb. Theory. Ser. A. — 1979. — V. 26. — P. 210—214.

Мусин О. Р. Про­блема два­дцати пяти сфер // Успехи матема­ти­че­ских наук. — 2003. — Т. 58, № 4. — С. 153—154.

Другие этюды раздела «Наилучшее расположение точек»