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

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

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

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