?

Log in

No account? Create an account

Previous Entry | Next Entry

Задачка в стиле Кнопа

В детстве придумала задачку, решение которой не могу найти до сих пор.

Дано: четыре человека, выйдя из дома пятого, поймали такси. Таксист развозит их по домам по очереди, он знает дорогу, так что повезет оптимальным маршрутом. Оплата такси осуществляется по счетчику, но сколько будет на счетчике денег в любой момент поездки водитель предсказать не может. Все пассажиры живут на разном расстоянии от места посадки и друг от друга, но никакие два пассажира не живут настолько близко, чтобы выйти вместе, а потом пойти по домам пешком.

Вопрос: Как им по-честному разделить плату за проезд? Естественно, выйдя из такси, пассажир больше не участвует в оплате проезда, то есть заплатить потом еще немного, или отдать деньги другому пассажиру он уже не сможет.

Пока я это писала, Лев придумал решение, кажется, напоминающее правильное. Но не знаю, может, есть и лучше.
promo fridka may 2, 2014 16:20 2
Buy for 40 tokens
Если вы любите порошки и пирожки, но при этом не читаете журнал taffy729, то вы пропускаете очень много прекрасного!

Comments

( 40 comments — Leave a comment )
poslan_za_elkoy
Sep. 17th, 2009 06:00 pm (UTC)
Я бы предложил половину оплаты по счётчику плюс полную сумму от последней остановки.
fridka
Sep. 17th, 2009 06:04 pm (UTC)
Ничего не поняла.
poslan_za_elkoy
Sep. 17th, 2009 06:11 pm (UTC)
Я и сам запутался - получается такссиссту слишком много. Сеййчас соображу :)
zhp
Sep. 17th, 2009 06:09 pm (UTC)
Первый выходящий платит по счетчику, сколько получается. Следующий вычитает эту цифру из показаний счетчика и платит за вторую часть поездки, и т.п.
fridka
Sep. 17th, 2009 06:17 pm (UTC)
То есть, если ты живешь в 20 километрах от друга, а я - в двадцати трех, то ты платишь за 20 километров, а я - за три. Хорошо получается, только как-то не слишком справедливо.
(Deleted comment)
(Deleted comment)
fridka
Sep. 17th, 2009 06:19 pm (UTC)
Твое (оно же Левино) решение - пока что самое оптимальное.
zuss
Sep. 17th, 2009 06:11 pm (UTC)
Я бы предложил первому заплалить половину плюс одну восьмую от стоимости первого отрезка. Второй платит стоимость второго отрезка, плюс полторы восьмые. Третий платит 1 + две с половиной восьмые, а третий 1 + три восьмые.
zuss
Sep. 17th, 2009 06:13 pm (UTC)
То есть, не восьмые, а шестнадцатые, конечно. ))
fridka
Sep. 17th, 2009 06:20 pm (UTC)
что-то я совсем запуталась. А почему?
zuss
Sep. 17th, 2009 06:28 pm (UTC)
При том условии, если дом каждого находится на равном расстоянии от места посадки, всем лучше сесть в разные машины. Для чего они сели в одну? Видимо, чтобы поболтать по дороге. Поэтому условие равной удаленности теряет смысл. Следовательно, надо рассматривать линейный путь, при котором последний как бы живет дальше всех. Отсюда и такая дифференциация.
janes9
Sep. 18th, 2009 07:35 pm (UTC)
Брать каждому отдельную машину дороже - и в задаче, и на практике.
nadia_yacik
Sep. 17th, 2009 06:14 pm (UTC)
человек, который не умеет считать - вроде меня - говорит, чтобы его отвезли в последнюю очередь и, соответственно, платит за всех по счетчику.
за это его потом поят пивом или там кормят бизнес-ланчами каждый по очереди.
делов-то :))
tea_cutter
Sep. 17th, 2009 06:48 pm (UTC)
По 100 рублей.
rallex
Sep. 17th, 2009 07:21 pm (UTC)
+1
janes9
Sep. 18th, 2009 07:35 pm (UTC)
:-D
las__
Sep. 17th, 2009 06:50 pm (UTC)
я гений, б/п!
разница в показаниях счетчика между двумя пунктами делится на число пассажиров, оставшихся к этому времени в машине, и каждый отдает получившуюся сумму шофёру. усё.
gostrov
Sep. 17th, 2009 07:53 pm (UTC)
Re: я гений, б/п!
То есть последний катается по всему городу, теряет время и еще платит больше всех?
las__
Sep. 17th, 2009 07:58 pm (UTC)
Re: я гений, б/п!
таксист везет оптимальным маршрутом, то есть, последнему и так дальше и дольше всех ехать и, соответственно, платить больше кого-либо, кто живет ближе, чем он.
хинт - "по-честному" в условиях данной задачи вовсе не значит "поровну".
ну, или это задача не математическая, а психологическая - кто как в данной ситуации понимает слово "по-честному" :)
gostrov
Sep. 17th, 2009 08:08 pm (UTC)
Re: я гений, б/п!
Но мы же не знаем, насколько ему дальше. Может, от дома второго третьему и последнему вообще в разные стороны. Я там ниже предлагаю математически правильное решение.
las__
Sep. 17th, 2009 08:16 pm (UTC)
Re: я гений, б/п!
согласна. я сильно уперлась в слово "оптимальный" (в моём представлении это такой путь, что шофёру не приходится в каком-либо пункте выбирать между двумя противоположными направлениями).
e_rubik
Sep. 17th, 2009 07:17 pm (UTC)
Это подготовка к субботе?
gostrov
Sep. 17th, 2009 07:51 pm (UTC)
Рассмотрим сначала случай двух пассажиров. Если второй живет почти рядом с первым, то справедливо первому заплатить половину того, что проехали вместе. Если второй живет почти на таком же расстоянии от первого, как и от исходний точки, то он почти не выигрывает от того, что едет вместе, и справедливо первому полностью расплатиться за свой участок. На самом деле истина лежит посередине - вот и возьмем среднее арифметическое, т.е. первому надо заплатить 3/4 от суммы на счетчике.

Распространяем этот принцип на произвольное число пассажиров: каждый кроме последнего платит 3/4 стоимости участка непосредственно перед его домом, остальное поровну. То есть:

Первый платит 3/4 первого участка.
Второй - 1/12 1-го + 3/4 2-го.
Третий - 1/12 1-го + 1/8 2-го + 3/4 3-го.
Четвертый - 1/12 1-го + 1/8 2-го + 1/4 3-го + полностью 4-й.
ruby_tooz
Sep. 17th, 2009 10:26 pm (UTC)
Это если предположить, что "истина лежит посередине". А точный расчёт невозможен в принципе.
Рассмотрим случай двух пассажиров. Полное расстояние b, первый вышел, проехав a, a
[Error: Irreparable invalid markup ('<b.>') in entry. Owner must fix manually. Raw contents below.]

Это если предположить, что "истина лежит посередине". А точный расчёт невозможен в принципе.
Рассмотрим случай двух пассажиров. Полное расстояние b, первый вышел, проехав a, a<b. Пусть S - сумма на счётчике в момент выхода первого пассажира. В конце пути на счётчике будет S*b/a, эту сумму должен получить таксист, и её-то и нужно разделить по-честному. Доля каждого пассажира должна быть пропорциональна проеханному им расстоянию, конкретно - a/(a+b) и b/(a+b), в сумме дают 1. Поэтому первый пассажир должен заплатить не S, а S'=S*b/(a+b) - сами посчитайте, в строчку очень неудобно дроби сокращать :). В предельных случаях, как Вы совершенно правильно указали, при a->0 S'->S, при a->b S'->S/2. Но в общем случае для точного расчёта необходимо знать b, а это по условию задачи невозможно. Так что увы.
То же верно и для произвольного числа пассажиров.
Да, и на самом деле не 3/4, а ln(2) ;)
gostrov
Sep. 17th, 2009 11:03 pm (UTC)
Все справедливо, кроме того, что доля каждого пассажира должна быть пропорциональна не проеханному им расстоянию, а тому расстоянию, которое он проехал бы, если бы ехал один прямо домой, а это не одно и то же и еще больше запутывает картину.

В общем, после прикидок в Экселе (вот человеку на работе делать нечего) неплохое приближение получается, если каждый платит половину своей суммы + четверть предыдущей. То есть:

Первый платит 1/2 первого участка.
Второй - 1/4 1-го и 1/2 2-го.
Третий - 1/4 1-го, 1/4 2-го и 1/2 3-го.
Четвертый - 1/4 2-го, 1/2 3-го и полностью 4-й.

Теперь каждый получается в выигрыше по сравнению с индивидуальным такси и процент выигрыша более-менее близок.
ruby_tooz
Sep. 17th, 2009 11:23 pm (UTC)
доля каждого пассажира должна быть пропорциональна не проеханному им расстоянию, а тому расстоянию, которое он проехал бы, если бы ехал один прямо домой, а это не одно и то же и еще больше запутывает картину

Да, действительно, это еще хуже.
mr_shmellbass
Sep. 17th, 2009 07:56 pm (UTC)
Арифметика, мэм...
Сумма от точки отправления до места высадки первого пассажира делиться на 4, от первого до второго на три и от второго до третьего на 2...Ну и остаток пути последний оплачивает из своего кармана сам...
В первом приближении выглядит логично, ибо если бы им всем надо было бы принципиально в разные стороны- они не брали бы одно такси, а взяли бы к примеру, два, три и т.д.
Косяк со стороны водителя исключён исходя из условий задачи.
evro
Sep. 17th, 2009 07:58 pm (UTC)
По-идее так:
p - цена одного километра

1 проехал x1 км и платит x1*p/4
2 проехал x2 км и платит x1*p/4 + (x2-x1)*p/3
3 проехал x3 км и платит x1*p/4 + (x2-x1)*p/3 + (x3-x2)*p/2
4 проехал x4 км и платит x1*p/4 + (x2-x1)*p/3 + (x3-x2)*p/2 + (x4-x3)*p
evro
Sep. 17th, 2009 07:59 pm (UTC)
А, нефига. Понял в чем косяк.
evro
Sep. 17th, 2009 08:03 pm (UTC)
Вообще, конечно, надо измерить расстояние по прямой до дома каждого пассажира, сумму расстояний принять за единицу и посчитать доли каждого пассажира.

В условиях года - погрешность небольшая, а если брать, например, сельскую местность, то метод сильно зависит от дорожной сети.

