ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с коробками (из ветки про тервер)
95 сообщений из 95, показаны все 4 страниц
  все  
Задача с коробками (из ветки про тервер)
    #39913709
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Есть 2N чуваков с разными именами.

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

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

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

Игроки должны заранее договориться и придумать стратегию, которая дает вероятность выигрыша не менее 30% на момент перед стартом игры, сколько бы чуваков не участвовало.
...
Рейтинг: 0 / 0
14.01.2020, 15:04
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913716
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
игроки вызываются в комнату по очереди, через равные промежутки времени
соответственно, каждому дается время пребывания в комнате.
таким образом, игрок не может с помощью длительности своего пребывания передать какую-либо информацию.
...
Рейтинг: 0 / 0
14.01.2020, 15:08
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913724
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
в брейнгеймс играешь что ли?
...
Рейтинг: 0 / 0
14.01.2020, 15:15
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913777
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
Имя пользователя1
Победа в игре - если все смогли найти свою бумажку.

я конечно не специалист, но по-моему у первого игрока всегда будет 50/50, ему никак не гарантируешь, что он найдёт себя...
...
Рейтинг: 0 / 0
14.01.2020, 16:16
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913796
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
При N=1 (2 игрока): первый открывает одну коробку, понимает где бумажка второго, как-то ее помечает, например ставит свою так чтобы коробка второго была справа. Второй берет свою. Минимум 50%.

При N>1: первые двое раскладывают на две равные кучи по первой букве имени, например А-М и Н-Я, остальные гарантированно себя найдут. Например при минимум N=2 (4 игрока) 2 точно найдут свою бумажку, это 50%. Дальше % будет расти.
...
Рейтинг: 0 / 0
14.01.2020, 16:31
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913815
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Dima T
как-то ее помечает

Имя пользователя1
выходит из комнаты, после чего коробки закрываются и всё в комнате приводится в состояние, которое было на момент захода чувака.
...
Рейтинг: 0 / 0
14.01.2020, 16:44
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913830
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Напомнило задачу про бесконечный поезд в космосе. Только там - можно было ставить пометки.
...
Рейтинг: 0 / 0
14.01.2020, 17:03
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913853
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Напомнило задачу про бесконечный поезд в космосе. Только там - можно было ставить пометки.
я ни разу не видел поездов в космосе, особенно бесконечных.
Нельзя ли написать, что там?
...
Рейтинг: 0 / 0
14.01.2020, 17:41
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913855
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я напишу. Но судейства с моей стороны не будет т.к. правильного ответа я не знаю. И уточнений тоже не вспомню
т.к. было лет 10 назад.

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

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

Нет никаких примерных оценок относительно размеров планеты и расстояний.
...
Рейтинг: 0 / 0
14.01.2020, 17:49
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913863
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
писать на бумажках можно только имя?
...
Рейтинг: 0 / 0
14.01.2020, 17:58
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913865
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
в одной коробке одна бумажка?
...
Рейтинг: 0 / 0
14.01.2020, 17:59
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913871
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
перекладывать бумажки тоже нельзя?
...
Рейтинг: 0 / 0
14.01.2020, 18:02
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913875
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Я напишу. Но судейства с моей стороны не будет т.к. правильного ответа я не знаю. И уточнений тоже не вспомню
т.к. было лет 10 назад.

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

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

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

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

Здесь интересно придумать решение, которое будет работать за линейное время. Обычно приводят решение с намного худшей асимптотикой.
...
Рейтинг: 0 / 0
14.01.2020, 18:03
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913877
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Непонятно о чем они могут договариваться? Они по сути заходят и называют случайное число в диапазоне от 1 до 2N.
Они могут просто испортить линейность и всё время называть например одно число?

Автор - комментируй. Не молчи. Или кажется что все-таки есть некая "сигнальная система" в процессе. Но ты - умолчал.
...
Рейтинг: 0 / 0
14.01.2020, 18:06
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913881
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aklin
писать на бумажках можно только имя?
да.
Одно имя - одна бумажка - одна коробка.

