?

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:
[User Picture]From: ingakess
2007-01-29 05:36 am
Ну, может, это не лично Эйнштейн ее придумал, я не знаю :). Но она во многих местах фигурирует как задача Эйнштейна. И там якобы есть еще приписка, что 98% людей ее решить не могут. Люди решают и удивляются, в чем дело, ведь они-то решили :). В связи с этим в некоторых местах, где я эту задачу видела, многие высказывают соображения, что, возможно, у задачи на самом деле не единственное решение. То, что неединственность может быть связана с разным пониманием фразы "зеленый дом стоит слева от белого", я вроде бы быстро поняла, а вот какие еще решения могут быть - в первом варианте задачи решила быстро, а вот второй только вчера вечером дорешала :). Правда, я до этого несколько дней к ней даже не притрагивалась, занята была очень... но всё равно, второй вариант задачи сложнее :).
А "не рисуя" я не могу, у меня память не настолько хорошая, чтобы столько объектов удерживать :). Я и устным счетом-то слабо владею, по той же причине :). Если числа большие, просто забываю предыдущий результат.
(Ответить) (Parent) (Thread)
From: tolsty_ubludok
2007-01-29 06:22 am
Ну я про -зеленый слева от белого- вообще не подумал! т.е. второй вариант вообще не рассматривал :(
(Ответить) (Parent) (Thread)
[User Picture]From: ingakess
2007-01-29 06:30 am
Я не знаю, может быть, такое в оригинальном варианте условия (до перевода) и не предполагалось. Я видела где-то условие этой задачи на английском, но как-то не вчиталась... А русских вариантов задачи несколько. Может быть, эта неоднозначность первоначально и не была заложена, но сейчас-то она есть :).
(Ответить) (Parent) (Thread)
[User Picture]From: ary
2007-01-29 11:07 am
Как рах Эйнштейн говорил, что 98% людей не могут решить ее В УМЕ! А с бумашкой-то все просто.

И кстати про "слева от белого" мне казалось именно как просто левее, а не соседний дом. Тыщу раз уже везде встречала эту задачу, но так и не удосужилась тоже порешать.
(Ответить) (Parent) (Thread)
[User Picture]From: ingakess
2007-01-29 09:16 pm
А я в уме даже не пробовала, потому что про "в уме" в тех вариантах условия, которые я видела, вроде бы ничего сказано не было...
А интересно было бы попробовать.
Только если "слева от белого" именно левее, а не соседний дом, я бы точно устно не решила :). Вот если ту формулировку задания, когда единственное решение, - там можно было бы попробовать...
С бумажкой единственное решение - элементарно. А вот в том понимании формулировки, когда оно не единственное, там сложнее. Особенно во втором варианте задачи, где условие про лошадь выглядит так: "Человек, который содержит лошадь, живет около того, кто курит Dunhill". Там и с бумажкой не так уж быстро решается :). То есть вообще как решать - понятно, но в голове лично мне столько фактов не удержать. Я ж говорю, на последних этапах решения, где пошли "предположим, что...", я поняла, что вот-вот собьюсь, какую ветку я уже рассмотрела, а какую нет, и нарисовала дерево на полях листка :). То есть я ветки рассматривала в определенном порядке, естественно, но вариантов "порядка" может быть несколько, и я поняла, что вот-вот забуду, какой из них выбрала в данном случае :).
(Ответить) (Parent) (Thread)