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