braindancer: (Default)
[personal profile] braindancer
В пику одному моему хорошему френду (не будем показывать пальцем, [livejournal.com profile] leon5555) вывешиваю задачку для проверки работоспособности мозгов :) Драконовских условий типа угнать решить за 60 секунд не ставлю, т.к. сам провозился с ней постыдно долго.

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

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

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

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

Date: 2011-04-19 07:19 pm (UTC)
From: [identity profile] gns-ua.livejournal.com
Если бы стаканы стояли в ряд, то задача бы решалась в два хода.

Поскольку стол вращается и мы не знаем какой стороной, инвариантом будет отношение с краю - в середине :) Мы лапаем два в центре, если они в разном положении - приводим их к одному. Запоминаем это положение. После вращения мы лапаем два крайних и приводим их в то состояние, в котором после первого шага оказались центральные.

В случае стаканов по углам квадрата... Сохраняется разница между диагональю и стороной, но стороны четыре а диагонали две.... Думаю... :)

Date: 2011-04-19 07:24 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Направление правильное, да :)

Date: 2011-04-19 08:32 pm (UTC)
From: [identity profile] gadyuka.livejournal.com
Не вполне понятно, нужно коснуться двух стаканов одновременно, или можно сначала одного, потом подумать, а потом другого? Это очень сильно влияет на оптимизацию процесса :)

Date: 2011-04-19 08:58 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Одновременно :)

Date: 2011-04-19 09:00 pm (UTC)
From: [identity profile] duh-predkov.livejournal.com
+1
1. сколько раз можно переворачивать стаканы до поворота стола?
2. только вместе или по очереди?
3. можно ли вынимать стаканы и оставлять у себя, во время поворотА?

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-19 09:01 pm (UTC) - Expand

Date: 2011-04-19 09:20 pm (UTC)
From: [identity profile] ukrfan.livejournal.com
Мне кажется. это никак не влияет.

Date: 2011-04-19 08:53 pm (UTC)
From: [identity profile] notknowthetruth.livejournal.com
Вообще не понял где уловка, но все же.
Шаг 1. Пробуем 2 стакана рядом:
1) Если одинаковое состояние - переворачиваем двоих (получаем состояние А двух стаканов после переворачивания)
2) Если разные состояния - один любой переворачиваем (получаем состояние А двух стаканов после переворачивания)
Шаг 2-3-...-N. Пробуем 2 стакана "по диагонали":
1) Стакан в состоянии не-А, переворачиваем в А.

Date: 2011-04-19 09:00 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Ну так на шагах 2,3,n вам может попасться одна и та же диагональ. Так и будете ее вечно щупать :)
(deleted comment)

(no subject)

From: [identity profile] ukrfan.livejournal.com - Date: 2011-04-19 09:24 pm (UTC) - Expand

(no subject)

From: [identity profile] notknowthetruth.livejournal.com - Date: 2011-04-19 09:27 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-19 09:58 pm (UTC) - Expand

Date: 2011-04-19 09:02 pm (UTC)
From: [identity profile] duh-predkov.livejournal.com
тоже подумал о таком варианте, но в теории кол-во шагов все равно может быть бесконечным

(no subject)

From: [identity profile] duh-predkov.livejournal.com - Date: 2011-04-19 09:03 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-19 09:59 pm (UTC) - Expand
(screened comment)
(screened comment)
(screened comment)
(screened comment)
(screened comment)
(screened comment)

(no subject)

From: [identity profile] notknowthetruth.livejournal.com - Date: 2011-04-20 03:26 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-20 03:56 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 09:32 pm (UTC) - Expand

Date: 2011-04-19 09:15 pm (UTC)
From: [identity profile] ukrfan.livejournal.com
IMO, задача не имеет решения. Приведя за два хода стаканы в состояние ПППН (где П - "правильный" стакан, а Н - "неправильный"), на следующем ходу, какой бы ход ни выбрали - диагональ или сторону - имеем вероятность получения ПП, а это означает, что мы вперед не продвинулись. Причем вероятность потрогать на следующем ходу "нетронутый" стакан одинакова, вне зависимости от выбора "сторона или диагональ", и составляет 50%.

Date: 2011-04-19 09:54 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Имеет, причем за фиксированное число ходов :)

