задачка (математическое)

[avva]

1. Четыре монеты лежат на окружности согласно сторонам света. Монеты закрыты колпачками, так что вы не видите, как лежит каждая, орлом или решкой. На каждом ходу вы можете открыть любые две монеты, каждую из них либо перевернуть, либо оставить как есть, и закрыть обратно. После каждого хода круг вращают на неизвестное случайное количество четвертных оборотов. Если после вашего хода все четыре монеты лежат одинаково, вы победили.

Опишите выигрышную стратегию. За сколько ходов она гарантирует победу?

2. Та же задача, но теперь вам завязали глаза и вы не видите, как лежат монеты, которые вы решили открыть в каждом раунде. Кроме того, переворачивает их кто-то другой по вашим указаниям, так что наощупь определить тоже нельзя. Существует ли выигрышная стратегия? Если да, то за сколько ходов она гарантирует победу?

Комментарии закрываю на какое-то время.

Update: Комментарии раскрыты, не заглядывайте, если хотите решать сами. Подробные решения описаны в новой записи. Спасибо всем :)

Comments

[mirdin.livejournal.com]

А ходы других игроков не видны?

[avva.livejournal.com]

Других игроков нет, есть только один игрок.

[vnarod.livejournal.com]

Когда я еще учился в школе, эта задачка была на олимпиаде для 5го или 6 классов, году так в 80м. Только там были четыре двухцветных стержня и лампочка загорелась если их повернуть одной стороной вверх. И после каждого переворота цилиндр вращался так, чтобы после остановки нельзя было в темноте сказать какие стержни перевернул раньше.

Решение там очень простое, ответ, кажется, 7 шагов.

[braindancer.livejournal.com]

1) http://braindancer.livejournal.com/60940.html

2) http://braindancer.livejournal.com/61552.html

:)

Интересное чтиво на тему (вы, наверно, уже и сами читали): http://www.ms.uky.edu/~jrge/Papers/BBP.pdf

[drexo.livejournal.com]

1. Две монеты рядом - на решку: получаем РР**
2. Два монеты напротив - на решку: РРРО или победа
3. Две монеты напротив, или победа или переворачиваем одного орла: Получаем или РОРО или РРОО
4. Две монеты напротив, если разные то меняем местами. Получаем РОРО
5. Переворачиваем любые противоположенные - победа

[(Anonymous)]

Формулировать надо креативнее!

«У входа в пещеру с сокровищами стоит бочка с 4 дырками по кругу в крышке. В каждой дырке можно нащупать селедку хвостом вверх или вниз. Али-Баба может просунуть руки в любые две дырки, определить положение селедок под ними и, если хочет, перевернуть одну или обе по своему усмотрению. Когда хвосты всех четырёх селедок окажутся направленными в одну сторону, дверь в пещеру откроется. Однако, после того, как Али-Баба вытаскивает руки, бочка некоторое время с дикой скоростью крутится, так что Али-Баба не может определить, куда именно он совал руки раньше. Как Али-Бабе открыть дверь не более чем за 10 засовываний?»

Задачка для шестого класса ФМШ, решение копипастить не буду. Вторая задачка, где положение селедок нельзя определить, немногим сложнее.

Предположим, что две селедки лежат хвостом вверх и две хвостом вниз. Одно из двух: либо две соседние селедки лежат хвостом вверх, либо две противоположные. Перевернем противоположные селедки. Если попали, хорошо. Если нет, то теперь у нас точно две соседние селедки лежат хвостом вверх. Перевернем две соседние селедки. Если попали, хорошо, если нет — две противоположные селедки лежат хвостом вверх. Перевернем противоположные селедки. Если дверь не открылась, значит, начальное предположение было неверным. То есть одна селедка лежит хвостом в одну сторону и три в другую. Перевернем одну селедку. Если дверь не открылась, то теперь исходное предположение верно и надо проделать все действия еще раз сначала.

[i-shmael.livejournal.com]

Первую решил, вроде.

1. Открываю Север - Юг, переворачиваю обе на Орла.
2. Открываю Север - Запад, по крайней мере одна из них уже О, переворачиваю вторую на О.
3. Если это еще не конец, у меня три О, одна Р. Открываю Север - Юг. Если среди открытых Р, переворачиваю на О -> конец. Если обе О, то одну из них переворачиваю на Р. Таким образом рядом два О, два Р.
4. Открываю Север - Запад, переворачиваю О на Р, а Р на О. Таким образом, у меня чередование ОРОР.
5. Открываю Север - Юг, переворачиваю обе монеты.

[(Anonymous)]

"открыть любые две монеты" - нельзя открыть одну, посмотреть, что там, и только после этого решать, какую открыть вторую?

[lagu.livejournal.com]

А можно сначала открыть один колпачок, а потом, в зависимости от содержимого, другой?

[lagu.livejournal.com]

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

[imfromjasenevo.livejournal.com]

что такое четвертные обороты?

[kapla55.livejournal.com]

Черт, и все-таки нужен еще один шаг для решения второй задачи:
1. Перевернуть диагональные.
2. Перевернуть рядом лежащие.
3. Перевернуть диагональные.
4. Перевернуть одну.
5. Перевернуть диагональные.
6. Перевернуть рядом лежащие.
7. Перевернуть диагональные.
Все.

1 - 6 ходов

[berzhitskaya.livejournal.com]

? ?
? ?

сторона
0 0
? ?

диагональ
0 0
0 ?

Дальше меняем любой 0 на 1, имеем 2 варианта:

0 1 или 0 0
1 0 1 1

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

