Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
 Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
Есть 2N чуваков с разными именами.

На старте игры имя каждого записывается на бумажку, кладется в коробку (итого 2N коробок), коробки в закрытой комнате выставляются в рядок абсолютно случайным образом.

Каждый чел по очереди заходит в комнату, открывает N коробок, смотрит в них бумажки, выходит из комнаты, после чего коробки закрываются и всё в комнате приводится в состояние, которое было на момент захода чувака.
Из комнаты чувак выходит через другую дверь в другое помещение, больше в комнату не заходит и ничего не может сообщить тем, кто ещё не заходил.

Победа в игре - если все смогли найти свою бумажку.

Игроки должны заранее договориться и придумать стратегию, которая дает вероятность выигрыша не менее 30% на момент перед стартом игры, сколько бы чуваков не участвовало.
14 янв 20, 15:04    [22058877]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
игроки вызываются в комнату по очереди, через равные промежутки времени
соответственно, каждому дается время пребывания в комнате.
таким образом, игрок не может с помощью длительности своего пребывания передать какую-либо информацию.
14 янв 20, 15:08    [22058887]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59841
в брейнгеймс играешь что ли?
14 янв 20, 15:15    [22058900]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 1218
Имя пользователя1
Победа в игре - если все смогли найти свою бумажку.

я конечно не специалист, но по-моему у первого игрока всегда будет 50/50, ему никак не гарантируешь, что он найдёт себя...
14 янв 20, 16:16    [22058974]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Dima T
Member

Откуда:
Сообщений: 14347
При N=1 (2 игрока): первый открывает одну коробку, понимает где бумажка второго, как-то ее помечает, например ставит свою так чтобы коробка второго была справа. Второй берет свою. Минимум 50%.

При N>1: первые двое раскладывают на две равные кучи по первой букве имени, например А-М и Н-Я, остальные гарантированно себя найдут. Например при минимум N=2 (4 игрока) 2 точно найдут свою бумажку, это 50%. Дальше % будет расти.
14 янв 20, 16:31    [22059000]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
Dima T
как-то ее помечает

Имя пользователя1
выходит из комнаты, после чего коробки закрываются и всё в комнате приводится в состояние, которое было на момент захода чувака.
14 янв 20, 16:44    [22059024]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Напомнило задачу про бесконечный поезд в космосе. Только там - можно было ставить пометки.
14 янв 20, 17:03    [22059045]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
mayton
Напомнило задачу про бесконечный поезд в космосе. Только там - можно было ставить пометки.
я ни разу не видел поездов в космосе, особенно бесконечных.
Нельзя ли написать, что там?
14 янв 20, 17:41    [22059080]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Я напишу. Но судейства с моей стороны не будет т.к. правильного ответа я не знаю. И уточнений тоже не вспомню
т.к. было лет 10 назад.

Подсчет космических вагонов.
В космосе висит очень большая планета. Вокруг нее - по орбите летат очень длинный поезд из вагонов
завернутых в кольцо. Тоесть последний вагон сцеплен с первым. Ваша задача - посчитать вагоны.
Что у вас есть? У вас есть мел. И вы можете помечать вагон любой пометкой. И передвигатся вдоль
вагонов влево и вправо. Никаких других возможностей перемещаться у вас больше нет.

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

Нет никаких примерных оценок относительно размеров планеты и расстояний.
14 янв 20, 17:49    [22059082]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59841
писать на бумажках можно только имя?
14 янв 20, 17:58    [22059095]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59841
в одной коробке одна бумажка?
14 янв 20, 17:59    [22059098]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 59841
перекладывать бумажки тоже нельзя?
14 янв 20, 18:02    [22059105]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
mayton
Я напишу. Но судейства с моей стороны не будет т.к. правильного ответа я не знаю. И уточнений тоже не вспомню
т.к. было лет 10 назад.

Подсчет космических вагонов.
В космосе висит очень большая планета. Вокруг нее - по орбите летат очень длинный поезд из вагонов
завернутых в кольцо. Тоесть последний вагон сцеплен с первым. Ваша задача - посчитать вагоны.
Что у вас есть? У вас есть мел. И вы можете помечать вагон любой пометкой. И передвигатся вдоль
вагонов влево и вправо. Никаких других возможностей перемещаться у вас больше нет.

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

Нет никаких примерных оценок относительно размеров планеты и расстояний.

А, ну это классика, бесконечный поезд. В оригинале можно было только включать/выключать свет в вагонах.

Здесь интересно придумать решение, которое будет работать за линейное время. Обычно приводят решение с намного худшей асимптотикой.
14 янв 20, 18:03    [22059109]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Непонятно о чем они могут договариваться? Они по сути заходят и называют случайное число в диапазоне от 1 до 2N.
Они могут просто испортить линейность и всё время называть например одно число?