Date: 2011-04-19 09:30 pm (UTC)
From: [identity profile] wouldnt.livejournal.com
Первый ход: Я бы взяла стаканы по диагонали, если они разные, то перевернула бы один чтобы оба были дном вниз. Если лампа не загорается, то вторая диагональ либо не симметрична, либо находится дном вверх.
Второй ход: снова смотрим ту же диагональ. Если стаканы одинаковые и дном вниз, то ход пропускаем и тогда будет 3 ход. Если разные, то переворачиаем один и тогда все 4 дном вниз - лампа загорается. Если одинаковые дном вверх - то переворачиваем оба, лампа загорается.
Третий ход - смтрим ту же диагональ, если 2 одинаковые и дном вниз, пропускаем... И так пока не найдем разные.

Date: 2011-04-19 09:56 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Да, но вам же может вечно попадаться одна и та же диагональ.
(screened comment)

Date: 2011-04-19 10:57 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Гениально, ты похоже даже на ход короче решил, чем я. Ща заскриню. :)

Date: 2011-04-20 06:05 am (UTC)
From: [identity profile] 3eta.livejournal.com
Допустим у стола четыре стакана: А, В, С и Д
Первая итерация: проверяем стакан справа и слева. Если положение у стаканов разное, приводим к одному, без разницы какому. Если одинаковое - переворачиваем оба (вдруг другие два тоже перевернуты). Допустим, мы выбрали стаканы дном вверх.
Итого: минимум два стакана у нас в правильном положении, если изначальное положение стаканов было разным. И три стакана в правильном положении, если изначально два выбранных стакана были дном вниз.

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

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

Date: 2011-04-20 06:55 am (UTC)
From: [identity profile] braindancer.livejournal.com
Ну мыслишь ты в правильном направлении :) Правильный ответ завтра, народ еще думает :)

(no subject)

From: [identity profile] mtplusj.livejournal.com - Date: 2011-04-21 06:39 pm (UTC) - Expand

(no subject)

From: [identity profile] mtplusj.livejournal.com - Date: 2011-04-21 06:48 pm (UTC) - Expand

(no subject)

From: [identity profile] 3eta.livejournal.com - Date: 2011-04-21 07:14 pm (UTC) - Expand

Date: 2011-04-20 07:45 am (UTC)
From: [identity profile] mel0dika.livejournal.com
а нельзя просто включатель нажать, что бы лампа включилась?)))

Date: 2011-04-20 07:49 am (UTC)
From: [identity profile] braindancer.livejournal.com
Ну вот, пришёл поручик и всё опошлил :)))

Date: 2011-04-20 02:22 pm (UTC)
From: [identity profile] leon5555.livejournal.com
твой моск силен аднако, так чо-то я сходу в аэропорту туплю, не вывешивай ответ следующие 36 часов - я как долечу, крепко падумаю :)))

Date: 2011-04-20 03:07 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Ну думай :) А куда это ты летишь 36 часов?? Это ж два раза вокруг Земли облететь можно

(no subject)

From: [identity profile] leon5555.livejournal.com - Date: 2011-04-20 03:56 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-20 03:58 pm (UTC) - Expand

(no subject)

From: [identity profile] leon5555.livejournal.com - Date: 2011-04-20 04:02 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-20 04:17 pm (UTC) - Expand

Date: 2011-04-20 07:01 pm (UTC)
From: [identity profile] helg.livejournal.com
Я бы поступил следующим образом.
Взял ближний левый и дальний правый стаканы, и поставил их, ну скажем, дном вниз.
Поворот 1.
Снова беру ближний левый и дальний правый стаканы. Если они стоят дном вверх, или один дном вниз, другой дном вверх - мне повезло, я попал на два "других" стакана. Просто переворачиваю их оба дном вниз и - вуаля!
Если же оба стакана стоят дном вниз - мне не повезло и я попал на те же стаканы, которые переворачивал в начале (это не могут быть два "других" стакана, иначе свет включился бы сразу). Тогда я переворачиваю их дном вверх. И тут мне может повезти - если два других стакана уже стоят дном вверх - свет включится. Если нет, то...
Поворот 2.
Сейчас я уже знаю, что 3 стакана на столе стоят дном вверх, и один - дном вниз. Тут уже не имеет значения, буду ли я брать стаканы по диагонали или с одной стороны - главное, буду вертеть стол до тех пор, пока мне не попадется стакан дном вниз, и тогда я его переверну дном вверх.
Таким образом, с наибольшей вероятностью я включу свет после первого же поворота.
Но возможно, не включу никогда - если стакан дном вниз будет постоянно от меня ускользать.

