Двое и монета. Как поделить поровну то, что не делится
Всем привет! С вами Георгий Вольфсон, это реальная математика на канале QWERTY. Я рад, что вам понравились, судя по вашим реакциям, наши рассуждения про дележку. И сегодня мы продолжим подобные же вещи, но на другом уже примере.
Пример тоже достаточно классический, если говорить про первую часть, но дальше, я думаю, у вас ждут некоторые открытия. Итак, предположим, что два пирата нашли какой-то клад. Возможно, просто ограбили, возможно, выкопали, не знаем. Но клад такой разнородный, то есть там есть драгоценные камни, монеты и перстни, что угодно. И вот его надо как-то поровну поделить. Как вы понимаете, это сделать очень трудно, потому что каждому будет казаться, что другому больше досталось.
Как это сделать по-честному? Вы можете поставить на паузу и попробовать придумать соответствующий алгоритм. Разумеется, я буду учитывать ряд допущений. Одно из моих допущений таково: во-первых, каждый пират по-своему может поделить его поровну, то есть ему будет казаться, что он поделил поровну, и, во-вторых, что клад можно поделить на любое количество частей в любой момент.
Понятно, что это допущение не работает, если весь клад состоит из одного огромного алмаза. Вы не можете его поделить на две части, но всё-таки мы предполагаем, что клад такой, что его можно делить на сколько угодно частей, чтобы на эту тему не париться. Итак, как в таком случае поступить?
Классический алгоритм таков: предположим, что первый пират разделил клад так, как ему кажется, поровну: половинка, ещё половинка. Но понятно, если второй тоже согласен, что это по уровню, всё хорошо. Если второй считает, что это не поровну, то у второго можно спросить: "Родной, а вот какая половина тебе кажется больше?" Например, сейчас все учителя математики задались вопросом, как половина может быть большей.
Имеется в виду половина того, что первый. Допустим, второй пират говорит: "Вот здесь вот больше". Ну хорошо, тогда ему можно отдать эту часть, потому что первый-то считает, что он поделил строго пополам, значит, он не в обиде. Он получит просто другую половину, а второй тоже не в обиде, потому что он считает, что он получил даже больше половины. Всё, значит, мы поделили.
Вот такой вот классный алгоритм! Заметьте, что в принципе этот алгоритм работает и на практике. То есть, если у вас есть, например, какой-нибудь кусок мяса, который вы хотите поделить между детьми, и они потом обязательно спорят, что вот ему достался больший кусок, ему достался меньший и так далее, то вы можете им предложить тот же алгоритм: что один режет, как ему кажется, пополам, но другой первым выбирает себе часть.
Тогда точно тот, кто режет, не может быть недоволен, что он резал честно пополам. Тут уж называется: сам виноват, если что. А другой не может быть, опять же, недоволен, потому что ему предоставили право выбора. Конечно, умные дети тогда понимают, что лучше выбирать, чем резать, потому что, если резал криво, то второй возьмёт сильно больший кусок, но это уже детали. Пока же подумаем вот о чем: а что делать, если этих самых разбойников было бы трое?
То есть у нас есть всё тот же клад, но у нас есть три разбойника: 1, 2, 3, и надо попытаться разделить поровну между ними. Вот это уже гораздо более хитрая задача. Даже если вы знаете принцип для двоих, всё равно поставьте на паузу и попробуйте над этим подумать. Некоторые думают сутками, потом таки придумывают правильный алгоритм и очень радуются. Так что вот подумайте сами, а потом уже послушайте мои рассуждения.
Что обычно предлагают люди, когда слышат задачу про трёх пиратов? Первый делит на три, как ему кажется, равные части. С точки зрения 1 это одна треть, одна треть, одна треть. Дальше он должен второму и третьему предоставить выбрать. Но если сначала выберет 2, а потом выберет 3, и дальше только 1 будет, это честный алгоритм или нет?
Вообще говоря, нет, потому что может быть и второй, и третий считают, что вот эта вот часть, она самая большая. И тогда, если второй заберёт, то третий будет чувствовать себя обиженным. Ну допустим, он считает, что вот здесь, там не знаю, одна десятая, здесь одна десятая, а здесь восемь десятых по мнению и 2, и 3. Тогда получится, что 2 забрал 80%, а третий считает: "А мне не досталось — в 1 десятая". Всё плохо, я недоволен.
Таким образом, этот алгоритм не пройдет. Можно попытаться тогда спросить 2 и 3: "Ребят, а какая часть для вас самая маленькая?" Напротив. И тогда, если вот эта самая маленькая по мнению 2 и 3 совпадает, допустим, вот она, то первый забирает. Он получил как минимум одну треть. Все довольны!
Но вот беда, может оказаться так, что вот тут-то как раз они будут считать, что самые маленькие — это разные части. Кто-то считает, что первый, кто-то считает, что второй. Как же с этим побороться? Прежде всего, давайте введём такие обозначения: k1, k2 и k3 — кусок первый, кусок второй, кусок третий. Мы предполагаем, что и 2 и 3 считают один из этих кусочков самым большим. Давайте назовем его a. Это для них самый большой.
Первый самый плохой для них должен быть разный. Что давайте, самый плохой для второго будет k3, со средней k2, а 3 наоборот. Тогда что мы делаем? Каждый кусочек мы поделим пополам. Сделаем это хитро: первый кусочек пополам делит второй товарищ и предлагает выбрать третьему. Тогда третий получит хотя бы половинку, здесь мы будем смотреть, сколько они получат. Половинку k1 второй получит ровно половинку k1, потому что он поделил пополам.
Второй кусочек снова 2 делит пополам, только на этот раз предлагает первому. Первому выбрать лучше, тогда первый получит как минимум половинку от k2, а второй получит ровно половинку от k2. Наконец, третий кусочек делит 3 тот, который считает что средний, и тогда опять же 1 выбирает, и он получит как минимум половинку от k3, а третий получает ровно половинку от k3.
Ну а теперь давайте посмотрим, что же у нас получилось. Я утверждаю, что каждый из них доволен, то есть получил как минимум треть от общего количества. Почему?
Первый получил как минимум половину от k2 и как минимум половину от k3, а напомним, с точки зрения 1 он делил ровно на три равные части. Значит, в первом случае он получил как минимум одну шестую, половинку от 3, и во втором случае, как минимум, одну шестую. Вместе он получает хотя бы одну треть всего клада. Значит, он доволен, он получил хотя бы одну треть.
Второй получил половинку от k1 и половинку от k2. Заметим, что тогда у второго будет 1/2 от k1 плюс k2. При этом он считает k3 самой худшей частью, значит, k3 для него не превосходит одной трети от всего общего клада. Но тогда k1 плюс k2 — это как минимум две трети на случай, если мы одну треть берём или даже меньше, то останется хотя бы две трети. Здесь вот хотя бы две трети.
Если эти две трети умножаю на одну вторую, я получаю хотя бы одну треть, значит, 2 доволен. Ну а третий он тоже доволен, потому что он получил как минимум половину от k1 и половину от k3. Но для него k1 и k3 — это лучшее 2 из 3 частей. Значит, опять же, он получает как минимум половину от двух третей клада, то есть это тоже хотя бы одна треть клада. Все, победа, значит, каждый доволен.
Обратите внимание, некоторые, может быть, удивятся, как же так, что каждый получил хотя бы одну треть, может быть, даже больше? Ведь в сумме один клад! Но не забудьте, что они оценивают эти части по-разному. То есть первый сказал, что он получил одну треть или больше по-своему, то есть он по-своему считает эту одну треть. 2 — по-своему, а третий — по-своему.
Посмотрим на ценность, может быть, разное, если, например, ну предположим, да, там есть бриллиант, рубин и тапас. Для кого-то бриллиант самый ценный, для кого-то рубин, для кого-то тапас. И каждый может оценивать свой камень в половину всего клада. Так что каждый получит как бы по половине, вроде бы, да, но со своей точки зрения.
Хорошо, мы не без труда, но справились, если разбойников 3. А если их 4, если 10, если 100 — это ещё более трудная задача. То есть попытаться сформулировать алгоритм, который будет работать для любого количества разбойников. Попробуйте поставить на паузу и придумать это, хотя это, конечно же, гораздо более трудная задача. Но и с ними справимся.
На самом деле, такой алгоритм, конечно, не единственный. Я предложу лишь один из вариантов, но думаю, он вам понравится. Логика такая: вот, допустим, для определенности у меня будет 100 разбойников. Первому разбойнику я говорю: "Отдели одну сотую от всего клада". Он что-то такое отделит. Теперь я спрошу 2: "Как ты считаешь, не много ли он себе взял? То есть эта одна сотая или может быть ты считаешь, что больше?"
Если он считает, что всё нормально, что это 1/100, или может быть даже меньше, он не против того, чтобы 1 взял себе такую долю. Он скажет: "Нормально, согласен!". Но если он считает, что первый взял всё слишком много, я ему говорю: "Родной, хорошо, тогда убери лишнее, чтобы осталось ровно одна сотая".
Тогда заметьте, что 2 оставит одну сотую, по своей версии тоже будет от 1/100 оклада. По версии уже 2, а первый обижен не будет, если 2 заберет этот кусочек, потому что по мнению 1 там была одна сотая, а стала только меньше. 2 ничего не докладывает, возможно, убирает.
Хорошо, тогда я спрашиваю 3: "А вот сейчас ты как считаешь: это одна сотая или возможно больше?" Если он согласен, его пропускаем. Если он не согласен, то считает, что больше, я говорю: "Убери, чтобы осталось ровно 1/100". То есть каждый раз у меня эта доля, которой мы выделяем, либо остаётся неизменной, либо уменьшается.
И так мы доходим до последнего 100 пирата. Всё, теперь я смотрю на последнего пирата, который что-то убирал. Вот, допустим, это был 75 пират. Вот он убрал по одной сотой по его версии, а все остальные согласились, что да, это одна сотая, возможно, даже меньше. Понять, что никому другому я предложить эту одну сотую не могу, то есть возможно, остальные считают, что их определят, если им дадут это. Но конкретно вот этот пират явно должен быть доволен, потому что он последний делил и он считает, что это одна сотая.
При этом остальные тоже должны быть этим довольны, потому что он забрал с их точки зрения меньше, чем одну сотую или меньше либо равно. Возможно, кого-то стоит ровно. Значит, после этого мы отдали вот этому пирату одну сотую, осталось как минимум 99 сотых клада по мнению каждого из оставшихся пиратов.
Дальше мы решаем аналогичную задачу, но для 99 пиратов, то есть первый отделяет одну 99 от того, что здесь есть, второй либо соглашается, либо уменьшает до своей 1/99 и так далее. И соответственно тот пират, который в итоге получит эту долю, он получит одну девяносто девятую от как минимум 99 сотых. Нужно, чтобы он получил как минимум одну сотую.
Перемножаем, значит, так мы сможем осчастливить каждого оператора. Вот такой вот крутой алгоритм! Из минусов: он довольно долго работает. Представьте себе, в первом случае мне нужно опросить 100 человек, и каждый, возможно, делает какие-то действия с кладом. Во втором случае 99 человек, в третьем 98 и так далее, долго-долго.
Есть забавная, такая, не то чтобы обобщение, большой уход в сторону: что делать, если, например, вместо клада будет бутылка вина? И мы хотим её разделить поровну между, ну скажем, давайте не 100, всё-таки пиратов на одну бутылку. Допустим, их будет трое, чтобы задача была примерно классической. Хоть быть третьим можно.
Что тогда делать, особенно если объём не делится на 3? Ну, например, 0.7 такая вот бутылка популярная 0.5. Предположим, что опять же каждый пират точно знает, как с его точки зрения отмерить любую часть от этой бутылки, но эта точка зрения может не совпадать другим пиратам.
То есть треть, по мнению одного, может не являться третью по мнению другого. Тогда смотрите, что можно сделать: берём бутылку и медленно-медленно наливаем в бокал. И как только хоть один пират считает, что набралось одна треть, он хлопает в ладоши или как-то по-другому останавливает процесс.
Тогда смотрите: вот если какой-то остановил и будет считать, что именно вы перестали наливать, то по мнению этого пирата накопилось ровно одна треть. А по мнению остальных — меньше, ну меньше либо равно. Сколько не аббат, сразу хлопнуть не важно, потому что иначе они хлопнули бы раньше.
Если бы они считали, что это больше, чем одна треть, они бы до этого уже хлопнули, а так как никто не хлопал, значит, вот эту одну треть можно отдать тому пирату, который хлопнул. Поесть остальным мы с ними работаем точно так же, то есть наливаем, пока кто-нибудь один не хлопнет, что вот ещё одну треть ему в бокал.
Как только кто-то хлопнул, отдаем ему оставшуюся, остальные довольны. Заметьте, что эта идея обобщается тоже для любого количества пиратов. Хотя, конечно, отложить одну десятую бутылки или, ещё хуже, одну сотую — это чуть сложнее.
Направьте из интересных замечаний, можно осознать еще и вот что: а что делать, если всё-таки мы не можем поровну разделить наш клад? То есть, допустим, у нас есть три каких-нибудь драгоценных камня, примерно одинаковых. Вот как мы их на две равные части поделим? Тот, кто делит, заведомо проигрывает.
Но здесь можно попытаться сделать чуть хитрее: каждый драгоценный камень попытаться просто оценить, сколько он стоит по мнению каждого из пиратов. Ну и, соответственно, это можно делать, договариваясь как-то, договорившись о цене, и потом недостающую половину просто стоимости кто-то компенсирует.
Либо есть ещё один забавный способ, я его вычитывал недавно один довольно известный математик пользуется, насколько мне известно, по крайней мере, когда ходит за покупками, особенно в других странах. Представьте себе, что есть покупатель, есть продавец, есть некий товар, который покупатель хотел бы купить, но в принципе может и не покупать.
Продавец всего хотел бы продать, в принципе, тоже может и не продавать. Дальше вопрос о цене. Каждый берёт бумажку и пишет свою цену: покупатель, допустим, цену a, а продавец — цену b. Дальше происходит следующее: если цена покупателя a меньше, чем цена b, то на всякий случай оговоримся, что покупатель пишет максимальную цену, которую он хочет заплатить за этот товар, за которую готов заплатить, а продавец — минимальную цену, за которую он продаст.
Так вот, если a меньше b, тогда просто сделка не состоится. Но если a больше либо равно b, то сделка состоится, и в качестве цены итоговой можно взять просто среднее арифметическое a плюс b пополам. То есть, если покупатель очень заинтересован и готов купить какую-то вещь, например, за 10 долларов, а продавец в принципе мог бы продать и за 6, ну будет нечестно, если покупатель отдаст 10. Это максимум, а продавец, в принципе, и на 6 был согласен.
Поэтому как раз — не нашим, не вашим — сделка может состояться за 8. Можете попробовать как-нибудь по использовать этот способ на практике. Если вы сейчас где-нибудь отдыхаете, то потом напишите, работает это в вашем случае или нет.
А в заключении такая слегка детская задачка, я её предлагаю обычно в седьмом классе на уроках геометрии. Представьте себе, что у вас есть полный стакан с водой, и вам нужно оставить в нём ровно половину стакана. Будем считать он такой цилиндрический. Можете рассмотреть удачу для бочки, в которой есть вода, тоже цилиндрическое. Вот надо ровно половину отмерить. Как это сделать?
Поставьте на паузу, можете попытаться предложить свои идеи. Я слышал очень разные версии, но классическое решение выглядит так: что нужно выливать воду из бокала и смотреть туда. И если в какой-то момент, если вы аккуратненько наклоняете, у вас вот эта линия уровня воды, на ней окажется край бокала, понятно, что вы выливаете, и покажется край дна. То вот именно в этот момент и будет половина.
Почему? Я думаю, что многие из вас могут догадаться сами, особенно те, кто представляет себе, что такое сечение цилиндра. Ну а мы на этом заканчиваем. Не забывайте оценивать лайком, если вам понравилось, или дизлайком, если нет. Подписывайтесь на наш канал и надеюсь, что увидимся с вами в новых выпусках. Пока-пока!
[Музыка]
[Музыка]