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 11:03 pm (UTC)
From: [identity profile] ukrfan.livejournal.com
ну типа столблю, как золотоискатель:)
Есть два типа, принципиально отличающихся: где по два стакана стоят П и Н, и где 3-1.
Поэтому:
1. переворачиваем диагональ. Если мы имели 2-2 в варианте ПНПН, задача решена. Если имели ППНН, то ничего не изменилось.
2. переворачиваем сторону. Если было ППНН, то либо мы решили задачу, либо получили ПНПН. Поэтому
3. Переворачиваем диагональ.
4. Если задача на прошлом ходу не решилась, значит, изначально имели 3-1. Меняем четность, переворачивая любой стакан.
5-7. Повторяем ходы 1-3, теперь (поскольку 2-2 на входе), задача решится на одном из них.

Date: 2011-04-21 11:31 pm (UTC)
From: [identity profile] konaire.livejournal.com
Прикольно! Не знаю мат. аппарата, но идея такая.

Изначально имеем только три возможных варианта:
A:
1 1
0 0
B:
1 0
0 1
C:
1 1
1 0

Что такое 1 и 0 - неважно. У нас есть два преобразования: "+" - это переворот обоих стаканов по любой стороне, "-" - переворот обоих стаканов по любой диагонали. При этом всегда:
A+ = B (или выигрыш)
B+ = A
C+ = C
A- = A
B- = выигрыш (всегда)
C- = C

1: поворот диагональных стаканов ("-"). Если свет на зажегся, то мы точно или в ситуации A или в ситуации C

2: поворот горизонтальных стаканов ("+"). Теперь мы точно или в ситуации B или в ситуации C.

3: поворот диагональных стаканов ("-"). Если свет не зажегся, то мы точно в ситуации C.

4: поворот любого одного стакана. Если свет не зажегся, то мы точно в ситуации A или B.

Повторяем шаги 1-3 и гарантированно выигрываем. Кажется, если нигде не наглючил, получается выигрыш за 7 ходов :)

То есть, последовательность такая: -, +, -, 1 любой стакан, -, +, -.
Edited Date: 2011-04-21 11:40 pm (UTC)

Date: 2011-04-22 03:26 am (UTC)
From: [identity profile] 3eta.livejournal.com
красиво, действительно! :)
зря я бросила

Date: 2011-04-22 03:55 am (UTC)
From: [identity profile] leon5555.livejournal.com
Если лампочка не горит, то у нас три возможных состояния:

UUUD
UUDD
UDUD


Шаг 1: Переворачиваем две чашки по диагонали, таким образом, если лампочка не загорелась мы исключаем состояние UDUD. После этого вращаем

Шаг 2: Переворачиваем две чашки стоящие рядом, если лампочка не загорелась, мы исключаем состояние UUDD, но переводим кейс в русло либо в состояния UUUD, либо UDUD. После этого вращаем

Шаг 3: Переворачиваем две чашки по диагонали, если лампочка не загорелась, то вращаем дальше. Если у нас состояние UDUD лампочка загорается. Второе возможное состояние UUUD, то есть лампочка остается потухшей. В общем если не горит, опять вращаем и дальше дело техники (просто надоело детально все расписывать)

Шаг 4: Переворачиваем одну чашку, если лампочка не загорелась, то вращаем дальше

Шаг 5: Переворачиваем две чашки по диагонали, если лампочка не загорелась, то вращаем дальше

Шаг 6: Переворачиваем две чашки стоящие рядом, если лампочка не загорелась, то вращаем дальше

Шаг 7: Переворачиваем две чашки по диагонали – лампочка должна загорецца

Date: 2011-04-22 09:29 am (UTC)
From: [identity profile] notknowthetruth.livejournal.com
Боксерские - Возможно.

В моем решении Атакуем Первую и Третью - щупать не надо.
Атакуем Вторую меняем на:
1. Рядом, переворачиваем один любой стакан, или win или получаем одну из двух комбинаций:
11
00
или
01
10
2. Применяем в ним поочередно стратегии Атакуем Первую и Атакуем Третью (где щупать не нужно) и win.

Еще хотелось бы каких то задач про бизнес, аля product mix и сложнее.

полное описание решения

Date: 2011-04-22 11:33 am (UTC)
From: [identity profile] leon5555.livejournal.com
У меня получается в 7 ходов:

Если лампочка не горит, то у нас три возможных состояния:

UUUD
UUDD
UDUD


Шаг 1: Переворачиваем две чашки по диагонали, таким образом, если лампочка не загорелась мы исключаем состояние UDUD. После этого вращаем

Шаг 2: Переворачиваем две чашки стоящие рядом, если лампочка не загорелась, мы исключаем состояние UUDD, но переводим кейс в русло либо в состояния UUUD, либо UDUD. После этого вращаем

Шаг 3: Переворачиваем две чашки по диагонали, если лампочка не загорелась, то вращаем дальше. Если у нас состояние UDUD лампочка загорается. Второе возможное состояние UUUD, то есть лампочка остается потухшей. В общем если не горит, опять вращаем и дальше дело техники (просто надоело детально все расписывать)

Шаг 4: Переворачиваем одну чашку, если лампочка не загорелась, то значит у нас один из двух вариантов UUDD или UDUD. Вращаем дальше


Шаг 5: Переворачиваем две чашки по диагонали, если лампочка не загорелась, то у нас остается комбинация UUDD вращаем дальше

Шаг 6: Переворачиваем две чашки стоящие рядом, если лампочка не загорелась, то значит у нас комбинация UDUD и мы вращаем дальше

Шаг 7: Переворачиваем две чашки по диагонали – лампочка должна загорецца

Date: 2011-04-23 07:06 pm (UTC)
From: [identity profile] chillaxedcfa.livejournal.com
Попробую.

Рассмотрим три возможные состояния системы: три-на-одного, пополам-линия, пополам-диагональ.

хх хо хх
хо ох оо

Любые другие расположения - это вариации на эти темы.

Первое действие. Исключим вторую систему из рассмотрения. Возмем диагональ и перевернем оба стакана.

ох оо ох
хх оо ох

Второе действие. Начнем работать с первой системой. Берем диагональ и переворачиваем один из стаканов. Рассматриваем неблагоприятный исход, мы не перевернули нужный стакан.

первая система:
ох оо
хо хх

вторая система (не важно, перевернуты стаканы или стоят нормально):
ох
хх

Третье действие - перевернем диагональ. Это уберет один из вариантов первой системы.
хх хо
хх хо

Вторая система:
хх
хо

Четвертое действие - перевернем линию. Опять же, события нам не благоприятствуют:
Первая система:
ох
хо

Вторая система:
оо хх
хо ох - два варианты, но они идентичны. Рассматривать дальше будем один из них.

Пятое действие - перевернем диагональ. Первая система исключена из рассмотрения.
Первая система:
хх
хх

Вторая система
хх
ох

Шестое действие - берем диагональ, переворачиваем один стакан. Система 2 разбивается этим действием на подсистемы.
Первая подсистема
хо ох
ох ох

Седьмое действие - берем диагональ, переворачиваем, исключаем первую подсистему

оо хх
оо оо

Восьмое действие - берем диагональ, меняем положения обоих стаканов
хо
ох

Девятое действие - берем диагональ, переворачиваем 2 стакана

оо
оо

Итого - девять действий.
Page generated Jun. 27th, 2017 07:08 pm
Powered by Dreamwidth Studios