Иначе говоря, до дома одного пассажира может быть километр по прямой, но чтобы к нему подъехать, надо сделать крюк в пять.
simatrix
Sep. 17th, 2009 09:25 pm (UTC)
Пробегая мимо...
Первый пассажир перед выходом платит по счетчику, водитель откладывает его деньги в сторону и едет дальше, второй пассажир перед выходом платит по счетчику, водитель отдает ему деньги первого пассажира в качестве сдачи и откладывает полученные деньги до выхода следующего пассажира - и так далее. Последний пассажир платит по последнему показанию счетчика и получает деньги предпоследнего в качестве сдачи.
fridka
Sep. 18th, 2009 05:33 am (UTC)
Re: Пробегая мимо...
Осталось уговорить шофера. Он на этом неплохо так теряет.
sveta_spb
Sep. 18th, 2009 09:50 am (UTC)
Re: Пробегая мимо...
Почему теряет?
fridka
Sep. 18th, 2009 09:57 am (UTC)
Re: Пробегая мимо...
или это я стормозила?
sveta_spb
Sep. 18th, 2009 10:04 am (UTC)
Re: Пробегая мимо...
Или я. Я так поняла, что каждый раз полные показания оплачиваются. Но тогда это ж вроде ничем не отличается от варианта, когда оплачивается разница, про который уже выяснили, что он несправедливый...
mitiay
Sep. 17th, 2009 10:11 pm (UTC)
Астарожна, многабукаф!
Из предыдущих комментариев вроде следует, что в твоем понимании "по-честному" - это пропорционально километражу. Начнем с того, что так не бывает :) Например, четыре пассажира живут в углах квадрата, из центра которого выехали, кварталы тоже квадратные, тогда один платит вчетверо больше другого исключительно из-за предпочтений таксиста по прокладке маршрута. Пусть тогда для каждого из них участок оптимального маршрута, проложенного таксистом, является оптимальным маршрутом до дома. Ну, до кучи еще положим, что таксист берет деньги просто пропорционально километражу, без суммы "за посадку". Расстояния, которые проедут пассажиры, обозначим как x,y,z,t, плату примем 1 уе за 1 единицу длины, все равно потом сократится :) Тогда совсем по-честному будет так: первый платит x*t/(x+y+z+t), второй соответственно y*t/(x+y+z+t), ну и так далее.
Поскольку по условию к моменту высадки первого ну ваще не известно, какими будут y, z и t, в качестве нулевого предположения мы примем, что расстояния между остановками одинаковы, то есть y = 2x, z = 3x, t = 4x. Если ну совсем никаких разумных предположений больше нет, то придется этим и обойтись и стребовать с первого x*4x/(x+2x+3x+4x)=2x/5, то есть 40% оплаты по счетчику.
К моменту высадки второго нам уже известно два расстояния, поэтому будем теперь считать, что машина проехала половину всего пути. То есть оценка общего расстояния равна 2y (третий выйдет при 1.5y), и нужно честно разлитьразделить сумму (2y-2x/5) на троих пропорционально их расстояниям. Второй должен заплатить y*(2y-2x/5)/(y+1.5y+2y) = 4y/9-4x/45. Уже веселая формула для троих (пьяных?) гостей, которым, оказывается, надо было еще запомнить ту сумму, которая была на счетчике, когда выходил первый :) После этого третий догадывается, что ему нужно запомнить и сумму на счетчике, когда выходил второй, и такси едет дальше.
К третьей остановке мы полагаем, что пройдено три четверти пути, и сумму (4z/3-(4y/9-4x/45)-2x/5) надо делить на двоих. Третий платит (4z/3-4y/9-14x/45)*z/(z+4z/3) = 4z/7-4y/21-2x/15. Четвертому в конце надо будет доплатить оставшееся.
Проверим правильность решения для сферического коня в вакууме, то есть когда действительно y = 2x, z = 3x, t = 4x. Первый платит 2x/5, второй 4*2x/9-4x/45 = 36x/45 = 4x/5, то есть в два раза больше первого. Третий платит 4*3x/7-4*2x/21-2x/15 = 126x/105 = 6x/5, то есть в три раза больше первого. На долю четвертого остается 4x-6x/5-4x/5-2x/5=8x/5, так что все правильно, но ничего не понятно :)
Сравним "честность" этого решения с твоим вариантом. Во-первых, при равных расстояниях между остановками в твоем случае первый платит x/4, то есть мало того, что живет близко, так еще и недоплачивает! Второй платит x/4+x/3 = 7x/12, что тоже меньше "честной" суммы. Третий x/4+x/3+x/2 = 13x/12 - и это тоже меньше! Бедный четвертый вынужден отдать 25x/12, что примерно на 30% больше нормы.
Проблемы у моего варианта начинаются, когда несколько пассажиров (пусть это будут все!) живут далеко от старта, но очень близко друг от друга (пусть первые двое об этом не знают, а то точно не согласятся на мой вариант). В твоем варианте все относительно счастливы - честно поделят плату за длинный участок и не очень честно остальное, но оно и непринципиально. А в моем - методика оценки полного расстояния дает сбой и первому приходится отдавать примерно на 60% больше, второму - на 42%, третий считается практически правильно (оценка предстоящего пути все еще кривая, но первые двое уже очень много заплатили), а четвертый может вообще оказаться в плюсе и получить до 1/315 от общей суммы :)
В общем, как ни пытайся честно разделить - все равно корень зла в неправильной оценке предстоящего пути.
serginhio
Sep. 18th, 2009 02:17 am (UTC)
Был в схожей ситуации. Все жили "в одном направлении", каждый выходящий платил 2/3 суммы счетчика. На утро сверились - погрешность в 10 рублей со 150 - можно пренебречь.
evgeniakon
Sep. 18th, 2009 04:35 am (UTC)
По-моему, проще каждому из них заказать отдельное такси. :)
fridka
Sep. 18th, 2009 04:49 am (UTC)
Задача придумана в конце 80-х. Тогда четрые такси в одном месте в один день были нереальны.
( 40 comments — Leave a comment )

Profile

пудель
fridka
Счастливая женщина

Latest Month

August 2017
S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Tags

Powered by LiveJournal.com