Автор - комментируй. Не молчи. Или кажется что все-таки есть некая "сигнальная система" в процессе. Но ты - умолчал.
14 янв 20, 18:06    [22059112]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
Aklin
писать на бумажках можно только имя?
да.
Одно имя - одна бумажка - одна коробка.

Перекладывать можно, но всё вернут на место. Читай условия. Никаких следов оставит не получится. Полы и стены вымоют, помещение проветрят.
14 янв 20, 18:08    [22059117]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
mayton
Непонятно о чем они могут договариваться? Они по сути заходят и называют случайное число в диапазоне от 1 до 2N.
Они могут просто испортить линейность и всё время называть например одно число?

Автор - комментируй. Не молчи. Или кажется что все-таки есть некая "сигнальная система" в процессе. Но ты - умолчал.
каждый заходящий просто молча открывает коробки и смотрит что в них.
Никакой сигнальной системы нет.
14 янв 20, 18:12    [22059121]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Хорошо. Я еще раз просто проговариваю (для себя) и для автора задачу в конкретных числах.

1) 20 человек. 20 коробок.
2) Один человек может открыть 10 коробок из 20.
3) После каждого человека корбоки - тасуются. Следы удаляются.
4) У каждого человека 1 попытка.
5) Передавать информацию о результате открытия коробок другим людям - нельзя.
6) Существуют вероятность того что 20 человек найдут свои имена. И эту вероятность мы можем оценить.
7) Автор считает что существует алгоритм ведущий к 30% выигрышу ВСЕХ людей сразу.

Верно ли я описал тезисы?
14 янв 20, 18:23    [22059125]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
mayton
Хорошо. Я еще раз просто проговариваю (для себя) и для автора задачу в конкретных числах.

1) 20 человек. 20 коробок.
2) Один человек может открыть 10 коробок из 20.
3) После каждого человека корбоки - тасуются. Следы удаляются.
4) У каждого человека 1 попытка.
5) Передавать информацию о результате открытия коробок другим людям - нельзя.
6) Существуют вероятность того что 20 человек найдут свои имена. И эту вероятность мы можем оценить.
7) Автор считает что существует алгоритм ведущий к 30% выигрышу ВСЕХ людей сразу.

Верно ли я описал тезисы?

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

И вероятность из п.6 надо оценить на момент перед игрой.
14 янв 20, 18:35    [22059131]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Соколинский Борис
Member

Откуда: Москва
Сообщений: 11584
Тут очевидно, нужно кооперативную стратегию искать. Примерно как 22058592
Но такой вероятности выигрыша у меня даже для 4-х игроков не получается.

OFF:
Вообще число странное, десятичных дробей никак не может быть в ответе. Может это 1/e ?
14 янв 20, 18:42    [22059135]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Соколинский Борис
Тут очевидно, нужно кооперативную стратегию искать. Примерно как 22058592
Но такой вероятности выигрыша у меня даже для 4-х игроков не получается.

OFF:
Вообще число странное, десятичных дробей никак не может быть в ответе. Может это 1/e ?

Он имел в виду больше 30%. Тоесть сойдет и 33.33% и т.д.
14 янв 20, 18:47    [22059141]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
msLex
Member

Откуда:
Сообщений: 7322
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


Чувакам надо поделиться на группы и каждая группа открывает свою часть коробок.

2/3 от общего количества открывает первую половину коробок
2/3 от оставшихся вторую половину коробок
2/3 от оставшихся первую половину коробок
и т.д.
14 янв 20, 19:57    [22059181]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
msLex
2/3 от общего количества открывает первую половину коробок
боюсь, в половине коробок не хватит имен на 2/3 участников.
14 янв 20, 20:08    [22059190]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
msLex
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


Чувакам надо поделиться на группы и каждая группа открывает свою часть коробок.

2/3 от общего количества открывает первую половину коробок
2/3 от оставшихся вторую половину коробок
2/3 от оставшихся первую половину коробок
и т.д.

Что такое "первая половина" ?
14 янв 20, 20:09    [22059191]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 448
mayton
msLex
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


Чувакам надо поделиться на группы и каждая группа открывает свою часть коробок.

2/3 от общего количества открывает первую половину коробок
2/3 от оставшихся вторую половину коробок
2/3 от оставшихся первую половину коробок
и т.д.

Что такое "первая половина" ?
как сказано в условии, коробки не свалены в кучу как попало, а стоят в рядок. Игроки могут заранее договориться, как обозначать для себя коробки в зависимости от их положения.
14 янв 20, 20:22    [22059202]     Ответить | Цитировать Сообщить модератору
 Re: Задача с коробками (из ветки про тервер)  [new]
mayton
Member

Откуда: loopback
Сообщений: 44240
Ага. Автор пишет
выставляются в рядок

Имеется в виду что есть декартов порядок. Ну... если игроки сговорились считать слева направо.
А коробки стоят сверху вниз. Фейл? ХЗ. В любом случае предполагается какая-то априорная инфа.

Иначе - пойди туда не знаю куда.
14 янв 20, 20:22    [22059203]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить