Неразрешимые головоломки и коллекционирование

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

Первой из таких головоломок по праву будет игра в пятнашки от Сэма Лойда. Требовалось всего лишь переставить местами кубики с номерами "15" и "14". Приз в 1000 долларов, предлагавшийся за первое правильное решение, никогда никому не был присужден, хотя тысячи людей утверждали, будто они решили задачу.



А вот доказательство того, что задача про дома и колодцы неразрешима, нашлось. (Кстати, эта же задача встречалась и под видом трубочек с коктейлями). Суть головоломки в том, что нужно проложить три тропинки от каждого дома к каждому колодцу. Тропинки не могут пересекаться и, естественно, не проходят через дома и колодцы. Здесь подробно объясняется почему этого сделать нельзя. На практике подобного рода задачи могут встретиться, например, при разработке печатных плат. Представим, что нужно на однослойной печатной плате соединить друг с другом шесть микросхем. Долго можно мучиться, если не знать теорию графов.

Пишите в комментариях об известных вам неразрешимых задачах. А может быть вы знаете как они решаются?

Понравилось? Опубликуй у себя: