Поделить на троих
Apr. 16th, 2015 04:11 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ny_quantВчера отмечали - нет не налоги - день рождения у приятеля. Один чувак предложил задачу о том как три пирата нашли сокровище и делят его на троих так чтоб никому не было обидно. Как на двоих всем известно - один делит, а другой выбирает долю.
Несмотря на то, что был сильно подшофе (или, возможно, благодаря этому), задачу я (как мне кажется) решил примерно за минуту, но он решения не понял и не принял, поэтому я ему сегодня его прислал снова в письменном виде.
Пафос не в самой задаче, хотя желающие поразвлечься are welcome. Я свое решение положу в комментарий ниже. Чур не подглядывать.
Пафос в том, что он продолжает упорно утверждать, что моё решение неверно - уже штук 7 имэйлов прислал с различными возражениями, которые мягко говоря не по делу. Чувак при этом математик по образованию, формально мой коллега по профессии, занимается на работе нетривиальными вещами - и вот на тебе.
UPDATE. Оказалось, мы по разному понимали условия задачи. Я понял так: организовать процесс дележки таким образом, чтобы каждый получил то, что ему кажется не менее, чем 1/3 сокровища вне зависимости от очередности. С его точки зрения (моими словами): чтоб каждому казалось, что никто не получил больше, чем он.
Несмотря на то, что был сильно подшофе (или, возможно, благодаря этому), задачу я (как мне кажется) решил примерно за минуту, но он решения не понял и не принял, поэтому я ему сегодня его прислал снова в письменном виде.
Пафос не в самой задаче, хотя желающие поразвлечься are welcome. Я свое решение положу в комментарий ниже. Чур не подглядывать.
Пафос в том, что он продолжает упорно утверждать, что моё решение неверно - уже штук 7 имэйлов прислал с различными возражениями, которые мягко говоря не по делу. Чувак при этом математик по образованию, формально мой коллега по профессии, занимается на работе нетривиальными вещами - и вот на тебе.
UPDATE. Оказалось, мы по разному понимали условия задачи. Я понял так: организовать процесс дележки таким образом, чтобы каждый получил то, что ему кажется не менее, чем 1/3 сокровища вне зависимости от очередности. С его точки зрения (моими словами): чтоб каждому казалось, что никто не получил больше, чем он.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
...Да в ней намёк...
Date: 2015-04-17 06:57 am (UTC)Пусть x - число рыб. Тогда задача сводится к тому, чтобы найти целые y,z,w так, чтобы x=3y+1, 2y=3z+1, 2z=3w+1. Это - система линейных неоднородных уравнений, проблема - добиться целочисленности и неотрицательности. Как и в случае "обычных" систем, любое решение неоднородной системы получается из частного решения и любого решения однородной системы x=3y, 2y=3z, 2z=3w. Решения однородной системы легко описать: z=3/2 w, y=9/4 w, x=27/4 w. Чтобы оно было целочисленным, надо, чтобы w делилось на 4, и тогда получаем минимальное положительное решение x=27. Складывая с частным "решением Дирака", получаем x=25, и получаем минимальное "настоящее" решение.