Previous Entry Share Next Entry
(no subject)
art surrealism искусство сюрреализм сюр
braindancer
В пику одному моему хорошему френду (не будем показывать пальцем, leon5555) вывешиваю задачку для проверки работоспособности мозгов :) Драконовских условий типа угнать решить за 60 секунд не ставлю, т.к. сам провозился с ней постыдно долго.

Перед вами квадратный стол. Над столом висит лампа. В каждом углу стола углубление (лунка), в ней стоит стакан. Стакан может стоять либо дном вверх, либо вниз. Изначальное их состояние неизвестно. В комнате темно, ни хрена не видно, все действия производятся наощупь.

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

Задача - включить лампу за минимальное число шагов.

P.S. Ответы не скриню, так что если хотите подумать - не лезьте сразу читать комменты :)

  • 1
(Deleted comment)
Направление правильное, да :)

Не вполне понятно, нужно коснуться двух стаканов одновременно, или можно сначала одного, потом подумать, а потом другого? Это очень сильно влияет на оптимизацию процесса :)

Одновременно :)

Вообще не понял где уловка, но все же.
Шаг 1. Пробуем 2 стакана рядом:
1) Если одинаковое состояние - переворачиваем двоих (получаем состояние А двух стаканов после переворачивания)
2) Если разные состояния - один любой переворачиваем (получаем состояние А двух стаканов после переворачивания)
Шаг 2-3-...-N. Пробуем 2 стакана "по диагонали":
1) Стакан в состоянии не-А, переворачиваем в А.

Ну так на шагах 2,3,n вам может попасться одна и та же диагональ. Так и будете ее вечно щупать :)

(Deleted comment)
(Screened comment)
(Screened comment)
(Screened comment)
(Screened comment)
(Screened comment)
(Screened comment)
IMO, задача не имеет решения. Приведя за два хода стаканы в состояние ПППН (где П - "правильный" стакан, а Н - "неправильный"), на следующем ходу, какой бы ход ни выбрали - диагональ или сторону - имеем вероятность получения ПП, а это означает, что мы вперед не продвинулись. Причем вероятность потрогать на следующем ходу "нетронутый" стакан одинакова, вне зависимости от выбора "сторона или диагональ", и составляет 50%.

Имеет, причем за фиксированное число ходов :)

Первый ход: Я бы взяла стаканы по диагонали, если они разные, то перевернула бы один чтобы оба были дном вниз. Если лампа не загорается, то вторая диагональ либо не симметрична, либо находится дном вверх.
Второй ход: снова смотрим ту же диагональ. Если стаканы одинаковые и дном вниз, то ход пропускаем и тогда будет 3 ход. Если разные, то переворачиаем один и тогда все 4 дном вниз - лампа загорается. Если одинаковые дном вверх - то переворачиваем оба, лампа загорается.
Третий ход - смтрим ту же диагональ, если 2 одинаковые и дном вниз, пропускаем... И так пока не найдем разные.

Да, но вам же может вечно попадаться одна и та же диагональ.

(Screened comment)
Гениально, ты похоже даже на ход короче решил, чем я. Ща заскриню. :)

Допустим у стола четыре стакана: А, В, С и Д
Первая итерация: проверяем стакан справа и слева. Если положение у стаканов разное, приводим к одному, без разницы какому. Если одинаковое - переворачиваем оба (вдруг другие два тоже перевернуты). Допустим, мы выбрали стаканы дном вверх.
Итого: минимум два стакана у нас в правильном положении, если изначальное положение стаканов было разным. И три стакана в правильном положении, если изначально два выбранных стакана были дном вниз.

Вторая итерация: проверяем стакан справа и по диагонали. Если один из них дном вниз, а мы знаем что у нас 3 стакана в правильном положении, значит этот стакан "новый". Переворачиваем, success.
Если оба стакана дном вверх, значит и в этом случае у нас совершенно точно три стакана в правильном и надо "поймать" четвертый.

