НГУ

Форумы НГУ
Текущее время: Вс фев 18, 2018 10:04 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Селедки-невидимки (по барабану - 2)
СообщениеДобавлено: Ср фев 01, 2006 9:11 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
N одинаковых кресел расставлены по периметру круговой карусели. В каждом кресле, в положении животом вверх или вниз, лежит невидимая селедка. Начальное положение селедок случайно. Одна попытка состоит в том, что вам закрывают глаза, карусель раскручивают и останавливают, после чего вы открываете глаза и заставляете некоторых (можно всех) селедок поменять свое положение на противоположное. (Ощупывание селедок строго запрещено!) Вы выиграете, если после одной из попыток или в начальном положении (повезло) все селедки расположатся животом вверх. При каких N можно выиграть наверняка и сколько для этого надо попыток?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Чт фев 02, 2006 12:09 am 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
Гост_Я писал(а):
<...> При каких N можно выиграть наверняка и сколько для этого надо попыток?
Чесслово, при N>1 я бы играть даже и не думал...

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 12:18 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
Кажется, при N=2 алгоритм очевиден:

1.Если все селёдки лежат животом вверх - вы выиграли.

2.Если вы не выиграли, то требуете, чтобы перевернули всех селёдок однвременно. Если все селёдки были животом вниз, то теперь они стали животом вверх, и вы выиграли.

Если вы опять не выиграли, то из этого следует, что одна селёдка лежит животом вниз, а другая - животом вверх. Тогда вы требуете перевернуть одну селёдку (неважно какую), и переходите снова к п.1. Максимум на четвёртом шаге вы выигрываете.

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 12:27 am 
Не в сети
Опытный автор

Зарегистрирован: Пн сен 13, 2004 12:08 am
Сообщения: 406
slb писал(а):
Кажется, при N=2 алгоритм очевиден <...>
Хм-м-м... Я-то был уверен, что после обьявления итогов (выиграл-не выиграл) игра по определению прекращается.

Автора!

_________________
КТО ИЩЕТ СМЫСЛ - ТОТ ГЛЯДИТ НА НЕБЕСА...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 10:45 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
SMS писал(а):
Автора!

Рассуждения slb показывают, что он правильно понимает постановку задачи. Для заданного N (количество селедок) требуется указать такое M (количество попыток), что после M попыток можно быть уверенным, что хотя бы однажды (после одной из этих M попыток) все селедки лежали брюшком вверх.
В качестве примера приведу решение для N=2. В исходном положении (или после очередной попытки) произвольной селедке присваиваем номер 1, а следующей за ней по часовой стрелке номер два. Тогда решение из трех попыток запишем так 12 - 1 - 12, т.е. сначала вертим обе селедки, затем одну, затем снова обе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 12:26 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
Что-то у меня ощущение, что при N=3 алгоритма, гарантирующего выигрыш, не существует, можно лишь максимизировать вероятность.

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 3:12 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Предлагаю селёдку заменить на камбалу, а то не получается - как ни положу, они всё на бок сваливаются.

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 02, 2006 3:31 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
bolbot писал(а):
Предлагаю селёдку заменить на камбалу, а то не получается - как ни положу, они всё на бок сваливаются.

Можно еще заменить на депутата, которого не видно в кресле, но он там есть, т.к. голосует. Депутат может устойчиво лежать на животе, на спине и в любом промежуточном состоянии.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн фев 06, 2006 11:08 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Подсказка.
Селедки в каждой из N пар диаметрально противоположных селедок в 2N-селедочной карусели могут иметь одинаковую или различную ориентацию. Таким образом задача для 2N селедок сводится к задаче для N селедок. Точнее:
(решение для 2N селедок) = (решение для N селедок)^2.

Скрытая подсказка.
Формулировку и решение этой задачи можно найти в интернете, например, по ключевым словам: COINS ON A LAZY SUSAN


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт фев 07, 2006 10:34 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Гост_Я писал(а):
bolbot писал(а):
Предлагаю селёдку заменить на камбалу, а то не получается - как ни положу, они всё на бок сваливаются.

Можно еще заменить на депутата, которого не видно в кресле, но он там есть, т.к. голосует. Депутат может устойчиво лежать на животе, на спине и в любом промежуточном состоянии.

Гост_Я, да как же можно лежать в кресле на животе? Думаю, лучше вместо кресел взять скамейки, как в МА, а класть на них студентов. Это будет весьма естественное зрелище.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 08, 2006 1:00 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2848
Откуда: Станислав Березнюк
Кажется, я сумел доказать, что при N>2 решения не существует.


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

С этой точки зрения очевидно, что переворачивание 1 селёдки эквивалентно переворачиванию N-1 селёдки, а переворачивание 2 селёдок - переворачиванию N-2 селёдок, и т.д.. Таким образом, нам достаточно рассмотреть, что будет в случае, когда не все селёдки лежат одной стороной вверх, если мы перевернём 1 селёдку, 2 селёдки, и для случая N>4 - k селёдок, где 2<k<N-2.

Очевидно, что если на текущем шаге мы не выиграли, то это означает, что существует две разноориентированные селёдки. Так как мы выбираем селёдки случайным образом, то всегда может реализоваться наихудший вариант, а именно:
- если мы решим перевернуть одну селёдку - то это будет селёдка, не имеющая отношения к разноориентированной паре, и ситуация принципиально не изменится;
- если мы решим перевернуть две селёдки - то это будут именно эти две селёдки, и ситуация принципиально не изменится;
- если мы решим перевернуть k селёдок - то в выбранные для переворачивания попадёт и разноориентированная пара, и ситуация принципиально не изменится;

Таким образом, при любом шаге всегда возможен случай, что ситуация принципиально не изменится. Значит, выигрышной стратегии не существует.


Гост_Я, каков ваш алгоритм при N=4?

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 08, 2006 2:13 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
slb писал(а):
Кажется, я сумел доказать, что при N>2 решения не существует...
Очевидно, что если на текущем шаге мы не выиграли, то это означает, что существует две разноориентированные селёдки...
- если мы решим перевернуть две селёдки - то это будут именно эти две селёдки, и ситуация принципиально не изменится;...

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

Мне кажется, что при N, которые не являются степенью 2, решения нет. При N=2, 4 точно есть.

Товарищи, не может селёдка лежать на спине!!! У ней там плавничок. Давайте переворачивать студентов.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 08, 2006 2:24 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
Pavel E. Alaev писал(а):
Давайте переворачивать студентов.

Не, на спине они храпеть начнут и тем самым демаскируются. Это уже задача для глухого получится. С депутатами задача станет некорректной - не всякого брюхом на твёрдое покрытие уложить можно.
Настаиваю на камбале. Смотришь на кресло - оно пустое, а на самом деле там камбала лежит, невидимая. Прикольно.

_________________
Наука умеет много гитик.


Последний раз редактировалось bolbot Ср фев 08, 2006 2:32 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 08, 2006 2:30 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Камбала известна тем, что у неё два глаза на боку. Но при этом остальное тело устроено стандартно - с одной стороны внутренности (живот), с другой мышцы (спина). Поэтому камбала ни на спине, ни на животе лежать не может, а только на боку.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 08, 2006 2:34 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт ноя 20, 2003 9:07 pm
Сообщения: 1919
Откуда: СССР
А мы переопределим:
Живот камбалы - светлая сторона туловища
Спина камбалы - тёмная сторона туловища

_________________
Наука умеет много гитик.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB