ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с коробками (из ветки про тервер)
20 сообщений из 95, страница 4 из 4
  4  все
Задача с коробками (из ветки про тервер)
    #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
| Ответить | Цитировать | Написать  
20 сообщений из 95, страница 4 из 4
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задача с коробками (из ветки про тервер)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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