А вот дальше я никак не мог уйти от "вероятности"... при 2/2 есть вариант попасть на два разных стакана. При 3/1 есть вариант попасть на два одинаковых стакана. Интересно, какой правильный ответ)

Ну мыслишь ты в правильном направлении :) Правильный ответ завтра, народ еще думает :)

(Deleted comment)
Ну вот, пришёл поручик и всё опошлил :)))

твой моск силен аднако, так чо-то я сходу в аэропорту туплю, не вывешивай ответ следующие 36 часов - я как долечу, крепко падумаю :)))

Ну думай :) А куда это ты летишь 36 часов?? Это ж два раза вокруг Земли облететь можно

(Deleted comment)
Ну вот фишка именно в том, чтобы гарантированно включить за некоторое определенное число ходов :) Так что твой вариант решением не считается, увы.

(Deleted comment)
Прикольная задачка.
Пользуясь предложенным выше обозначением, назовём стаканы П и Н.

Первая итерация - берём два диагональных стакана и ставим их ПП.
Если лампа не включилась, крутим стол.

Вторая итерация - осматриваем два стакана по диагонали.
Возможные варианты: ПП, ПН, НН.
Если НН или ПН, то осталось лишь перевернуть все Н в положение П.
Если снова попался ПП, то переворачиваем. Лампа либо загорится (НННН), либо нет (НННП).

Третья итерация - осматриваем два стакана по диагонали.
Варианты: ПН или НН. Если нащупали П, то это выигрыш - переворачиваем его.
Если не нащупали, то переворачиваем один из двух стаканов. Получаем ННПП.

Четвертая итерация - осматриваем два стакана на одной стороне стола и переворачиваем оба. Варианты: НН, ПП, ПН. В первых двух случаях мы сразу выигрываем. В последнем случае получаем ПНПН.

Пятая итерация - переварачиваем любую дигональ.
Вин! )

Верно :) Интересно, что решений на 5 ходов, оказывается, несколько, я решал немного по-другому.

(Screened comment)

Re: Красивая задачка на комбинаторику

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

ahsim решил бы задачку за пару-тройку минут - у него в МГУ, по моему, профильная кафедра была по Теории вероятности и Комбинаторике

Попробую

Обозначим все стаканы так:
неизвестные - а
дном вверх - х
стоящие как положено - о


Изначальное положение:
аа
аа

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

ха
ах

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

хо
хх

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

оо
хх

Стол крутится. Четвертое действие. Берем линию и меняем стаканы местами - нормально стоящий переворачиваем, перевернутый ставим нормально. Опять же, попадись нам одноименные стаканы, все бы уже закончилось.

ох
хо

Стол крутится. Пятое действие. Берем диагональ и меняем расположение стаканов.

Итого - пять действий.

Блин, как же просто получилось-то!

(Screened comment)
5 ходов тоесть))

1. Взяли на одной стороне, если в одинаковом состоянии, то поменяли у обоих, если в разном, то поставили в одинаковое. Допустим, теперь они стоят дном вниз.
2. Взяли по диагонали, если оба дном вниз, оставили, если один дном вверх, то его перевернули. Теперь три стакана стоят дном вниз, один - вверх.
3. Взяли на одной стороне, если один дном вверх то его переворачиваем и конец, если оба дном вниз, переворачиваем правый дном вверх.
4. Взяли по диагонали, если стоят одинаково, то переворачиваем и конец, если по-разному то ничего не делаем.
5. Взяли на одной стороне, если стоят одинаково то переворачиваем и конец, если по разному то оба переворачиваем.
6. Берем по диагонали, они стоят одинаково, переворачиваем и конец.

Ответ верный, хотя можно на ход короче :)

Хорошая задачка. Жаль, что я прочитала сначала ответ, а потому уже задание. Так что почти не считается.

  • 1
?

Log in