Перекладывать можно, но всё вернут на место. Читай условия. Никаких следов оставит не получится. Полы и стены вымоют, помещение проветрят.
...
Рейтинг: 0 / 0
14.01.2020, 18:08
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913884
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Непонятно о чем они могут договариваться? Они по сути заходят и называют случайное число в диапазоне от 1 до 2N.
Они могут просто испортить линейность и всё время называть например одно число?

Автор - комментируй. Не молчи. Или кажется что все-таки есть некая "сигнальная система" в процессе. Но ты - умолчал.
каждый заходящий просто молча открывает коробки и смотрит что в них.
Никакой сигнальной системы нет.
...
Рейтинг: 0 / 0
14.01.2020, 18:12
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913887
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Хорошо. Я еще раз просто проговариваю (для себя) и для автора задачу в конкретных числах.

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

Верно ли я описал тезисы?
...
Рейтинг: 0 / 0
14.01.2020, 18:23
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913893
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Хорошо. Я еще раз просто проговариваю (для себя) и для автора задачу в конкретных числах.

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

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

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

И вероятность из п.6 надо оценить на момент перед игрой.
...
Рейтинг: 0 / 0
14.01.2020, 18:35
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913895
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Тут очевидно, нужно кооперативную стратегию искать. Примерно как 22058592
Но такой вероятности выигрыша у меня даже для 4-х игроков не получается.

OFF:
Вообще число странное, десятичных дробей никак не может быть в ответе. Может это 1/e ?
...
Рейтинг: 0 / 0
14.01.2020, 18:42
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Соколинский Борис
Тут очевидно, нужно кооперативную стратегию искать. Примерно как 22058592
Но такой вероятности выигрыша у меня даже для 4-х игроков не получается.

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

Он имел в виду больше 30%. Тоесть сойдет и 33.33% и т.д.
...
Рейтинг: 0 / 0
14.01.2020, 18:47
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913925
msLex
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
msLex
Участник
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


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

2/3 от общего количества открывает первую половину коробок
2/3 от оставшихся вторую половину коробок
2/3 от оставшихся первую половину коробок
и т.д.
...
Рейтинг: 0 / 0
14.01.2020, 19:57
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913930
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
msLex
2/3 от общего количества открывает первую половину коробок
боюсь, в половине коробок не хватит имен на 2/3 участников.
...
Рейтинг: 0 / 0
14.01.2020, 20:08
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913931
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
msLex
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


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

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

Что такое "первая половина" ?
...
Рейтинг: 0 / 0
14.01.2020, 20:09
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913937
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
msLex
Надо полагать единственно чем можно управлять - это стратегия открытия коробок (т.е. какие коробки открывать)


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

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

Что такое "первая половина" ?
как сказано в условии, коробки не свалены в кучу как попало, а стоят в рядок. Игроки могут заранее договориться, как обозначать для себя коробки в зависимости от их положения.
...
Рейтинг: 0 / 0
14.01.2020, 20:22
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913938
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ага. Автор пишет
выставляются в рядок
Имеется в виду что есть декартов порядок. Ну... если игроки сговорились считать слева направо.
А коробки стоят сверху вниз. Фейл? ХЗ. В любом случае предполагается какая-то априорная инфа.

Иначе - пойди туда не знаю куда.
...
Рейтинг: 0 / 0
14.01.2020, 20:22
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913943
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Ага. Автор пишет
выставляются в рядок

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

Иначе - пойди туда не знаю куда.ну пусть коробки стоят на длинном горизонтальном столе.

В любом случае, игрокам заранее детально распишут все нюансы, потом они будут договариваться о стратегии. По моему, это очевидно.
...
Рейтинг: 0 / 0
14.01.2020, 20:26
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913946
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
в задаче интересен как поиск стратегии, так и подсчет вероятности. Оба компонента оставляют приятное послевкусие на долгие годы.
...
Рейтинг: 0 / 0
14.01.2020, 20:35
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913947
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Очевидно, что для чуваков стратегия непрерываного выбора коробок с простым шагом,
не кратным N, обеспечит равномерное покрытие проверками всего множества коробок.

Вопрос в том, обеспечит ли она нужную вероятность?
...
Рейтинг: 0 / 0
14.01.2020, 20:38
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913949
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
mayton
Что такое "первая половина" ?

