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