0 0 0 0
0 0 1 1

открываем сторону:

0 1
1 0

и диагональ:
0 0
0 0

[alexeybobkov]

Как именно "открыть любые две монеты"? Я должен сразу указать, какие две надо открыть, или я могу сначала открыть одну, посмотреть, что там, и в зависимости от этого выбрать вторую?

[avva.livejournal.com]

Должен сразу указать.

[webface.livejournal.com]

Во втором варианте игрок вообще ничего не видит или же получает какую-то информацию о состоянии монет в процессе игры?

[avva.livejournal.com]

Вообще ничего не видит.

[melkore.livejournal.com]

стратегия вероятности (она же ламерская) - тупо продолжать менять, пока все не совпадут.
гарантирует стопроцентную победу при бесконечном количестве ходов.

[niobium0.livejournal.com]

1)

a) открыть две смежные, перевернуть обе орлами вверху
б) открыть две противолежащие
б-1) если одна решкой вверх
б-1-а) перевернуть обе орлами вверх
б-1-б) открыть противолежащие
б-1-б-1) если одна решкой вверх, переврнуть орлом
б-1-б-2) если обе орлами вверх
б-1-б-2-а) перевернуть одну решкой вверх
б-1-б-2-б) открыть две смежные
б-1-б-2-б-1) если обе решками вверх, перевернуть обе орлами вверх
б-1-б-2-б-2) если обе орлами вверх, перевернуть обе решками вверх
б-1-б-2-б-3) если одна решка, один орел
б-1-б-2-б-3-а) перевернуть обе
б-1-б-2-б-3-б) открыть противолежащие, перевернуть обе.
б-2) если обе орлами гото б-1-б-2

5.. короче не нашел, но подозреваю, что есть.

2) c - перевернуть одну, б - перевернуть смежные, а - перевернуть противолежащие

абасаба

7, короче нет.

2))) 7 шагов

[berzhitskaya.livejournal.com]

Исходно может быть три конфигурации:
А:
01
10

Б:
00
11

или В:
00
01

Переворачиваем любую диагональ
А - мы выиграли
Б переходит в Б, В -> В

Переворачиваем любую сторону, либо выигрываем, либо Б -> А, В -> В

Переворачиваем диагональ - либо было Б и мы выигрываем, либо там было В (-> В)

Переворачиваем одну любую монетку, либо выигрываем, либо В переходит в А или Б.

Повторяем первые три действия. Получается 7 шагов.

[rakshas.livejournal.com]

1.

1) Выбираем две противоположные, делаем их одинаковыми.

2) Выбираем две рядом, делаем их того же цвета, что и в шаге один.

Итого у нас есть три монеты одной стороны.

3) Выбираем противоположные, если они разные, то меняем одну до победы. Если одинаковые, то переворачиваем одну.

Получаем по две монеты каждой стороной, общий вид ООРР.

4) Выбираем соседние, переворачиваем, получаем ОРОР.

5) Выбираем противоположные, переворачиваем, победа.

Итого в худшем случае у нас 5 ходов, естественно может получиться и лучше если повезет на каком-то этапе.

2. Условия второй не понял.

Можно пояснить немного?

[gdt.livejournal.com]

в 1-й вроде получается 5 ходов максимум.

[poteshnaya.livejournal.com]

Да вроде одинаково, что 1, что 2. Пять шагов получается.

1. Противоположные. Делаем одинаковыми.

2. Противоположные. Если разные, то тривиально, делаем одинаковыми и может еще раз инвертируем противоположные.

Если одинаковые, то инвертируем.
Если не выиграли, значит у нас три одинаковых, а четвертый другой.

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

4. Соседние. Если одинаковые, то инверт и победа.
Если разные, меняем местами.
Получили ситуацию одинаковых противоположных.

5. Противоположные. инвертируем.
Победа.

[bukky-boogwin.livejournal.com]

А разрешено открыть вторую монету уже после того, как мы узнали положение первой? Или нужно выбрать две сразу и только потом открыть обе?

[avva.livejournal.com]

Нет, нужно выбрать две сразу.

[poteshnaya.livejournal.com]

В 3 пункте "если не выиграли" лишнее, не можем мы там)

[gdt.livejournal.com]

а во 2-й указания могут быть только безусловные (переверни монету на севере, а на востоке не трогай), или могут быть и условными (если разные, сделай одинаковыми)? в первом случае вообще нет никаких идей. интересно будет завтра посмотреть.

[avva.livejournal.com]

Только безусловные.

[(Anonymous)]

Следует помнить, что набор монет может иметь всего четыре вида: "решка, орёл, решка, орёл", "решка, решка, орёл, орёл", "решка, решка, решка, орёл", "орёл, орёл, орёл, решка".

Подробная инструкция для второй задачи:
1. Переворачиваем противоположные монеты. Если набор был "решка, орёл, решка, орёл", мы победили.
2. Переворачиваем смежные монеты.
3. Переворачиваем противоположные монеты. Если изначальный набор был "решка, решка, орёл, орёл", мы победили либо сейчас, либо в пункте 2.
4. Открываем противоположные монеты, переворачиваем одну из них, а вторую оставляем в прежнем положении. Таким образом, если мы сейчас не победили, полученный набор выглядит либо как "решка, орёл, решка, орёл", либо как "решка, решка, орёл, орёл".
5. Переворачиваем противоположные монеты.
6. Переворачиваем смежные монеты.
7. Переворачиваем противоположные монеты. Победа!

[volk007.livejournal.com]

А переворачивать можно любые или только открытые?