Читать «Золотой билет» онлайн - страница 26

Рис. 3.5. Нетрадиционные потенциальные пары

В поисках клики

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

На деле выяснилось, что труд здесь требуется совершенно непосильный. Количество различных групп размера 50 оказалось непомерно огромным и выражалось числом из 151 цифры; не было и речи о том, чтобы проверить хотя бы сотую долю вариантов. Круг поиска пытались сузить всеми возможными способами – в частности, отсекли тех жителей, у которых было меньше 49 друзей, поскольку они-то уж точно не могли входить в искомую клику. Однако, несмотря на свою высокую квалификацию, исследователи не набрали и 25 друзей и при этом не смогли представить убедительное доказательство того, что клики размера 50 в Королевстве не существует.

Работа встала. Исследователи опустили руки. Внезапно одного из аспирантов осенило: «Слушайте, у нас же есть „Альфа“!» «Альфой» называлось известное, но при этом полусекретное сообщество, все члены которого, по слухам, дружили между собой. Пятьдесят «альфовцев» удалось найти довольно быстро: ведь, в конце концов, секретным сообщество было лишь наполовину. Оставалось только перебрать 1225 пар, чтобы проверить дружеские связи. К изумлению исследователей (но не самих «альфовцев», разумеется), все пятьдесят действительно оказались друзьями. Клика нашлась.

Передай скипетр

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

Дети в Королевстве любят играть в игру под названием «Передай скипетр», в которой участники по очереди передают друг другу небольшую палку. Передачей считается тот момент, когда палку держат двое – передающий и принимающий.

Правила игры:

1. Палку можно передавать только друзьям.

2. Между любыми двумя друзьями палка должна переместиться ровно один раз.

Пусть в игре участвуют пятеро детей. Одно из возможных решений таково: начинают с Барбары, она передает палку Эрику, Эрик – Алексу, Алекс – Кэти, Кэти – снова Эрику, а Эрик – Дэвиду.