Мальчик разрезал торт на 10 частей (не обязательно равных).
Потом взял и съел самый маленький кусочек (если таких несколько, то любой из них).
Потом разрезал один из оставшихся кусков на 2 и снова съел самый маленький из 10.
И последний раз разрезал один из кусов на два и съел самый маленький из 10.

Вопрос: какую максимальную часть торта мог съесть мальчик?

20% торта макс

<= 1/10

От балды - 3/8

(1) Почему я могу и 80% съесть при такой формулировки

4/20

(2) Неправильно.

так как он ест только самый маленькие куски, то чтобы съесть больше - самый маленький кусок должен быть максимально большим, значит резать надо на равные части. сначала режим на 10 равных. съедаем 1/10. потом режем 1/10 на равные половинки, в 2 итерации съедаем еще 1/10

3/14

я могу съесть так 37,5 %

20%

Отрезаем 1/100 1 часть потом еще раз 1/100 - вторую , потом еще 1/100 - тертью.
Остальное делим на 7 равных частей. Получаем 10 не очень равных частей.
Съдам первую.  Делим большой кусок пополам, съедам второй, еще один кусок делим -съедаем третий кусок.
Ответ мальчик съел столько сколько хотел

(7) во второй итерации получаеи 2 по 1/20й, значит съесть можем только 1/20 во второй итерации, в 3й съедаем ещё 1/20. 1/10+1/20+1/20

1 раз - съел максимиум - 1/10
2 раз - макс. 1/20
3 раз - макс. 1/20
итого: 2/10 = 1/5, т.е., 20%

(12) че сказать то хотел? 1/10+1/20+1/20 = 20%, что я и написал в (1)

"в 2 итерации съедаем еще 1/10" в две итерации съедаем еще 1/10 - два раза едим по 1/20

(14) аа, в "две" итерации, а я думал во "второй"

Разделяем торт на части:
1/12 - 8шт
2/12 - 2шт

Съедаем 1/12, на втором шаге делим 2/12 и съедаем ещё 1/12. На третьем тоже самое.


В итоге съели 3/12 = 1/4

(12),(14) делим на 14 частей: 1,1,1,1,1,1,1,1,2,2.
1) едим 1
2) делим 2 пополам, едим 1,
3) делим 2 пополам, едим 1
итог 3/14 торта = 21,42%.
Кто больше?)

(18), упс, каюсь, у меня с арифметикой беда) получается так же как в (17)

(13) +1

жадные 1С-ники, что вы сразу есть начинаете по максимуму?

(18) почему на 14?

(18) пока придерживаюсь этого же решения.

(18) А почему 14 а не 12??
2/12 = 1/6 максимум что съест мальчик!

Взяли кусок, разделили на 2 части стало 2 куска. То есть был 1 и появился еще 1!
было 10, в начале стало 11
потом стало 10
потом опять 11
потом опять 10
появилось за все итерации только 2 кусочка!

(21) Что про (17)?

(24)а почему 2 если 3?

(18) только действительно 3 / 12, т.е 1 / 4

(26) Осталось доказать, что больше нельзя

(17) да, так лучше будет ) 25% получается

11 ответ как по мне самый правильный)

а там максимальная часть... плохо прочитал условие(

(26) пропустил, да верно, а больше нельзя?

вообще да, 20%

17 похоже на правду:
всего кусков после 3х разрезаний 12
съедено из них 3 минимальных, 3/12=25%

(35) тебе надо доказать, что при переходе к 3 из 12 ты всегда ешь минимальные. В общем случае - это неочевидно.

(36) в (17) вроде предельно четко алгоритм описан. что там неочевидно?

Тут заковыка, он резал случайные куски, а ел минимальные

(37) в (17) частный случай. Нет доказательства, что это максимальное значение.

(37) неочевидно, что он дает максимальный результат, например, если сначала отрезать 1/11, а потом остатки по-другому распределить, вдруг будет еще лучше

(33) Порядок поедания/отрезания тут неважен (это можно отдельно доказать, думаю)
Т.е. мальчик мог тупо порезать торт на 12 частей а потом съесть три минимальных.

(36) Итак реально, всего кусков 12

a1<=a2<=a3<=...<=a12
a1+a2+a3+...+a12=1

Очевидно мальчик съел a1+a2+a3, но
a1+a2+a3<=a1+a2+a3
a1+a2+a3<=a4+a5+a6
a1+a2+a3<=a7+a8+a9
a1+a2+a3<=a10+a11+a12

складываем: a1+a2+a3<=(a1+a2+a3+...+a12)/4=1/4

(42) Неочевидно. Где гарантия, что разрезая он сперва не съел а4, а потом а2 и а1, так как как а3 получился только на 2 интерации?

Берем самый простой вариант 10 кусков равномерных.

едим 1-й
делим любой в пропорции пополам у нас 2 куска по 5 и они минимальны


Итого 20 %
по ощущениям предел должен быть в районе 25 %

максимально - это если сначала порезал на 10 равных частей, съел 1/10, потом 2 раза оставшиеся нетронутые куски резал ровно пополам и съел еще 2 раза по половине 1/10, т.е., 2 раза по 1/20

согласен обсчитался, 3/12 = 1/4 !))