Коробки стоят в ряд, т.е. можно договориться по какому правилу открывать, например если каждый игрок будет открывать коробки с первой по N, то они проиграют в ста процентах случаев, потому что только половина игроков в этом случае найдет свои бумажки, тоже самое если они будут отрывать с N+1 до 2N.
...
Рейтинг: 0 / 0
14.01.2020, 20:42
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913952
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
Вопрос в том, обеспечит ли она нужную вероятность?
разумеется, нет. это даже навскидку легко проверить, не вычисляя вероятность
...
Рейтинг: 0 / 0
14.01.2020, 20:49
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913956
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
20 человек. Каждый из которых. Независимо от других находит свою коробку с вероятностью 0.5. Событие A.
Событие - все 20 нашли свои коробки как по мне является пересеченеем независимых событий A 20 раз.

По моему получается
...
Рейтинг: 0 / 0
14.01.2020, 20:54
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913957
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Имя пользователя1,

События независимы, вероятность для каждого игрока найти свою бумажку 1/2, соответственно вероятность для всех равна 0.5 в степени N, при условии что стратегия покрывает весь набор коробок, откуда вы хотите взять 30 процентов?
...
Рейтинг: 0 / 0
14.01.2020, 20:55
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913958
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя1,

Проверил для N=1: обеспечивает.
...
Рейтинг: 0 / 0
14.01.2020, 20:55
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913960
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
В условии не хватает связи событий, например нашедший уносит свою коробку.
...
Рейтинг: 0 / 0
14.01.2020, 20:57
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913963
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
mayton
20 человек. Каждый из которых. Независимо от других находит свою коробку с вероятностью 0.5. Событие A.
Событие - все 20 нашли свои коробки как по мне является пересечением независимых событий A 20 раз.

Нужно сделать из зависимыми.
...
Рейтинг: 0 / 0
14.01.2020, 21:04
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913972
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
Имя пользователя1,

Проверил для N=1: обеспечивает.
а, например, для N=10 не обеспечивает.
...
Рейтинг: 0 / 0
14.01.2020, 21:12
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913973
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
iOracleDev
В условии не хватает связи событий, например нашедший уносит свою коробку.
в условии всего хватает.
...
Рейтинг: 0 / 0
14.01.2020, 21:14
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913976
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя1,

может ли чувак в комнате перекладывать бумажки в открытых им коробках? ))
...
Рейтинг: 0 / 0
14.01.2020, 21:18
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913979
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
Имя пользователя1,

может ли чувак в комнате перекладывать бумажки в открытых им коробках? ))
22059024
...
Рейтинг: 0 / 0
14.01.2020, 21:31
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913988
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Имя пользователя1
Aleksandr Sharahov
Имя пользователя1,

может ли чувак в комнате перекладывать бумажки в открытых им коробках? ))
22059024
Значит, могут, и это сильно упрощает дело.
Чувак просто упорядочивает открытые бумажки по алфавиту. При правильной системе обхода, которую я пока не придумал, должно где-то возникнуть число e.
...
Рейтинг: 0 / 0
14.01.2020, 21:48
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913991
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Соколинский Борис,

а че там думать)

открыл коробку, там - 42, куда засунуть эту 42 - понятно сразу
...
Рейтинг: 0 / 0
14.01.2020, 21:52
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913993
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
авторвсё в комнате приводится в состояние, которое было на момент захода чувака.
господа, вам непонятно это предложение?

абсолютно все изменения, которые чел сделал в комнате, откатятся сразу после его выхода, до захода следующего чела.

задача на логику, а не на смекалку.
...
Рейтинг: 0 / 0
14.01.2020, 21:56
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913994
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Примерная схема:
1. Все чуваки договариваются о последовательности обхода по алфавиту.
2. Первый чувак если найдет свое имя - кладет его в первую коробку.
2.Следом идет последний по алфавиту. Он открывает коробку с номерами n, n+2.. 2N.
3. Чувак из середины.
...
Надо дорихтовать, но уже намечается что-то вроде Shell-сортировки.
...
Рейтинг: 0 / 0
14.01.2020, 21:57
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39913999
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Имя пользователя1
сколько бы чуваков не участвовало.

Давайте рассмотрим пример с двумя чуваками, две коробки, каждый чувак может посмотреть только одну, если оба посмотрят одинаковую коробку, то они проиграли, стратегия только одна - посмотреть разные коробки, первый первую второй вторую или первый вторую второй первую неважно в плане исхода. Вероятность обнаружить свое имя у каждого из них 1/2, т.е. вероятность выигрыша при стратегии дающей возможность выигрыша 1/4.
...
Рейтинг: 0 / 0
14.01.2020, 22:04
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914006
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
iOracleDev
Имя пользователя1
сколько бы чуваков не участвовало.

Давайте рассмотрим пример с двумя чуваками, две коробки, каждый чувак может посмотреть только одну, если оба посмотрят одинаковую коробку, то они проиграли, стратегия только одна - посмотреть разные коробки, первый первую второй вторую или первый вторую второй первую неважно в плане исхода. Вероятность обнаружить свое имя у каждого из них 1/2, т.е. вероятность выигрыша при стратегии дающей возможность выигрыша 1/4.

Хотя нет не так, если первый угадал, то второй тоже автоматически угадал, если первый не угадал, то второй тоже автоматически не угадал, от второго исход уже не зависит, в случае двоих чуваков вероятность 1/2.
...
Рейтинг: 0 / 0
14.01.2020, 22:15
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914010
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
Имя пользователя1
открывает N коробок, смотрит в них бумажки, выходит из комнаты

таки он с собой бумажку уносит, если нашёл?
...
Рейтинг: 0 / 0
14.01.2020, 22:38
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914019
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
полудух
Имя пользователя1
открывает N коробок, смотрит в них бумажки, выходит из комнаты

таки он с собой бумажку уносит, если нашёл?
22059280
...
Рейтинг: 0 / 0
14.01.2020, 23:06
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914024
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
так у нас ещё и вариант, что все найдут одну и ту же бамажку...
...
Рейтинг: 0 / 0
14.01.2020, 23:28
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914030
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Стратегия - каждый i-й игрок смотрит коробку начиная со своего номера i до i+N-1.
...
Рейтинг: 0 / 0
15.01.2020, 00:06
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914046
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
iOracleDev
Стратегия - каждый i-й игрок смотрит коробку начиная со своего номера i до i+N-1.

Так все коробки будут просмотрены одинаковое число раз.

Но на формулу вероятности выигрыша всех это не влияет.
...
Рейтинг: 0 / 0
15.01.2020, 01:41
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914048
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
mayton
Так все коробки будут просмотрены одинаковое число раз.

Но на формулу вероятности выигрыша всех это не влияет.

Формула возможно неправильная, нужно не только одинаковое число просмотров коробок, но и максимальная связность всех со всеми при минимальных зацикливаниях друг на друга, на вероятность влияет.
...
Рейтинг: 0 / 0
15.01.2020, 02:03
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914097
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alibek B
Участник
Имя пользователя1
после чего коробки закрываются и всё в комнате приводится в состояние, которое было на момент захода чувака.

Ну так пусть каждый игрок i открывает коробки, начиная с 1+(i-1)*2.
Тогда игроки гарантированно откроют все коробки (не будет коробки, которую ни открыл никто).
И будет определенная вероятность, что при этом каждый встретит свою бумажку.
Эта стратегия не гарантирует победу, но повышает ее вероятность до максимальной.
...
Рейтинг: 0 / 0
15.01.2020, 09:20
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914098
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Имя пользователя1
Dima T
как-то ее помечает

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

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

PS Весь топик не читал, возможно уже предлагали.
...
Рейтинг: 0 / 0
15.01.2020, 09:27
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914099
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alibek B
Участник
Если между событиями нет ни связи, ни передачи информации, то это близко к бросанию монетки N раз, где выигрышем будет выпадение решки N раз.
Но поскольку победой будет, если все игроки найдут свои коробки, то есть определенная вероятность того, что какая-то коробка (или коробки) не будут открыты ни разу — и это будет вероятность гарантированного проигрыша.
Поэтому лучшее, что можно сделать — это свести эту вероятность к нулю, для чего нужен такой порядок открытия коробок, чтобы неоткрытой коробки не осталось.

Приведенная стратегия — это стратегия не того, как выиграть (я не вижу такой стратегии), а как не проиграть.
...
Рейтинг: 0 / 0
15.01.2020, 09:35
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914100
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
если доказать, что вероятность того,
что случайная перестановка длины 2N содержит цикл длины от N+1 до 2N,
менее 0.3, то я знаю решение ))
...
Рейтинг: 0 / 0
15.01.2020, 09:49
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914101
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
iOracleDev
mayton
Так все коробки будут просмотрены одинаковое число раз.

Но на формулу вероятности выигрыша всех это не влияет.

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

Дай твою формулу.
...
Рейтинг: 0 / 0
15.01.2020, 09:50
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914111
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
если доказать, что вероятность того,
что случайная перестановка длины 2N содержит цикл длины от N+1 до 2N,
менее 0.3, то я знаю решение ))
возможно, стоит озвучить здесь это решение, а потом уж упороться в элементарную комбинаторику, под занавес вспомнив одну симпатичную формулу про асимптотику:)
...
Рейтинг: 0 / 0
15.01.2020, 10:05
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914139
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты
...
Рейтинг: 0 / 0
15.01.2020, 10:37
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914145
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я выше написал что 50% гарантированно без всяких хитростей. Каждый тупо открывает первые N. Вероятность что найдет свою N/2N = 0.5
...
Рейтинг: 0 / 0
15.01.2020, 10:42
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914147
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Dima T
Тогда все игроки открывают одни и те же коробки. Половина найдет свои бумажки.
надо, чтобы каждый нашел свою коробку.
а так половина не найдет, это заведомый фейл
Aleksandr Sharahov
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты
ок, осталось промыслить вероятность.
...
Рейтинг: 0 / 0
15.01.2020, 10:44
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914236
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте иммитационную модельку. Как и с днями рождений мы все сомневались.
...
Рейтинг: 0 / 0
15.01.2020, 12:45
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914258
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Давайте иммитационную модельку. Как и с днями рождений мы все сомневались.
?
...
Рейтинг: 0 / 0
15.01.2020, 13:09
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914263
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
Давайте иммитационную модельку. Как и с днями рождений мы все сомневались.
?

Дима пишет.
Я выше написал что 50% гарантированно без всяких хитростей. Каждый тупо открывает первые N. Вероятность что найдет свою N/2N = 0.5

Я отвечаю. Надо смоделировать.
...
Рейтинг: 0 / 0
15.01.2020, 13:13
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914266
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Имя пользователя1
пропущено...
?

Дима пишет.
Я выше написал что 50% гарантированно без всяких хитростей. Каждый тупо открывает первые N. Вероятность что найдет свою N/2N = 0.5

Я отвечаю. Надо смоделировать.Дима не совсем правильно понял задачу, скорее всего.

Победа в игре - это когда все нашли свои имена. Если хоть один игрок не нашел, это то же самое, как если бы никто не нашел. И надо максимизировать вероятность побед, а не единичных находок.
...
Рейтинг: 0 / 0
15.01.2020, 13:18
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914268
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
пропущено...

Дима пишет.
пропущено...

Я отвечаю. Надо смоделировать.
Дима не совсем правильно понял задачу, скорее всего.

Победа в игре - это когда все нашли свои имена. Если хоть один игрок не нашел, это то же самое, как если бы никто не нашел. И надо максимизировать вероятность побед, а не единичных находок.

Что думаешь насчет моей формулы?
...
Рейтинг: 0 / 0
15.01.2020, 13:20
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914274
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Имя пользователя1
пропущено...
Дима не совсем правильно понял задачу, скорее всего.

Победа в игре - это когда все нашли свои имена. Если хоть один игрок не нашел, это то же самое, как если бы никто не нашел. И надо максимизировать вероятность побед, а не единичных находок.

Что думаешь насчет моей формулы?
22059224 ?
ну да, если каждый будет независимо от других просто открывать половину коробок, то так и выходит, об этом я сразу сказал 22058302
...
Рейтинг: 0 / 0
15.01.2020, 13:25
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914290
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Имя пользователя1
mayton
пропущено...

Что думаешь насчет моей формулы?
22059224 ?
ну да, если каждый будет независимо от других просто открывать половину коробок, то так и выходит, об этом я сразу сказал 22058302

Ну а если они будут открывать серии по формуле от номера человека следующие N штук. По модулю 2N.

Я считаю что на формулу не влияет.
...
Рейтинг: 0 / 0
15.01.2020, 13:39
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914294
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Имя пользователя1
пропущено...
22059224 ?
ну да, если каждый будет независимо от других просто открывать половину коробок, то так и выходит, об этом я сразу сказал 22058302

Ну а если они будут открывать серии по формуле от (N % человек до (N + 1) % человек) ?

Я считаю что на формулу не влияет.
влияет, но незначительно. Смысла в этом нет, всё равно шансы копеечные.

вот в стратегии Сани Шарахова совсем другие расклады.
...
Рейтинг: 0 / 0
15.01.2020, 13:43
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914295
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
дубль сообщения.
...
Рейтинг: 0 / 0
15.01.2020, 13:43
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914299
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты

Насколько я понимаю. Шарахов предлагает пронумеровать людей.
(это как я понимаю и есть "договорняк" до начала эксперимента)

И здесь я не совсем понял
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
Хорошо-бы перефразировать. Боюсь ошибится.
...
Рейтинг: 0 / 0
15.01.2020, 13:48
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914301
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Всего перестановок: (2N)!

Из них циклом длины N+1: (2N)!/(N+1)
Из них циклом длины N+2: (2N)!/(N+2)
....
Из них циклом длины 2N: (2N)!/(2N)

Всего с длинным циклом: (2N)!*{[1/(N+1)]+[1/(N+2)]+[1/(2N)]}

Нужно показать, что их доля в общем количестве: P=[1/(N+1)]+[1/(N+2)]+[1/(2N)]<0.7
...
Рейтинг: 0 / 0
15.01.2020, 13:48
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914306
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Aleksandr Sharahov
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты

Насколько я понимаю. Шарахов предлагает пронумеровать людей.
(это как я понимаю и есть "договорняк" до начала эксперимента)

И здесь я не совсем понял
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру

Хорошо-бы перефразировать. Боюсь ошибится.

Отсортируем чуваков по алфавиту
и вместо фамилий будем использовать их порядковый номер.
Перефразирую:
2б) если открытой в коробке лежит номер другого чувака,
то полагаем текущий номер равным обнаруженному номеру.
...
Рейтинг: 0 / 0
15.01.2020, 13:54
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914313
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
Всего перестановок: (2N)!

Из них циклом длины N+1: (2N)!/(N+1)
Из них циклом длины N+2: (2N)!/(N+2)
....
Из них циклом длины 2N: (2N)!/(2N)

Всего с длинным циклом: (2N)!*{[1/(N+1)]+[1/(N+2)]+[1/(2N)]}

Нужно показать, что их доля в общем количестве: P=[1/(N+1)]+[1/(N+2)]+[1/(2N)]<0.7
пока всё верно
...
Рейтинг: 0 / 0
15.01.2020, 14:02
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914316
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Имя пользователя1
пропущено...
?

Дима пишет.
Я выше написал что 50% гарантированно без всяких хитростей. Каждый тупо открывает первые N. Вероятность что найдет свою N/2N = 0.5

Я отвечаю. Надо смоделировать.
Я неправильно условия понял 22059507
...
Рейтинг: 0 / 0
15.01.2020, 14:05
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914318
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Aleksandr Sharahov
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты

А что делать если в 7-й коробке номер 7 ?
...
Рейтинг: 0 / 0
15.01.2020, 14:07
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914324
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя1,

компьютер говорит, что при N>=110 неравенство выполняется.
Возможно, при большей точности вычислений граничное N может быть улучшено.

Как аналитически доказать, пока не понятно.
...
Рейтинг: 0 / 0
15.01.2020, 14:15
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914326
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alibek B
Участник
Aleksandr Sharahov

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты

Игроков - N. А коробок - 2N.
Допустим в коробке 1 лежит номер 2. Игрок 2 никогда не откроет эту коробку, потому что будет начинать с коробки 2.
...
Рейтинг: 0 / 0
15.01.2020, 14:16
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914327
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima T
Aleksandr Sharahov
Имя пользователя1,

