Форумы-->Форум для внеигровых тем-->
1|2|3|4|5|6|7|8|9|10
| Автор | Математическая задача |
|---|
| Да, так. Но, судя по посту выше, решение для 100 (для 3, думаю, тоже) на порядок проще, не так ли? | для Necrovoin:
Ну да, вон у поста 137 оно почти в 1 строчку поместилось. Правда, если расшифровать его так, чтобы было понятно каждому, оно займет строчек 10. | Если знаете,я могу другую задачку про гномов задать, она на мой взгляд, намного сложнее, чем та.
Конечно знаю, её уже скоро в яслях будут давать. 99 гномов можно спасти точно. Слушаю более сложную (я препод олимпиадной подготовки) | | Про гномиков это пример хорошей интересной задачке,которая порадует детей не особо подготовленных, идеалочка прямо, один недостаток только, её прям вот все знают | для Ути-Пути3:
Более сложная была в посте 120:) Ну, по крайней мере, она намного менее изестная.
я препод олимпиадной подготовки
Тогда, я думаю, у вас тоже найдутся примеры интересных задачек. Требования простые - решение можно описать в посте так, чтобы оно было понятно без рисунка, то есть всякие геомы не подойдут. Задача должна просто решаться с помощью красивой идеи, поэтому тут не все олимпиадные задачки подойдут, так как во многих требуется довольно длинная доработка идеи до конечного решения.
Не думаю, что мне удастся удивить вас какой-то задачкой, потому что я их все воспроизвожу по памяти, сама память ограничена, и в нее, по большей части, попадают задачи, имеющие простое решение, которые вы, в силу своей работы, вероятно знаете наизусть.
Но попробую следующее: (задача связана с геомом, поэтому подробно решение описывать не нужно, только идею):
Дан многогранник, в который вписана сфера. При этом грани покрашены в черный и белый цвета так, что у каждой белой грани - только черные соседи.
Доказать, что:
1)Сумма всех площадей черных граней не меньше, чем белых.
2)Количество черных граней не меньше, чем белых. | для Mystical_Hunter:
Правда, если расшифровать его так, чтобы было понятно каждому, оно займет строчек 10. Плз, расшифруй. Ну и для случая: 2 гнома, 2 цвета. | для Ed_War:
"сумма цветов всех колпаков сравнима со i по модулю 100".
- расшифровывается следующим образом: два целых числа называются сравнимыми по модулю 100, если их разность делится на 100, т.е например, числа
..... -267, -167, -67, 33, 133, 233, 333, ..... все сравнимы друг с другом по модулю 100. Соответственно, если пронумеровать цвета от 0 до 99 и сложить сумму всех 100 цветов, то получится какое-то большое число (ну, например, 5683), но ему соответствует число 83 из диапазона от 0 до 99. Также гномы пронумеруют себя тоже числами от 0 до 99, и гном с номером i будет вычислять свой цвет из предположения, что общая сумма сравнима с i по модулю 100. Например, пусть гном с номером 42 посчитал сумму цветов всех остальных гномов получил 4781. Тогда он должен сказать цвет под номером 61, потому что в таком случае общая сумма цветов будет
4781+61=4842 и ей соответствует 42 из диапазона от 0 до 99. Если его предположение верно, то он назовет как раз свой цвет, иначе - умрет. Теперь возьмем гнома, номер которого совпадает с тем самым числом из диапазона от 0 до 99, которое сравнимо с суммой цветов всех 100 шапок по модулю 100. Именно он и выживет в итоге.
Для двух гномов, соответственно, гном с номером 0 считает, что сумма его цвета и цвета второго гнома сравнима с 0 по модулю 2 (четная). То есть если на втором гноме шапка цвета 0, то он также должен назвать 0, если 1 - он должен назвать 1.
Это как раз тот гном, который называет цвет шапки другого.
Гном с номером 1 считает, что сумма его цвета и цвета второго гнома равна 1, то есть если на втором гноме 1, то он должен сказать 0, если 0 - то 1. Это тот гном, который говорит противоположный цвет. | | Ничего себе. А обоснование решения можно? А то похоже на рандомное пальцем в небо. | для Necrovoin:
В смысле? Сумма всех цветов имеет какой-то остаток от 0 до 99 при делении на 100.
Гном с номером i предполагает, что этот остаток равен i и, зная цвета остальных, вычисляет цвет своей шапки. Ровно один из гномов окажется прав и выживет. | | Не въезжаю. Почему именно I? Почему бы не предположить, что остаток должен быть равен i+29, или, например, 10? И с чего бы один окажется прав? Я не спорю, что ответ верный, но разъясняете вы его не очень. | И с чего бы один окажется прав?
Потому что сумма всех 100 цветов имеет какой-то из остатков от 0 до 99, и каждый гном "берет на себя" один из этих остатков. В моем варианте - каждый просто считает, что остаток равен номеру самого гнома, но можно и по-другому, это не принципиально. Важно только, чтобы все гномы "закрывали" разные остатки. | для Mystical_Hunter:
Важно только, чтобы все гномы "закрывали" разные остатки.
Это легко, достаточно всем написать свой номер. Проблема в том, что хотя бы один гном должен угадать свой колпак. Ваш алгоритм работает, но вот строгое его доказательство не приведено и вряд ли уложится в 10 строк) | для Mystical_Hunter:
как же вы ужасно излагаете решение (без обид)
Посто 147 на русском языке. Обозначим n - число цветов на гномах (оно написано где-то в условии).И ставим цветам в соответствие остатки при делении на n (от 0 до n-1). 100 гном смотрит сумму номеров цветов на первых 99, берет от неё остаток при делении на n и называет цвет с таким номером (если он не совпадет с цветом 100, то 100 умрет, но за идею, все равно никак точно угадать не мог, он первый говорит). Следующий знает сумму остатков на всех гномах включая себя (её назвал ему 100), и знает на первых 98 (он их видит). вычитает из 1 числа второе, получает остаток для своего цвета. Дальше аналогично, остальные спаслись. Геому гляну не видел. Задачка от Ути (была на собеседовании в Яндекс, математическом форт Байярде, там её не решили, а задача изи). Поймали двух крутых математиков и посадили в две далекие камеры без возможности общаться. Затем бесконечное число раз подбросили обычную монетку и сообщили первому исходы всех нечетных бросков а второму - всех четных (в больном воображении любителей классической математики такое возможно на изи). Затем первый называет любой какой хочет четный номер, а второй - любой нечетный номер. Если результаты бросков с выбранными номерами совпадают, их отпускают, иначе казнят. Математики знали заранее, что их ждет (не знали только сами исходы) и могли предварительно договориться. Как им следует действовать, чтобы выйти на свободу с вероятностью строго большей 50%? | | А так вообще если чего-то хочется, то ли револиции, то ли решить абы какую задачку (возможно интересную), заходите на сайт diofant.ru и решайте. | для Ed_War:
Важно только, чтобы все гномы "закрывали" разные остатки.
Имелось в виду, остатки от деления суммы цветов всех колпаков на 100.
но вот строгое его доказательство не приведено
В каком это месте доказательство не строгое? Просто в посте 147 я пыталась дополнительно пояснять на примерах. А если кратко резюмировать, то получится:
Если сумма всех цветов имеет остаток i (от 0 до 99) при делении на 100, то гном с номером i (такой точно найдется, потому что номера гномов покрывают ВСЕ значения из диапазона от 0 до 99), согласно нашей стратегии,
будет вычислять свой цвет из предположения, что общая сумма сравнима с i по модулю 100. (имеет остаток i при делении на 100). Так как в его случае это предположение верно, то и цвет своего колпака он тоже вычислит верно и победит. | | всё, я понял, там про другую задачу писали, сори) | для Ути-Пути3:
153+ Это решение первой задачи про гномов (когда он стоят в колонну). Мы уже вторую давным-давно обсуждаем (ее условие в посте 120). И пост 147 тоже про нее. | | Вот теперь пост 147 на русском языке. Сумма остатков номеров вскех 100 гномов может принимать значения от 0 до 99 (сумма имеется в виду по модулю 100). Чтобы получить свой номер гном должен из этой неизвестной суммы S вычесть сумму остатков номеров цыетов остальных 99 гномов, которые он видит. Они договорились, что 1 гном считает, что S=0 второй, что S=1 и так далее. 100 что S=99. Ровно 1 из них прав, он и выживет. | | в посте 158 имелось в виду, как и в предыдущей задаче, нумеруем цыета от 0 до 99. Свой номер следует понимать как остаток соответствующий его цвету | сумма имеется в виду по модулю 100
Я в основном там это и объясняла в том числе и на примерах. Не все здесь владеют терминологией и решали когда-либо задачи на остатки. |
1|2|3|4|5|6|7|8|9|10К списку тем
|
