Леонард Эйлер атындағы олимпиада,2009-2010 оқу жылы, қорытынды кезеңнің 1-ші туры

Швамбаранияда кейбір қалалар екіжақты қонбайтың авиарейстермен байланысқан. Рейстер үш авиакомпания арасында бөлінген, мұнымен қатар, егер қандай да бір авиакомпания А және Б қалаларына қызмет көрсетсе, онда басқа компанияның ұшақтары бұл екі қаланың арасында ұшпайды. Әр қаладан үш компанияның да ұшақтары ұшатыны белгілі. Бір қаладан ұшып шығып, жол-жөнекей барлық үш компанияның рейстерін пайдаланып, және ешқандай екі қаланың ортасында екі рет болмай, қайтадан сол қалаға қайтып келуге болатының дәлелдеңіз. ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Вылетим из любого города А первой компанией, попадем в город Б, из него вылетим второй компанией, далее третьей, затем снова первой, второй, третьей и т. д. Рассмотрим самый первый момент, когда на этом пути встретился город В, где мы уже были. Тогда кусок нашего пути от первого посещения города В до второго и будет искомым. В самом деле, если мы в первый раз вылетели из города В в город Г, то из Г сразу вернуться в В мы не могли. Поэтому между двумя посещениями города В мы совершили хотя бы три перелёта и, значит, воспользовались по пути рейсами всех трёх компаний.