braindancer: (Default)
[personal profile] braindancer
Итак, первое решение задачи о стаканах на столе на 5 ходов, найденное [livejournal.com profile] ukrfan (оно не единственное, в комментах к задаче есть другие):

1) Трогаем 2 стакана по диагонали. Если они одинаковые - переворачиваем оба и переходим к шагу 3, если разные - приводим к одинаковому состоянию (скажем, вниз).

2) Трогаем стаканы на одной из сторон. Один из них точно будет вниз, т.к. мы его трогали в первом шагу; второй, если он не вниз - переворачиваем вниз.

3) Теперь у нас гарантированно ситуация НН/НВ (3 стакана вниз, 1 вверх), иначе свет бы включился на одном из первых двух шагов.

Трогаем 2 стакана по диагонали. Если стаканы разные - значит, нам повезло и попался последний "вверх"; переворачиваем его, задача решена. Если оба вниз - переворачиваем один вверх.

4) Теперь у нас гарантированно ситуация ВВ/НН (по двум сторонам одинаковые стаканы).

Трогаем стаканы на одной из сторон. Если попались одинаковые - переворачиваем оба, задача решена. Если попались разные - переворачиваем оба.

5) Теперь у нас гарантированно ситуация ВН/НВ (стаканы накрест).

Трогаем два диагональных стакана, они гарантированно одинаковые, переворачиваем оба. Задача решена.

Поздравляю правильно решивших:

[livejournal.com profile] ukrfan
[livejournal.com profile] notknowthetruth
[livejournal.com profile] poruchik
[livejournal.com profile] leon5555
[livejournal.com profile] chillaxedcfa
[livejournal.com profile] mediaplayer
[livejournal.com profile] dysto

Но это ещё не всё. Если мозги не устали, предлагаю подумать вот над чем: предположим, что вы в боксёрских перчатках, так что вы не можете определить состояние стаканов, которые вы переворачиваете. Грубо говоря, операция "пощупать" недоступна. Возможно ли решить задачу за фиксированное число ходов?

Date: 2011-04-21 09:45 pm (UTC)
From: [identity profile] dysto.livejournal.com
задачи как таковой нет, наши действия детерминированы, чередуем диагональ и сторону и переворачиваем
вопрос образуется ли при этом цикл с непременным прохождением одного из нужных состояний

Date: 2011-04-21 10:30 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Не совсем так :) Я, пожалуй, некорректно перевёл условие. Вы не обязаны чередовать, и не обязаны выбрать/перевернуть ДВА стакана.

Date: 2011-04-21 11:46 pm (UTC)
From: [identity profile] dysto.livejournal.com
тогда да, решается
на входе возможны три варианта:
1) стаканы на диагоналях стоят одинаково, на сторонах соответственно по-разному
2) НН/ВВ
3) три стакана в одной позиции, четвертый - в другой
1-й шаг: переворачиваем два стакана на диагонали, исключаем вариант 1), варианты 2) и 3) остаются вариантами 2) и 3) соответственно
2-й шаг: переворачиваем два стакана на стороне и если лампа не зажглась то либо у нас вариант 2) превратился в вариант 1), либо вариант 3) остался собой. Переворачиваем два стакана по диагонали, остается только вариант 3)
3-шаг: переворачиваем один стакан, вариант 3) превратился либо в вариант 1) либо в вариант 2); переворачиваем два стакана на диагонали, если не помогло то два стакана на стороне и потом если надо то еще раз два стакана по диагонали
Прикольно.

Profile

braindancer: (Default)
braindancer

May 2011

S M T W T F S
1234 567
891011121314
15161718192021
22232425262728
293031    

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 27th, 2017 07:14 pm
Powered by Dreamwidth Studios