Да, кстати вот еще к вопросу "разноформенных" фигур.
Головоломки
Сообщений 241 страница 270 из 1117
Поделиться2412014-07-06 19:34:31
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Поделиться2422014-07-06 20:26:33
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Да, кстати вот еще к вопросу "разноформенных" фигур.
Красиво 
Поделиться2432014-07-07 03:34:11
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
А вот та задача, о которой я говорил.
Я ее увидел в постановке от Michal Forisek:
Любопытно.
Немного напоминает задачу о разборчивой невесте, но на первый взгляд сложнее Подумаю
Поделиться2442014-07-07 03:39:34
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Известно, что доля блондинов среди голубоглазых больше, чем доля блондинов среди всех людей. Верно ли, что доля голубоглазых среди блондинов больше, чем доля голубоглазых среди всех людей?
Верно.
Поделиться2452014-07-07 20:51:08
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
А вот та задача, о которой я говорил.
Я ее увидел в постановке от Michal Forisek:Любопытно.
Немного напоминает задачу о разборчивой невесте, но на первый взгляд сложнее
Да, пожалуй, что-то общее есть. Ну и конечно эта задача сложнее - уж как минимум вычислительно.
Поделиться2462014-07-07 20:52:27
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Известно, что доля блондинов среди голубоглазых больше, чем доля блондинов среди всех людей. Верно ли, что доля голубоглазых среди блондинов больше, чем доля голубоглазых среди всех людей?
Верно.
Да, наверное тут лучше было ставить задачу в виде "что больше"
Поделиться2472014-07-08 04:05:02
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Известно, что доля блондинов среди голубоглазых больше, чем доля блондинов среди всех людей. Верно ли, что доля голубоглазых среди блондинов больше, чем доля голубоглазых среди всех людей?
Верно.
Да, наверное тут лучше было ставить задачу в виде "что больше"
Или даже "достаточно ли информации, чтобы сделать вывод, что больше..."
Поделиться2482014-07-08 04:10:30
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
А вот та задача, о которой я говорил.
Я ее увидел в постановке от Michal Forisek:Любопытно.
Немного напоминает задачу о разборчивой невесте, но на первый взгляд сложнее
Да, пожалуй, что-то общее есть. Ну и конечно эта задача сложнее - уж как минимум вычислительно.
Такое ощущение, что эта лотерея в отличии от разборчивой невесты динамическим программированием не решается.
В общем, навскидку идея следующая.
Получаем первое число х1. Поскольку распределение чисел равномерно, то из оставшихся восьми в интервал (0,x1) попадет в среднем (x1*8) чисел. Надо подумать, куда округлить, вверх или вниз, и назвать номер исходя из этого среднего.
Аналогично следует поступать, когда уже известны k чисел. Если уже названная нумерация противоречива, то можно называть номера произвольно, иначе - смотреть матожидания, сколько оставшихся чисел попадет в какой из k+1 промежутков.
Будет время, попробую оценить вероятность выигрыша при таком подходе.
А уж как понимать, какая из стратегий оптимальна с точки зрения вероятности выигрыша, я пока не знаю
Поделиться2492014-07-08 17:24:11
- Перошка :)
- Зарегистрирован: 2013-01-11
- Приглашений: 0
- Сообщений: 46197
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Пол: Женский
- Провел на форуме:
1 день 11 часов - Последний визит:
2019-07-11 20:05:20
Ничего себе вы головоломки загадываете! :17:
Поделиться2502014-07-08 19:42:39
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Такое ощущение, что эта лотерея в отличии от разборчивой невесты динамическим программированием не решается.
Как раз именно динамическим программированием и решается
Поскольку распределение чисел равномерно, то из оставшихся восьми в интервал (0,x1) попадет в среднем (x1*8) чисел. Надо подумать, куда округлить, вверх или вниз, и назвать номер исходя из этого среднего.
Надо же - теперь я понял, как думала харьковская команда, когда решала эту задачу - почему у них был коэффициент N-1 (у всех остальных было разумеется N). Но конечно это не оптимальная стратегия - ни та ни другая.
Поделиться2512014-07-08 20:29:58
- Служба охраны правопорядка
- Зарегистрирован: 2008-10-11
- Приглашений: 0
- Сообщений: 544
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
9 часов 41 минуту - Последний визит:
Вчера 10:26:27
Мы с одним моим другом на третий день наконец-то решили задачу для трёх гномов
Ну публикуй тогда решение - проверим.
Хотя допускаю, что просто мы нашли не оптимальное решение.
Имеешь в виду, что зависимость ответа от увиденного трудно записать в явном виде?
Ещё никто своё решение не опубликовал?
Для трёх гномов выглядит это примерно так:
Логика следующая:
* если гномы видят одинаковые цифры, то
-- первый пишет то что видит,
-- второй пишет на один больше того что видит,
-- третий пишет на два больше того что видит.
* если гномы видят разные цифры, то
-- первый пишет то число что не видит,
-- второй пишет на один больше того числа что не видит,
-- третий пишет на два больше того числа что не видит.
** во всех случаях 4 заменяется на 1, а 5 заменяется на 2.
Поделиться2522014-07-08 20:32:23
- Служба охраны правопорядка
- Зарегистрирован: 2008-10-11
- Приглашений: 0
- Сообщений: 544
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
9 часов 41 минуту - Последний визит:
Вчера 10:26:27
Имеешь в виду, что зависимость ответа от увиденного трудно записать в явном виде?
Записать не трудно. Там везде формулы Excel. Трудно расширить это всё до 17 гномов)))
Поделиться2532014-07-08 21:23:57
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Надо подумать, куда округлить, вверх или вниз, и назвать номер исходя из этого среднего
Ну вверх или вниз точно нелогично - иначе ответ 1 или 9 будет неввозможным (ну кроме крайних случаев). Кажется те ребята округляли к ближайшему целому, а у меня были изначально слишком "добрые" тесты.
Признаюсь, кстати, что я эту задачу в свое время не решил.
Поделиться2542014-07-08 21:39:00
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Записать не трудно. Там везде формулы Excel. Трудно расширить это всё до 17 гномов)))
Проверил - действительно подходит. И решение по значениям совпадает с тем, которое я подразумевал. И еще одна идея правильно поймана - придумать некий инвариант и перебрать от него все возможные смещения.
В общем, круто Наверное, чтобы на общий случай обобщить - возможно стоит понять как выразить одной арифметической формулой (то же самое число для двух одинаковых и недостающее для разных).
Поделиться2552014-07-09 04:12:25
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Ну вверх или вниз точно нелогично
Ну да, это я уже сообразил.
Поделиться2562014-07-09 04:13:26
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Имеешь в виду, что зависимость ответа от увиденного трудно записать в явном виде?
Записать не трудно. Там везде формулы Excel. Трудно расширить это всё до 17 гномов)))
Осталось только упростить запись для трёх гномов (чтобы без условий было), и ее можно обобщать
Поделиться2572014-07-09 04:56:38
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Такое ощущение, что эта лотерея в отличии от разборчивой невесты динамическим программированием не решается.
Как раз именно динамическим программированием и решается
Поскольку распределение чисел равномерно, то из оставшихся восьми в интервал (0,x1) попадет в среднем (x1*8) чисел. Надо подумать, куда округлить, вверх или вниз, и назвать номер исходя из этого среднего.
Надо же - теперь я понял, как думала харьковская команда, когда решала эту задачу - почему у них был коэффициент N-1 (у всех остальных было разумеется N). Но конечно это не оптимальная стратегия - ни та ни другая.
Про динамическое программирование еще подумаю
Так, а если мы будем так делать. Вот выпало число x1. Остальные числа - либо меньше (каждое с вероятностью x1), либо больше (вероятность 1-x1).
Рассматриваем соответствующий ряд Бернулли - известно же наивероятное число успехов для него (за успех считаем, например, попадание в интервал (0,x1)). Если по нему считать?
Хотя, это похоже то же самое и получится
Ладно, пытаемся упростить задачу. Если число всего одно - тут и думать нечего, все уже придумано до нас
Если осталось два числа, и номер предпоследнего (z) не определяется исходя из уже выбранной нумерации, значит, нужно для него выбрать один из двух соседних номеров, скажем 1 или 2 (предполагаем что два оставшихся в интервале (0,x)).
Интуиция подсказывает, что нужно брать номер 2, если z>x/2 и 1 в противном случае. Тогда вероятность угадать правильно (при условии, что уже выбранная нумерация не противоречит загаданной последовательности) будет - пусть z<=x/2 - равна 1-z/x. В худшем случае 1/2, если (z=x/2), но тут уж ничего не поделаешь. От этой 1/2 в худшем случае никуда не уйти, ведь два последних числа могут вообще оказаться равными - а тут только гадать.
В общем, нужно оптимально научиться решать задачу для меньшего размера последовательности. Действительно, динамическое программирование поможет
Поделиться2582014-07-09 21:23:57
- Лидер сопротивления Последняя надежда человечес
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 5467
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
11 часов 24 минуты - Последний визит:
2024-11-09 13:33:59
Рассматриваем соответствующий ряд Бернулли - известно же наивероятное число успехов для него (за успех считаем, например, попадание в интервал (0,x1)). Если по нему считать?
Это правильная идея, только это ведь еще не все, что нужно для полной победы.
Второй подход до конца не смог понять, кажется он дальше от правильного решения, но могу ошибаться.
Два последних числа могут вообще оказаться равными - а тут только гадать
Ну этим точно можно пренебрегать: вероятность того, что какие-то два значения совпадут, - нулевая.
Поделиться2592014-07-10 05:07:04
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Второй подход до конца не смог понять, кажется он дальше от правильного решения, но могу ошибаться.
Ну я его тоже пока до конца не понял
Ну этим точно можно пренебрегать: вероятность того, что какие-то два значения совпадут, - нулевая.
Действительно.
Тогда, по идее, для двух чисел можно хорошую стратегию придумать, типа тоже с генерированием случайного числа Х от 0 до 1 и предположением, что если первое число больше Х, то оно большее из двух. Надо прикинуть, какая вероятность получится...
Это правильная идея, только это ведь еще не все, что нужно для полной победы.
Попробую развить.
Поделиться2602014-07-10 05:11:21
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Да, вот еще задачка, которую пока не знаю, как решить Вчера на нее наткнулся.
48 шариков разложены в 30 коробок так, что в каждой коробке есть хотя бы один шарик. Коробки выставлены в один ряд. Доказать, что в этом ряду найдутся несколько подряд идущих коробок таких, что в них вместе взятых лежит ровно 11 шариков.
Ну есть некоторые идеи по решению, но они какие-то трудоемкие. А мне кажется, что должно быть элегантное красивое короткое решение
Поделиться2612014-07-10 15:28:58
- Служба охраны правопорядка
- Зарегистрирован: 2008-10-11
- Приглашений: 0
- Сообщений: 544
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
9 часов 41 минуту - Последний визит:
Вчера 10:26:27
Проверил - действительно подходит. И решение по значениям совпадает с тем, которое я подразумевал. И еще одна идея правильно поймана - придумать некий инвариант и перебрать от него все возможные смещения.
Имеешь в виду, что зависимость ответа от увиденного трудно записать в явном виде?
Записать не трудно. Там везде формулы Excel. Трудно расширить это всё до 17 гномов)))
Осталось только упростить запись для трёх гномов (чтобы без условий было), и ее можно обобщать
Ну, в общем у меня получилось что:
* первый гном пишет сумму чисел всех остальных гномов.
* второй гном пишет число на первом гноме минус сумму остальных гномов (кроме первого) плюс 1
...и так далее...
* семнадцатый гном пишет число на первом гноме минус сумму остальных гномов (кроме первого) плюс 16
*** везде имеется в виду остаток от деления на 17 и 0 заменяется на 17.
Для всех 827240261886336764177 вариантов не проверял, но пару десятков тысяч вариантов проверил.
Интуитивно кажется, что решение может быть ещё проще, но пока ничего более красивого не нашёл.
Поделиться2622014-07-10 16:16:48
:17:
Поделиться2632014-07-10 17:17:29
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Канадец, решение верное
Ну чтобы было лучше понятно, как оно работает, я бы переформулировал следующим образом.
Каждый гном знает сумму всех чисел, кроме своего.
Пусть первый гном исходит из того, что полная сумма делится на 17.
Второй - что остаток от деления полной суммы на 17 равен 1.
Третий - что 2.
...
Семнадцатый - что 16.
Исходя из этих предположений, каждый однозначно определяет число, которое должен написать. И поскольку ровно одно из этих предположений верно, один из них напишет правильное число.
Твое решение эквивалентно этому, с точностью до перестановки гномов
Поделиться2642014-07-10 17:46:34
- Служба охраны правопорядка
- Зарегистрирован: 2008-10-11
- Приглашений: 0
- Сообщений: 544
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
9 часов 41 минуту - Последний визит:
Вчера 10:26:27
Каждый гном знает сумму всех чисел, кроме своего.
Пусть первый гном исходит из того, что полная сумма делится на 17.
Второй - что остаток от деления полной суммы на 17 равен 1.
Третий - что 2.
...
Семнадцатый - что 16.Исходя из этих предположений, каждый однозначно определяет число, которое должен написать. И поскольку ровно одно из этих предположений верно, один из них напишет правильное число.
Красота
Не подумал посмотреть на эту задачу с такой стороны.
Поделиться2652014-07-10 18:04:03
- Живая сталь
- Откуда: Нижний Новгород
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 3572
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Возраст: 45 [1979-05-30]
- Провел на форуме:
18 часов 12 минут - Последний визит:
2016-05-12 15:03:24
Да, вот еще задачка, которую пока не знаю, как решить
48 шариков разложены в 30 коробок так, что в каждой коробке есть хотя бы один шарик. Коробки выставлены в один ряд. Доказать, что в этом ряду найдутся несколько подряд идущих коробок таких, что в них вместе взятых лежит ровно 11 шариков.
Ну есть некоторые идеи по решению, но они какие-то трудоемкие. А мне кажется, что должно быть элегантное красивое короткое решение
[SPOILER]Х1 – шариков в 1 коробке, х2 – шариков в 1 и 2 коробке, х3 – в 1,2,3 и т.п, х30 с 1 по 30ю коробку.
Шариков в одной коробке не может быть больше 19 (48 шариков разложили по одному в коробки и осталось еще 18, которые можно запихать как угодно в эти же коробки) и не менее 1.
y1=х1+11, y2=x2+11, y3=x3+11,… y30=x30+11.
Числа x1,…, х30 – разные
И у1, … у30 – разные.
Всего их 60. Среди этих 60 чисел, каждое из которых не превосходит 59 (=48+11) найдется два одинаковых по любому.
Напишу индексы в скобках, а то сливаются.
i, k от 1 до 30
Пусть это x(i) и y(k)=x(k)+11.
x(i)=x(k)+11
x(i)-x(k)=11
Значит с k+1 по i коробку будет ровно 11 шариков.[/SPOILER]
Отредактировано Doug (2014-07-10 18:31:38)
Поделиться2662014-07-10 18:11:11
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Любопытно, сейчас посмотрю.
Только у нас наоборот, 30 коробок и 48 шариков...
Поделиться2672014-07-10 18:12:28
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Супер вообще. Как додумалась до такого?
Поделиться2682014-07-10 18:20:33
- Живая сталь
- Откуда: Нижний Новгород
- Зарегистрирован: 2012-06-04
- Приглашений: 0
- Сообщений: 3572
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Возраст: 45 [1979-05-30]
- Провел на форуме:
18 часов 12 минут - Последний визит:
2016-05-12 15:03:24
Любопытно, сейчас посмотрю.
Только у нас наоборот, 30 коробок и 48 шариков...
Ой, да, тогда до 30 )) Сейчас исправлю числа ) Все равно получается, только впритык ))
Супер вообще. Как додумалась до такого?
Очень давно когда-то видела подобную, только не с шариками и не с коробками, но запомнилось решение
upd. Под кат уберу.
Отредактировано Doug (2014-07-10 18:24:18)
Поделиться2692014-07-10 18:26:58
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Сейчас исправлю числа
Еще исправь 30 шариков на 48
Поделиться2702014-07-10 18:27:52
- Зарегистрирован: 2009-08-07
- Приглашений: 0
- Сообщений: 65535
- Уважение: [+0/-0]
- Позитив: [+0/-0]
- Провел на форуме:
1 день 11 часов - Последний визит:
2022-06-17 20:07:42
Очень давно когда-то видела подобную, только не с шариками и не с коробками, но запомнилось решение
Здорово Я бы до такого не догадася, наверное