Доброго дня, всем любителям математики! Представляю вашему вниманию еще три интересные, на мой взгляд, логические задачи. Первая часть находится здесь. Спасибо всем, кто участвовал в обсуждениях и находил неточности! Итак,
Путник взбирается на высокую гору по тропе как по серпантину. На это ему необходим весь день с утра до вечера, с учетом времени на отдых и перекусы. На вершине горы находится жилище. Путник, добравшись до него, проводит в нем ночь и на следующий день с утра отправляется в обратный путь. Он также шел до вечера. Вопрос – есть ли на этом пути точка, в которой путник находился в одно и то же время дня когда поднимался и когда спускался обратно?
Наложим график функции зависимости координаты путника от времени дня в первый и второй день. Эти графики пересекутся в искомой точке.
Трем приятелям нужно разделить ножом кусок масла на троих таким образом, чтобы каждый из приятелей посчитал, что получил как минимум одну треть от общего количества. Как им следует поступить?
Рассмотрим случай, когда приятелей двое. Тогда любой из них делит масло на две части таким образом, чтобы для него самого эти части казались равнозначными. Затем второй приятель забирает кусок, который на его взгляд не меньше одной второй. Задача решена.
При добавлении третьего приятеля начинаем решать задачу с того момента, когда была решена предыдущая. Каждый приятель делит свой кусок масла на три части так, чтобы, как и в предыдущем случае, для него эти части казались равнозначными. Затем третий приятель берет у каждого по одному наиболее понравившемуся кусочку. Таким образом, с его точки зрения, он получит как минимум одну треть с каждой половинки. А это как минимум одна треть от целого. Действительно, сложим одну треть от первой половины и одну треть от второй, вынесем за скобки одну треть и в скобках получим сумму половинок, то есть целое.
100 преступников отбывают наказание в тюрьме с пожизненным сроком, каждый в отдельной камере. Однажды от начальства тюрьмы каждому из них поступило предложение – всех их освободят, если они смогут выполнить следующее задание.
В пустующей камере есть лампочка с выключателем, свет выключен. В случайный день в нее будут запускать случайного заключенного, и он сможет либо включить, либо выключить лампочку, либо вообще не трогать выключатель. Этот процесс будет продолжаться до тех пор, пока один из заключенных не скажет, что точно знает, что все заключенные побывали в этой камере хотя бы один раз (а это однажды обязательно произойдет, притом за этот период некоторые заключенные могут побывать в камере не один раз). Заключенным разрешено встретиться и придумать стратегию, но только один раз до начала испытания. Как им следует поступить? Для удобства примем, что заключенные и надзиратели бессмертны.
Заключенным нужно выбрать того, кто будет заходить в камеру и выключать свет каждый раз, когда он будет гореть, а всем остальным - включать свет, если он не горит при первом или очередном посещении камеры и не трогать его при последующих. Тогда тот заключенный, который выключает свет, сможет точно определить, что все остальные посетили камеру, когда выключит свет девяносто девять раз.
Комментарии (22)
axion-1
18.11.2025 13:47а всем остальным включать свет при первом посещении камеры
Только если он там уже не горит.
Включать свет один раз, при условии что он был выключен. При всех остальных посещениях, до и после, ничего не трогать.
artptr86
18.11.2025 13:47Задача про путника сформулирована некорректно. Вопрос звучит как: «есть ли на этом пути точка, в которой путник находился в одно и то же время дня когда поднимался и когда спускался обратно?». Подразумевается, что либо такая точка есть, либо её нет.
Наложение графиков — не ответ, а может быть одним из способов решения, но для этого нужно иметь сам график. Про него в условии не сказано ни слова. Если бы было сказано что-то в стиле: «Путник постоянно отмечает на графике текущее время по оси X и расстояние от подножия горы по оси Y. Если существует точка, в которой он побывал в одно и то же время, то как её найти?», то она имела бы смысл. Однако в данной формулировке решается она тривиально.
Иначе и вторую задачу легко решить: просто возьмём весы и поделим масло на три равных по массе кусочка.
kipar
18.11.2025 13:47но нам не нужно найти точку, нужно доказать что она есть. Хотя с графиками действительно формулировка стремная, надо было теорему Больцано-Коши использовать.
qwe101
18.11.2025 13:47теоремы - это хорошо, но: совместим оба дня. Один поднимается, другой спускается. Где-то они встретятся.
Alexandroppolus
18.11.2025 13:47Задача про камеру и лампочку здесь дана в самом базовом варианте. У нее есть разные усложнения. Например, игрокам неизвестно, в каком состоянии лампочка на старте. Тогда все, кроме счётчика, зажигают свет два раза, а счётчик говорит, что все побывали, когда досчитает до 197.
Akina
18.11.2025 13:47Задача о трёх приятелях.
В решении есть такая фраза: "Каждый приятель делит свой кусок масла на три части так, чтобы, как и в предыдущем случае, для него эти части казались равнозначными." По условию задачи кусок масла - ОДИН. Соответственно вопрос - как определить, кто что делает? Кто делит этот один кусок на две части? Кто определяет, какой кусок кому отдать для дальнейших операций, и кто будет выбирать по трети от каждого куска? И откуда такая уверенность, что каждый согласен как с тем, какую ему отвели роль на каждом этапе, так и с тем, как кто-то другой выполнил каждую из этих операций? Ведь нет никакой гарантии, что двое других и вправду поделят свои куски на абсолютно равные части - и, следовательно, тот, кто "берет у каждого по одному наиболее понравившемуся кусочку", находится в наиболее выигрышном положении.
На самом деле самая большая проблема при решения задачи именно в этом - выборе, кому, когда и что делать, ведь доверие полностью отсутствует. Любая элементарная операция над куском масла (разрезание) или его частью (выбор) выполняется только одним из троих. Но доверие к выбору того, кто именно выполнит операцию и как именно он её выполнит, у двух других - нет.
Но если не заморачиваться на выбор того, кто и что делает, и считать, что любой выбор определяет жребий/кубик/ВКР, а также что никто и никому не подыгрывает, то возможны и другие варианты. Например - первый делит кусок на три части, второй определяет, какой кусок достанется первому, потом остаток собирается обратно в один кусок, и всё повторяется - второй делит, третий определяет, какой кусок достанется второму. Такой алгоритм достаточно прост и легко расширяем. Справедливость деления упирается лишь в то, насколько каждый способен максимально поровну поделить кусок. Но в этом случае вина за получение куска меньше, чем при абсолютно ровном делении - целиком его вина, и поводов для обиды нет. А на ВКР обижаться бессмысленно.
Alexandroppolus
18.11.2025 13:47В вашем варианте возможен сговор между первым и вторым, когда первому достанется кусок более 1/3. Потом второй и третий поделят остаток поровну, а уже после первый и второй тайком поделят поровну свои части и будут иметь более 1/3 на нос.
А вот предложенный автором вариант не допускает сговора, и там без разницы, каким по счету быть.
нет никакой гарантии, что двое других и вправду поделят свои куски на абсолютно равные части
Главное, что эти части будут равные с их точки зрения, то есть никаких претензий они предъявить не смогут
Akina
18.11.2025 13:47А вот предложенный автором вариант не допускает сговора
Да щазз! Первый сговаривается со вторым, второй при делении своего куска делит не на три по 1/3, а один заведомо больше остальных. Первый выбирает его, профит пополам.
Но главное не это. Задача имеет смысл только при условии что никто никому ни на сколько не доверяет, то есть никаких договорённостей априори не может быть. Иначе это просто обязано быть описанным в условии явно.
kipar
18.11.2025 13:47Первый выбирает его, профит пополам.
вот только после деления на три куска забирает оттуда понравившийся не первый а третий.
В целом в варианте автора честность дележа обеспечивается без доверия - если кто-то поделил неровно, то другой сможет выбрать кусок побольше, но "виноват" в этом тот кто делил, считается что раз уж он поделил то считает куски ровными и готов получить любой из них.Ну и да. В детстве у нас с братом и сестрой эта задача возникала постоянно. Мы делили всё подряд (правда были воспитаны так что каждый старался получить часть не побольше а поменьше, но суть не меняется). До приведенного решения мы не догадались (да и делить на шесть частей не всегда удобно), поэтому придумали особый протокол. Один делит на три части двое других на счет "три" указывают на понравившуюся. Если выбрали одну и ту же - повторяют, нельзя указывать на одну и ту же больше двух раз подряд, если за три попытки не пришли к согласию значит первый поделил не очень и он дорабатывает дележ. Была еще модификация про случай когда "дележ очевиден" (скажем три апельсина по-другому не поделить) - там трое указывают на счет три (и тоже нельзя указывать подряд на одну и ту же больше двух раз подряд, что открывает возможность для маневров), ну и доп.правило что в случае мороженого или подобных вещей облизывание бумажки достается тому кто делил за его труд. Учитывая все это, я как эксперт в вопросе дележа на троих подтверждаю - вариант автора вполне честный.
Akina
18.11.2025 13:47вот только после деления на три куска забирает оттуда понравившийся не первый а третий.
Господи, ну второй сговаривается с третьим, какая разница-то? Или третий, если не дурак, по отдельности сговаривается с каждым из первых двух (да потом ещё и кидает их)...
Не это главное. Главный вопрос - кто, на каком основании и по какому принципу, выбирает, кто в приведённом решении "для троих" выбирает, кто будет этим третьим. Для двоих ситуация абсолютно симметрична (даже первоначальное деление на две части не обязано быть ровным), но вот для троих такой симметрии уже нет. То есть индукция не вытанцовывается...
Alexandroppolus
18.11.2025 13:47ну второй сговаривается с третьим
А толку? Здесь при любом сговоре оставшийся участник своими усилиями обеспечивает себе 1/3, и никому, кроме себя, потом не сможет предъявить претензии. Это и требуется от решения.
У вас, если второй отдаст первому более 1/3, или третьему покажется, что у первого более 1/3, то третий участник ничего с этим поделать не может и будет недоволен результатом
Akina
18.11.2025 13:47Ну, может, вы всё же ответите на вопрос - почему вы считаете, что нет разницы, кто будет этим третьим, выбирающим по одному куску из каждой половинки, поделенной на три части? Повторю - решение для двоих справедливо, потому что симметрично, а у решения для троих такого свойства нет (а точнее, сам переход от двоих к троим несимметричен), и я как-то не вижу предпосылок к тому, чтобы считать его обоснованным.
Решение для двоих справедливо, потому что каждый считает, что оставшаяся из двух сделанных им частей в точности равна забранной другим, а забранная им часть, сделанная другим, не меньше, то есть каждый уверен, что он получил не меньше половины исходного куска. А вот аналогичного рассуждения для троих я не вижу. Первый не может быть уверен, что часть, отделённая вторым и потом забранная третьим, не превышает оставленные третьим две части - то есть у него НЕТ уверенности, что его доля не меньше, чем у кого-то другого.
Alexandroppolus
18.11.2025 13:47у него НЕТ уверенности, что его доля не меньше, чем у кого-то другого
Ему нужна только уверенность, что его доля не меньше 1/3 от всего куска. Распределение оставшихся 2/3 его никак не волнует и никак от него не зависит, потому что сразу после дележки один из тех двоих может просто отдать свою долю другому
Akina
18.11.2025 13:47Ему нужна только уверенность, что его доля не меньше 1/3 от всего куска.
Вот именно этого я и не наблюдаю.
С моей точки зрения каждый из троих думает так: остальные двое сговорились, и сделают так, чтобы я получил как можно меньше, а профит поделят. Так вот - решение должно гарантировать, что даже если это так, то всё равно он получит треть, потому что решение таково, что любой договор остальных двух о неравномерности деления даст третьему кусок бОльший, чем одна треть, и только абсолютно точное деление даст ему ровно треть.
kipar
18.11.2025 13:47Допустим сговорились первый и второй. как бы они не делили куски,третий возьмет две понравившиеся половины и они будут не меньше 1/3.
Допустим сговорились первый и третий. Как бы не поделил первый, второй возьмет понравившийся кусок и соответственно он будет не меньше половины. Дальше САМ второй делит свой кусок на три части чтобы третий забрал треть, соответственно если сам он делит нормально то останется не меньше чем с 2/3 * 1/2 = 1/3.
Допустим сговорились второй и третий. Продолжать?Akina
18.11.2025 13:47Допустим сговорились первый и третий. Как бы не поделил первый, второй возьмет понравившийся кусок и соответственно он будет не меньше половины.
Кусок - 6 кг. Первый и третий сговорились. Кусок поделен на два по 3 кг. Второй делит наивно по 1 кг. Первый делит на 1 г + 1 г + 2998 г. Третий берёт из его дележа большой кусок. Второй по итогу - в пролёте, ему достанется всего 1001 г.
Продолжать?
Угу...
Alexandroppolus
18.11.2025 13:47каждый из троих думает так: остальные двое сговорились, и сделают так, чтобы я получил как можно меньше, а профит поделят. Так вот - решение должно гарантировать, что даже если это так, то всё равно он получит треть
Согласен
потому что решение таково, что любой договор остальных двух о неравномерности деления даст третьему кусок бОльший, чем одна треть
Вовсе необязательно. Может оказаться, что участники сговора поделили криво, а третий игрок получил ровно 1/3. Главное, что они не могут сговориться так, чтобы ему досталось менее 1/3
Daemonis
Что если несколько заключенных зашли в камеру перед этим заключенным и больше никогда туда не зайдут?
Vorchun
Хорошо подмечено, ибо по условиям задачи:
Т.е. 99 выключений явно не равно количеству уникальных.
hohlov06
Вероятно надо доработать условие для тех, кто включает свет - единственный раз включать свет, когда свет выключен, а не просто при первом посещении. Тогда счётчик дойдёт до 99