Форум умных людей > Задачи и головоломки > Логические задачи и головоломки (Модераторы: Илья, Лев) > Квадратик
Страниц: 1 [2]
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Квадратик  (Прочитано 7054 раз)
0 Пользователей и 1 Гость смотрят эту тему.
0. На входе на платформу "9 3/4" расположены 2015 переключателей, каждый из которых может иметь два состояния: ON и OFF. Разрешается за один рубль переключить или три произвольных соседних переключателя, или одну пару крайних переключателей (либо 1й и 2й, либо 2014й и 2015й). Докажите, что за конечное число таких операций можно все переключатели поставить в состояние  ON.

1.В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:
«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».

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

2. На входе в налоговую есть 2014 переключателей, каждый из которых может иметь два состояния: ON и OFF («вкл.» и «выкл.»), но по внешнему виду нельзя определить, в каком состоянии находится переключатель. За один рубль разрешается переключить какой-то один переключатель. Вход откроется, если ровно 1008 переключателей окажутся в состоянии ON, а остальные - в OFF. Какое наименьшее количество денег необходимо, стобы наверняка попасть в налоговую?
Димыч
Умник
****
Offline Offline

Сообщений: 770

СПАСИБО
-вы поблагодарили: 65
-вас поблагодарили: 384


Просмотр профиля
� Ответ #15 : Январь 26, 2015, 22:33:21 �
Я могу доказать, что есть ровно 2 решения (с точностью до симметрии) и в остальных случаях максимум будет не меньше 28. Но нужно картинки нарисовать для наглядности. В общем там 4 этапа: сначала оставляем для каждого красного квадратика прямоугольник 3×4, потом сокращаем его вдвое (на этом этапе уже появляется синий квадрат 5×5 в центре), потом еще раз вдвое, и в конце находим решения. Сейчас лень расписывать.

Эти пользователи сказали вам СПАСИБО :

Робинзон

За это сообщение 1 пользователь сказал спасибо!
Записан
Димыч рекомендует (upd. 2012-11-17)
Страниц: 1 [2]
  Печать  
« предыдущая тема следующая тема »
 
Перейти в: