<< Предыдущая

стр. 39
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

429. На рисунке видно, что корабли образуют 5 прямых по 4 корабля на каждой, а белые призрачныеT
T




корабли указывают позиции, с которых 4 из них были перемещены.T
T




430. На рисунке представлено симметричное решение, при котором 21 звезда образует 11 прямых по 5T
T




звезд на каждой прямой.T
T




431. Очевидно, что для двух и большего числа прилегающих стран необходимы по крайней мере двеT
T




краски (случай 1). Если три страны попарно прилегают друг к другу, то необходимы три краскиT (случай 2). Для
T T T T T T




четырех стран требуются три краски, если четвертая (TЖ) страна прилегаетT к двум другим, уже прилегающим
T T T




друг к другу (случай 3). (Поскольку возможен вариант,T когда, как в случае 4, краска 3 прилегает к двум не
T T T T T T T




прилегающим друг к другу странам, иT в силу этого можно обойтись двумя красками.) Четыре же краски
T




понадобятся и в случае,T когда четвертая страна прилегает к каждой из трех прилегающих друг к другу стран
T




(случайT 5).T
T T
Для пяти прилегающих стран потребуются 3 краски, если одна страна прилегает к двум прилегающимT друг
T T




к другу странам (случай 6). Четыре краски потребуются, если пятая страна прилегает к каждой изT трех T T T




прилегающих друг к другу стран (случай 7). Однако 5 красок потребовались бы в случае, если быT пятая страна T T T




прилегала к четырем прилегающим друг к другу странам. Если такая карта возможна, тоT теорема не верна.T T




Рассмотрим сначала четыре страны, прилегающие друг к другу. Мы произведем небольшоеT
T




преобразование, приняв, что любые две прилегающие друг к другу страны связаны между собойT мостом. Мост
T T




может иметь любую длину, а страны можно свести просто к точкам, не влияя наT условияH41.T В случаях 8 и 9 я PU UTHP
T T T T T T




изобразил четыре страны (точки), соединенные между собой мостами (линиями).T Относительное расположение T




этих точек совершенно несущественно, и выясняется, что в каждомT возможном случае к одной из стран (точек) T




нельзя подобраться снаружи.T

Это легко доказать. Если 3 точки связаны между собой прямыми, то эти точки должны либоT образовывать
T T




треугольник, либо лежать на одной прямой. Предположим сначала, что они образуютT треугольник ЖКЗT, как в T T T




случае 16T. Тогда четвертая страна (TГ) должна лежать либо внутри треугольника,T либо вне его. Если она лежит
T T T T T




внутри, то очевидно, что она окружена. Поместим ее снаружи и соединимT с Ж и З, как показано на рисунке; T T T T T




тогда Г нельзя соединить с К, не окружив при этом Ж или З. Пусть Г прилегает к Ж или К; тогда Г нельзя
T T T T T T T T T T T T T T T T T




соединить с З, не окружив либо Ж, либо К. Пусть Г прилегает к К и З; тогда Г нельзя соединить с Ж, не
T T T T T T T T T T T T T T T T T T




окружив либо Ж, либоT З. T T T T T




Рассмотрим теперь второй вариант, когда КЖЗ лежат на прямой (случай 17T). Если Г лежит внутри, тоT она
T T T T T T T T




окружена. Поместим Г снаружи и соединим, как показано, с К и З; тогда Г нельзя соединить с Ж, неT окружив
T T T T T T T T T T T




при этом либо К, либо З. Пусть Г прилегает к К и Ж; тогда Г нельзя соединить с З, не окруживT К или Ж. Пусть
T T T T T T T T T T T T T T T T T T




Г прилегает к Ж и З; тогда Г нельзя соединить с К, не окружив Ж илиT З.
T T T T T T T T T T T T T T T




Таким образом, мы разобрали все возможные случаи и нашли, что если три страны прилегают друг кT другу,
T T




то четвертая страна не может прилегать ко всем трем так, чтобы при этом ни одна из стран неT оказалась T




окруженной.T

Случай 10T — это случай 8 до преобразования, а случай 11T — то же самое, что и случай 9. МожноT заметить,
T T T T T T T T T T




что до К нельзя добраться снаружи. Следовательно, нельзя нарисовать четыре страны такимT образом, чтобы
T T T




пятая страна прилегала к каждой из них; поэтому пятая страна может иметь тот же цвет,T что и К. А если нельзя T T T




нарисовать пять прилегающих друг к другу стран, то это и подавно невозможноT сделать с большим числом T




стран.T

Теперь ясно, что при каждом очередном добавлении новой страны нее страны, нарисованные ранее,T
T




должны прилегать друг к другу, чтобы предотвратить повторное использование какой-нибудь краски. ПриT этом
T T




условии мы можем нарисовать страны, однако одна из них окажется окруженной. Далее, мы можемT нарисовать T




пятую страну прилегающей только к одной стране (как в случае 12T), к двум (как в случае 13T) или к трем T T T T T T




странам (как в случае 14T). В одном случае новой страной может быть Ж, Г или К, во втором —T Г или К и в
T T T T T T T T T T T T
третьем случае — только К. Возьмем последний случай 14 и «предпочтем», или повторим, К. Но при этом мы
T T T T T T T T




вынуждены окружить З. Рисуя шестую страну, самое лучшее, что мы можем сделатьT (пытаясь прийти в
T T T




противоречие с теоремой), это «предпочесть» З (как в случае 15T), а в результатеT оказывается окруженной К. И T T T T T T T




так далее до бесконечности. Мы вынуждены окружать какую-нибудь краскуT на каждом шаге и тем самым T




делать ее пригодной к употреблению на следующем шаге. Но если выT не можете построить карту, для которой T




потребовалось бы пять красок, то такой карты и неT существует. Следовательно, необходимое число красок T




никогда не превысит четырех, и теоремаT доказана.T T

<< Предыдущая

стр. 39
(из 51 стр.)

ОГЛАВЛЕНИЕ

Следующая >>