(45) неравномерным можно достичь большего

(43) *итерации. Приношу извинения.

(47) всегда ел минимальный кусок, так что вряд ли...

(47) как раз таки равномерным больше. Всё правильно, сначала режем на 10, потом ещё 2 раза, т.е. всего на 12 частей. Если резать равномерно и жрать по 1/12, то и получаются максимальные 3/12, т.е. 25%

17,5%

3/16

(51) неудачник?) здесь уже выложено 2 алгоритма, как можно съесть 20% и 25%

Исходя из того, что всегда мальчик ест самый маленький из имеющихся кусков:
1. В первый раз максимум, который он может съест - это 0.1 торта. при любом неравном делении кусков он съест меньше 0.1
2. Соответственно по второй раз он не сможет съесть больше 0.1/2=0,05
3. остаются куски по 0.1 и 0.05, то есть у него два варианта - либо резать 0.1 пополам, либо 0.05. Исходим из того, что мальчик не идиот и режет максимальный, то есть он съедает еще 0.05
Игого: 0.1+0.05+0.05 = 0.2 торта, то есть 20%

Кстати, а торт круглый? ))

(53) =( Некорректно прочитал ТЗ =(

опровергни (17). он съест в первый раз меньше 0.1 зато потом нагонит и перегонит

(57) это к (54)

2/10

(57) а, ну или так

(55) А какая разница? Треугольный, допустим

(61) на круглом считать проще. )

(0) а торт равномерен по плотности?

(63) хороший вопрос!

Зададимся получением 21

Нам нужны следующие куски 7+14+14+7*9= 98

(0)"Вопрос: какую максимальную часть торта мог съесть мальчик?"

максимальную в объеме или в весе?)

(64)я анекдот вспомнил про еврейского мальчика, перед которым клали 2 монетки 3 и 5 шекелей. он всегда брал 3, она была больше по размеру. так повотрялось много раз.
Ребе спросил, почему ты поступаешь так неразумно? Возьми 5!
мальчик ответил, если я так сделаю, они перестанут давать мне деньги.

+(65) цель 24

8+16+16 +7(8,57)

(66) а пофиг, если надо по объёму, то делим на 12 равных по объёму, а если по весу, то делим на 12 равных по весу.

(54)
Жадный алгоритм не всегда приводит к максимальному результату

Соответсвено предел 25%

(43) "дорезаний" было два, а кусочков среди "маленьких" a1, a2, a3 -  три, поэтому хотя бы один был получен изначально
вот меньший из "маленьких" и едим
делаем дорезание №1, если появился "маленький" - опять едим его, если не появился, то уже был, все равно едим его
и так же со вторым дорезанием

(63) + и по высоте

(71) это уже в (17) стало извесно

Вопрос: какую максимальную часть торта мог съесть мальчик?
Мог весь торт съесть, в условии же не сказано, что он после третьего куска есть остановился, он только последний раз торт разрезал...

(0) Можно съесть четверть (25%) торта

(74) Чукча не читатель ;)

В общем, пока решение видится в таком виде.

Чтобы съесть максимум торта, нам надо съесть максимум в каждой итерации. Возьмем последнюю 3 итерацию. У нас есть десять кусков и из них надо съесть 1. Максимум функции F = Min(A) достигается, если A - однородное, т.е. все куски одинаковые на 3 итерации. Откатываемся ко 2 итерации. Для того, чтобы нам съесть максимум торта, кусок, который мы съели, должен быть больше либо равен минимальному куску в третьей итерации. Учитывая, что все куски в третьей итерации однородны и что мы обязаны съедать минимальный во второй итерации, мы получаем, что во второй итерации мы съели такой же кусок, как и в третьей. Аналогично доказываем первую итерацию. Итог мы получаем, что мы съели 3 из 12 равных кусков. Т.е. максимум 25%.

(0)
Пусть объем  всего торта равен 1
Ответ: 1/2 + 1/4 + 1/8 - Е, где Е > 0 - сколь угодно малое число.

(78) "Чтобы съесть максимум торта, нам надо съесть максимум в каждой итерации." - это неочевидно. Может максимум достингается разными размерами?

(80) это очевидно. Если ты съедаешь в 3ей не максимум - значит это не оптимальное состояние и можно найти лучшее. Значит в ей также надо есть максимум.

(78)
Первое предложение неверное.

как лесица сыр делила?

(78) согласен, динамическое программирование, рассуждения с конца процесса

(81)
В максимальном примере (25%) как раз первый раз не максимальный. Максимальным за первый раз является 10% от торта.

(82) первое предложение лишее, скажем так

(82), если ты съел не максимум - значит это не оптимальное решение. Ибо можно съесть больше. Следовательно максимум надо есть на каждой итерации.

