?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

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

Пока я это писала, Лев придумал решение, кажется, напоминающее правильное. Но не знаю, может, есть и лучше.

Comments

( 40 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
poslan_za_elkoy
Sep. 17th, 2009 06:00 pm (UTC)
Я бы предложил половину оплаты по счётчику плюс полную сумму от последней остановки.
fridka
Sep. 17th, 2009 06:04 pm (UTC)
Ничего не поняла.
(no subject) - poslan_za_elkoy - Sep. 17th, 2009 06:11 pm (UTC) - Expand
zhp
Sep. 17th, 2009 06:09 pm (UTC)
Первый выходящий платит по счетчику, сколько получается. Следующий вычитает эту цифру из показаний счетчика и платит за вторую часть поездки, и т.п.
fridka
Sep. 17th, 2009 06:17 pm (UTC)
То есть, если ты живешь в 20 километрах от друга, а я - в двадцати трех, то ты платишь за 20 километров, а я - за три. Хорошо получается, только как-то не слишком справедливо.
(Deleted comment)
(Deleted comment)
(no subject) - fridka - Sep. 17th, 2009 06:19 pm (UTC) - Expand
zuss
Sep. 17th, 2009 06:11 pm (UTC)
Я бы предложил первому заплалить половину плюс одну восьмую от стоимости первого отрезка. Второй платит стоимость второго отрезка, плюс полторы восьмые. Третий платит 1 + две с половиной восьмые, а третий 1 + три восьмые.
zuss
Sep. 17th, 2009 06:13 pm (UTC)
То есть, не восьмые, а шестнадцатые, конечно. ))
(no subject) - fridka - Sep. 17th, 2009 06:20 pm (UTC) - Expand
(no subject) - zuss - Sep. 17th, 2009 06:28 pm (UTC) - Expand
(no subject) - janes9 - Sep. 18th, 2009 07:35 pm (UTC) - Expand
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
(no subject) - janes9 - Sep. 18th, 2009 07:35 pm (UTC) - Expand
las__
Sep. 17th, 2009 06:50 pm (UTC)
я гений, б/п!
разница в показаниях счетчика между двумя пунктами делится на число пассажиров, оставшихся к этому времени в машине, и каждый отдает получившуюся сумму шофёру. усё.
gostrov
Sep. 17th, 2009 07:53 pm (UTC)
Re: я гений, б/п!
То есть последний катается по всему городу, теряет время и еще платит больше всех?
Re: я гений, б/п! - las__ - Sep. 17th, 2009 07:58 pm (UTC) - Expand
Re: я гений, б/п! - gostrov - Sep. 17th, 2009 08:08 pm (UTC) - Expand
Re: я гений, б/п! - las__ - Sep. 17th, 2009 08:16 pm (UTC) - Expand
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) ;)
(no subject) - gostrov - Sep. 17th, 2009 11:03 pm (UTC) - Expand
(no subject) - ruby_tooz - Sep. 17th, 2009 11:23 pm (UTC) - Expand
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: Пробегая мимо...
Осталось уговорить шофера. Он на этом неплохо так теряет.
Re: Пробегая мимо... - sveta_spb - Sep. 18th, 2009 09:50 am (UTC) - Expand
Re: Пробегая мимо... - fridka - Sep. 18th, 2009 09:57 am (UTC) - Expand
Re: Пробегая мимо... - sveta_spb - Sep. 18th, 2009 10:04 am (UTC) - Expand
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 - можно пренебречь.
Page 1 of 2
<<[1] [2] >>
( 40 comments — Leave a comment )

Profile

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

Latest Month

October 2017
S M T W T F S
1234567
891011121314
15161718192021
22232425262728
293031    

Tags

Powered by LiveJournal.com