0) чувак полагает текущий номер коробки равным своему номеру
1) чувак открывает коробку с текущим номером
2а) если там лежит его номер, то выходит из комнаты
2б) если там лежит чужой, то полагает текущий номер коробки равным чужому номеру
3) повторяет п.1-2 пока не откроет N коробок
4) выходит из комнаты

А что делать если в 7-й коробке номер 7 ?


Седьмой чувак откроет коробку и покинет помещение.
Он сделал свое дело.
...
Рейтинг: 0 / 0
15.01.2020, 14:17
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914332
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Alibek B.,

игроков 2N
...
Рейтинг: 0 / 0
15.01.2020, 14:19
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914336
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alibek B
Участник
Если убрать всю словесную мишуру, то задача сводится к тому, что каждый игрок должен открыть половину коробок и игроки выигрывают, если при этом каждый игрок найдет свою коробку.
Если игроки будут открывать коробки независимо друг от друга, то есть вероятность того, что какая-то коробка так и не будет открыта ни одним из игроков, что будет гарантированным проигрышем.
Чтобы этого не было, игроки должны открывать коробки так, чтобы неоткрытых коробок не осталось — это довольно легко сделать (например нечетные начинают открывать коробки с начала, четные с конца, каждый открывает N коробок, пропуская первые i-1 коробок, где i порядковый номер игрока).
Вероятность выигрыша это не повысит, но снизит вероятность проигрыша (исключив гарантированный проигрыш, когда останутся неоткрытые коробки).
...
Рейтинг: 0 / 0
15.01.2020, 14:22
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914338
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alibek B
Участник
Aleksandr Sharahov
игроков 2N

О. Да, это совсем другое дело.
Тогда стратегия с максимальной вероятностью выигрыша возможна.
...
Рейтинг: 0 / 0
15.01.2020, 14:23
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914341
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Aleksandr Sharahov
1/(N+1)]+[1/(N+2)]+[1/(2N)
тут асимптотика
...
Рейтинг: 0 / 0
15.01.2020, 14:25
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914350
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ага. Если-бы у нас было 3N людей и N коробок тогда точно оставались-бы неоткрытые.
...
Рейтинг: 0 / 0
15.01.2020, 14:37
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914401
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
mayton
Дай твою формулу.

Давал уже
iOracleDev
Стратегия - каждый i-й игрок смотрит коробку начиная со своего номера i до i+N-1.


Насчет связности, пример расчета для простой но неправильной стратегии: игроков 4
раскладываем игроков и коробки в две корзины, игроки 1 и 2 открывают коробки 1 и 2,
соответственно игроки 3 и 4 открывают корзины 3 и 4. Каждая коробка открывается по два раза.

для первого игрока вероятность положительного результата 1/2, в случае положительного результата
для первого игрока, вероятность положительного результата для второго равна 1/3, потому что у него
одна попытка стала заведомо проигрышной и сделала ее таковой первый игрок угадав свою коробку.
Итого вероятность на данный момент 1/6 для всех. Далее в случае если первый и второй игроки угадали
свои коробки, то третий и четвертый могут не играть вообще, потому что для них вероятность стала 1.
Итоговый результат выигрыша для всех 1/6, так как то.

PS: для своей формулы не считал))
...
Рейтинг: 0 / 0
15.01.2020, 15:59
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914409
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Соколинский Борис
Aleksandr Sharahov
1/(N+1)]+[1/(N+2)]+[1/(2N)
тут асимптотика [img=https://www.codecogs.com/eq.latex?Ln{(2)}]
да, всё верно, стремится к ln(2)

а поскольку [1/(N+1)]+[1/(N+2)]+...+[1/(2N)] монотонно возрастает с увеличением N (что элементарно доказать), то выше ln(2) никогда не поднимется.
...
Рейтинг: 0 / 0
15.01.2020, 16:11
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914431
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Каждый игрок должен случайно выбирать коробки.
Тривиальный случай - N = 1, вероятность выигрыша равна:
Код: plaintext
1.
2.
1   3   2   1
- = - > - = -
2   6   6   3

Следующий шаг - N = 2:
Код: plaintext
1.
2.
1   1    7   147   144   1
- + - = -- = --- > --- = -
4   3   12   432   432   3

Дальше требуется уметь суммировать по m последовательность 1/(2N - m), где m пробегает значения от 1 до N.
Я - не умею.
...
Рейтинг: 0 / 0
15.01.2020, 16:33
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914447
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Меня опять терзают смутные сомнения, что стратегию можно улучшить только при четырёх условиях:
1. Игрок знает свой порядковый номер
2. Игроки заходят в комнату в порядке своих номеров
3. Проверяемые 2N коробок выставлены в ряд и могут быть "перенуменованы слева направо" (для арабов - справа налево, для японцев и китайцев - сверху вниз)
4. Допускается ровно одна перестановка.

Первый игрок просматривает N случайно выбранных коробок. Не нашёл искомое - проигрыш. Нашёл - поменял найденное с первой коробкой.
Т.е. каждый или проигрывает или переставляет найденную коробку на позицию, равню своему порядковому номеру.
В результате будет постоянно уменьшаться число проверяемых коробок, а N-ому игроку потребуется проверить N из N+1 коробки, что "почти наверняка выигрыш".
...
Рейтинг: 0 / 0
15.01.2020, 17:03
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914452
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Basil A. Sidorov
Каждый игрок должен случайно выбирать коробки.
Тривиальный случай - N = 1, вероятность выигрыша равна:
Код: plaintext
1.
2.
1   3   2   1
- = - > - = -
2   6   6   3

Игрок не случайно выбирает коробки, первый - первую, второй -вторую, итоговая вероятность выигрыша 1/2.

PS: единственное что могут сделать игроки - договориться по какому правилу смотреть коробки, для каждого игрока
комната с коробками неизменаа, все изменения сделанные игроком перед входом следующего отменяются, 1-3 пункты да, перестановки коробок будут rollback)).
...
Рейтинг: 0 / 0
15.01.2020, 17:13
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914461
Митя_Ниточкин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Митя_Ниточкин
Гость
Каждому инструкция

