?

Log in

No account? Create an account
Задача Эйнштейна - Заметки на полях — ЖЖ [entries|archive|friends|userinfo]
Инга Кесс

[ website | Растрепанный Блокнот ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Задача Эйнштейна [янв. 28, 2007|05:55 pm]
Инга Кесс
[Настроение |чудесное :)]
[Музыка |Оазис Ю - Звёзды]

Сейчас решаю "Задачу Эйнштейна". Логическая задачка :).

Первый вариант условия:

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

1. Норвежец живет в первом доме.
2. Англичанин живет в красном доме.
3. Зеленый дом находится левее белого.
4. Датчанин пьет чай.
5. Тот, кто курит Rothmans, живет рядом с тем, кто выращивает кошек.
6. Тот, кто живет в желтом доме, курит Dunhill.
7. Немец курит Marlboro.
8. Тот, кто живет в центре, пьет молоко.
9. Сосед того, кто курит Rothmans, пьет воду.
10. Тот, кто курит Pall Mall, выращивает птиц.
11. Швед выращивает собак.
12. Норвежец живет рядом с синим домом.
13. Тот, кто выращивает лошадей, живет в синем доме.
14. Тот, кто курит Philip Morris, пьет пиво.
15. В зеленом доме пьют кофе.

Ответить нужно на вопрос: "Кто разводит рыбок?".

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

Второй вариант задачи очень похож (если не считать некоторой разницы в названиях и порядка условий). Но вот одно условие отличается существенно, про лошадь, поэтому этот вариант задачи несколько более сложный. И я его еще не дорешала :). Точнее, дорешала до половины, но поскольку дело было ночью, а завтра наутро на работу, я эту задачку бросила. Последние несколько дней изредка бросала взгляд на нее, недорешанную; было приятно знать, что у меня впереди еще вот такое. Но не продолжала. А вот сейчас решила дорешать. Пока что кроме основного (очевидного) решения нашла еще четыре (то есть пока решений всего пять), но до конца пока не дорешала. Я же хочу найти все решения. Или понять, что других решений точно нет :).

Вот он, второй вариант:

1. Англичанин живет в красном доме
2. Швед держит собаку
3. Датчанин пьет чай
4. Зеленый дом стоит слева от белого
5. Жилец зеленого дома пьет кофе
6. Человек, который курит Pall Mall, держит птицу
7. Жилец из среднего дома пьет молоко
8. Жилец из желтого дома курит Dunhill
9. Норвежец живет в первом доме
10. Курильщик Marlboro живет около того, кто держит кошку
11. Человек, который содержит лошадь, живет около того, кто курит Dunhill
12. Курильщик сигарет Winfield пьет пиво
13. Норвежец живет около голубого дома
14. Немец курит Rothmans
15. Курильщик Marlboro живет по соседству с человеком, который пьет воду

Вопрос тот же: "У кого живет рыба?"


Вот как я ее решаю (можно было сделать разные таблицы, но мне цветами и графическими значками удобнее обозначать кое-какую информацию, если я решаю "вручную").



Ярко-розовым (внутри таблицы) закрашены клетки, общие для варианта "зеленый дом слева от белого - значит, ближайший сосед слева" и варианта "зеленый дом стоит левее белого, но не обязательно непосредственно рядом". Зеленым цветом - клетки, которые относятся к варианту "зеленый дом слева от белого, но не обязательно непосредственно рядом". Незакрашенные клетки с карандашными метками - "предположим, что...". Получается дерево вариантов. На начальных этапах ячейку, про содержимое которой делается предположение, я обводила кружком (первый уровень), квадратом (второй уровень), треугольником (третий уровень). Знаки "+" и "-" я на первом уровне ставила в целую ячейку, на втором - в половинку, на третьем - в четвертую часть. Сначала было много неподходящих вариантов, когда предположение приводило к противоречию с какими-то начальными условиями. Их я, естественно, отбрасывала. Потом таких вариантов стало меньше, и мне пришлось добавить еще пару уровней - их я уже обозначала специальными значками. Значки - для того, чтобы знать, содержимое каких ячеек после рассмотрения варианта нужно очистить, а содержимое каких - оставить (т.к. этот уровень мы еще не целиком рассмотрели).

Естественно, если считать, что "зеленый дом стоит слева от белого" означает "слева и вплотную к нему", никаких таких заморочек не нужно :). Достаточно просто обычной таблички. И никаких "предположим, что...". Пока я решала задачу в первом варианте, у меня была обычная табличка с плюсиками-минусиками, ну и еще цветовые обозначения в столбце "значение". Они не обязательны, просто так удобнее прослеживать связи между строчками таблицы, чем по текстовому условию. Я сначала хотела эти связи обозначать стрелками, но цвета удобнее: стрелок слишком много, они бы визуально перепутались и все равно было бы неудобно отслеживать :).

Я вот хочу, когда наконец дорешаю эту задачу, оформить ее решение (разумеется, не в этом извращенном варианте, а в том, в котором всего четыре решения) - визуализировать сам процесс, в динамике, и подсунуть нашим студентам :). Предварительно подсунув саму задачу и время на решение.
Чем не задачка школьного уровня? ;)
Если курильщики смущают (применительно к гипотетическим школьникам), есть вариант этой задачи, где не курят, а то ли каким-то спортом занимаются, то ли что-то в этом роде :). Где-то я такой вариант видела...

А хотя, впрочем, и тот вариант, который я рассматриваю сейчас (с "предположим, что..." и "получили противоречие"), тоже было бы полезно показать... уже из других соображений :).

Никто не хочет задачку порешать? ;)
Мне просто любопытно, кто сколько решений найдёт.
Я ведь могла по невнимательности и пропустить что-то :). Я ж человек жутко рассеянный, поэтому в конце концов на полях нарисовала дерево, которое раньше держала в голове. Оно, правда, еще не дорисовано. Задача-то еще не дорешана до конца. Может, там и другие решения есть... :)
Мне просто из принципа интересно "вручную" решить.

А когда найду все решения, выкладывать их? ;)
(отдельным постом)
СсылкаОтветить

Comments:
From: bntr
2007-02-06 10:52 am
попробовал изобразить процесс решения =)
http://bntr.livejournal.com/28962.html
(Ответить) (Thread)