Date: 2011-04-20 08:43 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Ну вот фишка именно в том, чтобы гарантированно включить за некоторое определенное число ходов :) Так что твой вариант решением не считается, увы.

(no subject)

From: [identity profile] helg.livejournal.com - Date: 2011-04-20 08:53 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-20 09:29 pm (UTC) - Expand

Date: 2011-04-21 09:08 am (UTC)
From: [identity profile] poruchik.livejournal.com
Прикольная задачка.
Пользуясь предложенным выше обозначением, назовём стаканы П и Н.

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

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

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

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

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

Date: 2011-04-21 06:15 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Верно :) Интересно, что решений на 5 ходов, оказывается, несколько, я решал немного по-другому.

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 09:33 pm (UTC) - Expand
(screened comment)
From: [identity profile] leon5555.livejournal.com
что-то мне подсказывает, что здесь должно быть стройное, элегантное математическое решение - очень такие напоминающие что-то очень знакомое циклические пермутации (что-то на уровне де жа вю) - блин лень рыться в нете, но уверен, что есть формальное мат решение

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

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

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


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

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

ха
ах

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

хо
хх

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

оо
хх

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

ох
хо

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

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

Date: 2011-04-21 07:00 pm (UTC)
From: [identity profile] mtplusj.livejournal.com
Блин, как же просто получилось-то!

(no subject)

From: [identity profile] chillaxedcfa.livejournal.com - Date: 2011-04-21 07:03 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 07:21 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 09:34 pm (UTC) - Expand
(screened comment)

Date: 2011-04-21 08:33 pm (UTC)
From: [identity profile] mediaplayer.livejournal.com
5 ходов тоесть))

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 08:54 pm (UTC) - Expand

Date: 2011-04-21 09:15 pm (UTC)
From: [identity profile] dysto.livejournal.com
1. Взяли на одной стороне, если в одинаковом состоянии, то поменяли у обоих, если в разном, то поставили в одинаковое. Допустим, теперь они стоят дном вниз.
2. Взяли по диагонали, если оба дном вниз, оставили, если один дном вверх, то его перевернули. Теперь три стакана стоят дном вниз, один - вверх.
3. Взяли на одной стороне, если один дном вверх то его переворачиваем и конец, если оба дном вниз, переворачиваем правый дном вверх.
4. Взяли по диагонали, если стоят одинаково, то переворачиваем и конец, если по-разному то ничего не делаем.
5. Взяли на одной стороне, если стоят одинаково то переворачиваем и конец, если по разному то оба переворачиваем.
6. Берем по диагонали, они стоят одинаково, переворачиваем и конец.

Date: 2011-04-21 09:25 pm (UTC)
From: [identity profile] braindancer.livejournal.com
Ответ верный, хотя можно на ход короче :)

(no subject)

From: [identity profile] dysto.livejournal.com - Date: 2011-04-21 09:31 pm (UTC) - Expand

(no subject)

From: [identity profile] yury buzko - Date: 2011-04-21 10:14 pm (UTC) - Expand

(no subject)

From: [identity profile] dysto.livejournal.com - Date: 2011-04-21 10:59 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 11:04 pm (UTC) - Expand

(no subject)

From: [identity profile] ukrfan.livejournal.com - Date: 2011-04-21 11:05 pm (UTC) - Expand

(no subject)

From: [identity profile] dysto.livejournal.com - Date: 2011-04-21 11:09 pm (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 11:14 pm (UTC) - Expand

(no subject)

From: [identity profile] dysto.livejournal.com - Date: 2011-04-21 11:17 pm (UTC) - Expand

(no subject)

From: [identity profile] ukrfan.livejournal.com - Date: 2011-04-22 08:27 am (UTC) - Expand

(no subject)

From: [identity profile] braindancer.livejournal.com - Date: 2011-04-21 09:34 pm (UTC) - Expand
Page generated Aug. 21st, 2017 07:42 pm
Powered by Dreamwidth Studios