Сначало открой коробку под номером равным твоему номеру
Если не угадал открой под номером который открыл
...
Рейтинг: 0 / 0
15.01.2020, 17:31
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914471
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Митя_Ниточкин

Если не угадал открой под номером который открыл

Масло маслянное.
...
Рейтинг: 0 / 0
15.01.2020, 17:37
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914483
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
Митя_Ниточкин

Если не угадал открой под номером который открыл

Масло маслянное.
наверно, подразумевалось то самое, что Шарахов описал ранее.
...
Рейтинг: 0 / 0
15.01.2020, 17:47
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914491
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Господа, задачу считаем решенной.

ответ, как водится, размазан по топику, смотреть 22059496 -> 22059738 -> 22059793

суть: при открывании коробок проходим по перестановочному циклу, тогда вероятность успеха равна вероятности, что в нашей перестановке нет цикла длиной более половины.
...
Рейтинг: 0 / 0
15.01.2020, 17:52
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39914521
Митя_Ниточкин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Митя_Ниточкин
Гость
Не видел что ответ уже написали

По поводу доказательства:
В уме получается 1/3 что больше 0.3

Через час доеду до дома проверю
...
Рейтинг: 0 / 0
15.01.2020, 18:44
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39918126
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Я пропустил самое интересное((
Имя пользователя1
Господа, задачу считаем решенной...
суть: при открывании коробок проходим по перестановочному циклу, тогда вероятность успеха равна вероятности, что в нашей перестановке нет цикла длиной более половины .
Маленькое примечание.
2N обеспечивает не равенство простому числу (кроме 2).
Цикл есть циклическая подгруппа в группе перестановок.
Кол-во элементов в любой подгруппе есть делитель порядка группы (которая ==(2N)! ).
Любая конечная группа разложима в "декартово" произведение "не пересекающихся" циклических подгрупп. Соответственно (2N)! == n1 * n2 * ... nk.

Если цикл >N (т.е. половины), то ... делайте выводы сами.
...
Рейтинг: 0 / 0
23.01.2020, 22:30
| Ответить | Цитировать | Написать  
Задача с коробками (из ветки про тервер)
    #39918136
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Сорри, неточность:
Цикл есть порождает циклическую подгруппу в группе перестановок.
...
Рейтинг: 0 / 0
23.01.2020, 23:41
| Ответить | Цитировать | Написать  
95 сообщений из 95, показаны все 4 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с коробками (из ветки про тервер)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]