Максимум в последней итерации, но не обязательно в первых двух

(87)
Читай про жадные алгоритмы и матроиды

а ответ получается 3/20

(85) там доступный максимум. Как бы максимум для функции Min(A), а не Максимум из кусков.

Если после первого деления торта мальчик делил куски на две равные части, то ответ 1/10 + 1/10 + 1/10 - Е = 3/10 - Е, Е>0 - сколь угодно малое
Если делил на 2 НЕравные части, то ответ 1/10 + 1/20 + 1/40 - Е = 7/40 - Е, Е>0 - сколь угодно малое

(92) ответы местами перепутал.
Если делил на 2 равные, то 7/40 - Е
Если делил на 2 неравные, то  3/10 - Е

сходу же 20%

(93) Правильный ответ видимо в (17), тока доказательства строгого пока нет.

(94) Нужно максимизировать долю.

(89) ну так вроде именно это здесь и используется, если я все правильно помню и понимаю.

(95) всего 12 долей, максимальная минимальная ))) доля 1/12, какие ещё нужны доказательства?

10,75%. Вроде так

я не пойму что то чё вы тут рассуждаете
чтобы съесть наимбольший наименьший кусок нужно поделить торт на равные части.
то есть на 1/10. и мы съедаем кусочек.
затем парень режет ещё один кусок (любой вить все равны)
тоесть 1/10/2 = 1/20 и ест его(как минимальный)
потом повторяет(решет 1-н большой и ест половину(1/20)

получается 1/10+1/20+1/20 = 4/20 или 1/5 = 0,2

(98) Пардон, 15,25%

(97) Это доказательство такое :)?

(100) Не, 17,5%. Вроде так.

Похоже Адский плющ самый сытый будет )

1/4

25%

(104) опередил, блин

(106) из Эстонии?

(107) Когда писал ответ, не видел вторую страницу.

3/12=1/4
10 кусков 8 по 1/12 и 2 по 1/6
Сожрал 1/12, 1/6 разрезал на 2
Сожрал еще 1/12, 1/6 поделил на 2, сожрал еще 1/12

(109) я считал 9 кусков по 1/12 и 1 по 3/12, который два раза будет резать. Но суть не меняется.

(110) тут все упирается в осознание что всего кусков будет 12, и есть он будет 3 минимальных из них, а дальше уже не важно)

Мальчик конечно странный, на всю голову

(112) Вполне нормальный, если предположить что его попросили нарезать торт на 9 частей, но не есть, а он очень хотел съесть и чтобы это никто не заметил.

(99) неа, торой раз он разрезал большой кусок

50% Точно сожрет

максимум будет 50% + 25% итого 75%

Да, как у вас такие цифры-то получаются?

Из 10 неравных или равных долей мелкий подлец ополовинил две. В итоге - 12 долей. Съел 3 наименьшие доли.
Задача - превратить съеденные 3 наименьшие доли в максимально большие.
Как только одна из трёх выбранных долей будет больше любых других наименьших трёх, то она перестаёт быть наименьшей.
Выход один - уровнять полученные 12 долей. Условие, описанное мной, не обеспечивает, но и не противоречит условию автора задачи.
3/12 = 1/4 = 25%

Моё решение:

Максимальный первый кусок: 1/10
Максимальный второй кусок: 1/20
Максимальный третий кусок: 1/40

Ответ: 1/10 + 1/20 + 1/40 = 7/40 = 17,5%

Будет правильный ответ, или я его просмотрел?

(118) Максимальный кусок, то есть режем на равные куски:)

30%

(33) Почему верно, если он резал-жрал-резал-жрал...? ;)

у нас технологи карту раскроя торта делают на компе)))

Предлагаю собраться в пивбаре и смоделировать на пиве!!!

(118) ЦБ по твоей формуле ключевую ставку считал... однажды ночью

(118) Правильный ответ уже был в (105)

(123) С тобой что ли? Никто не придет.

Решаем в обратном порядке, пытаемся добавлять к изрезанному торту куски и склеивать их так, чтобы добавить как можно больше.

Имеем 9 кусков, добавляем кусок<= любого из этих 9
Максимальная добавка получится, если все 9 кусков равны и мы добавим такой же по размеру кусок.
После этого склеиваем любые два куска.
Добавляем еще один кусок, такого же размера, как прошлый.
Склеиваем любые два куска одного размера
И еще добавляем кусок такого размера
Получаем исходный торт.

Итого 9+1+1+1=12

Значит, съели 3/12

Первый раз он съел минимальный из 10 то есть максимум 1/10,
второй раз взял из 9 оставшихся который был 1/10 еще располовинил считаем равными 1/20, и еще раз 1/20, 1/5 то.е 20%

(128)
Цель задачи - найти максимально-возможный съеденный объем торта.
Мальчик может сожрать больше.

четверть торта

(125) Почему он правильный?

(131) Потому, что он больше, чем твои 17,5 и в (109) алгоритм не противоречащий условиям задачи.