Поедание торта

[Shadow]

(Оффтоп)

С этими вложенными цитатами трудно понять кто с кем разговаривает и о чем. Формальное доказательство оптимальности будет?

[whitefox]

Shadow в сообщении #943556 писал(а):

whitefox в сообщении #943541 писал(а):

С наименьшим весом.

Ну, весом, объемом - какая разница. Вот напр. 12 кусков:
$1,2,3,4,4,4,\cdots\quad (9\times 4)$ Можно съест куски $4,3,1$ Тоесть, утверждение

Sender в сообщении #943525 писал(а):

имеем 12 частей, из которых берутся 3 наименьшие

не верное и нельзя использовать в доказательстве.

То есть на первом шаге множество весов (в данном случае "вес" это абстрактное понятие и может обозначать массу, объём, и т. д.) будет $W_1=\{1,2,3,4\}$ наименьшим элементом будет 1, по условию задачи нужно выбрать кусок наименьшего веса, если таких кусков несколько, то любой из них.

Так как в вашем примере всего один кусок имеет вес 1, то после его поедание множество весов станет $W_2=\{2,3,4\}.$ И у нас нет никакого произвола в выборе веса (но может быть произвол в выборе конкретного куска наименьшего веса, если таких несколько).

После поедания второго куска множество весов станет $W_3=\{3,4\}$. И снова мы обязаны по условию задачи выбрать кусок наименьшего веса.

[Shadow]

whitefox в сообщении #943573 писал(а):

То есть на первом шаге множество весов будет $W_1=\{1,2,3,4\}$ наименьшим элементом будет 1, по условию задачи нужно выбрать кусок наименьшего веса, если таких кусков несколько, то любой из них.

Нет, на первом шаге множество весов было $W_1=\{6,4\}$, элемент весом 1 появился на позднем этапе. Так что на первом шагу съели кусок весом 4.

[whitefox]

Shadow в сообщении #943570 писал(а):

Формальное доказательство оптимальности будет?

Пусть $w$ обозначает суммарный вес съеденных кусков. Тогда если все 12 частей имеют одинаковый вес, то выбирая на каждом шаге кусок наименьшего веса получим $w=\frac14.$ Если же не все куски равны, то выбирая на каждом шаге кусок наименьшего веса получим $w<\frac14.$

-- 10 дек 2014, 12:16 --

Shadow в сообщении #943578 писал(а):

Нет, на первом шаге множество весов было $W_1=\{6,4\}$, элемент весом 1 появился на позднем этапе. Так что на первом шагу съели кусок весом 4.

Согласен, действительно нельзя утверждать, что из 12 частей будут выбраны три наименьших.

[Sender]

Да, можно утверждать лишь, что съеденные куски в общем случае попадают в пятёрку наименьших.

[gris]

Интересно, а если к Сардааночке пришёл Сарханчик, который всегда выбирает наибольший кусок, то может ли она при прочих равных условиях употребления тортика, минимизировать свои потери?

[Sender]

Эмпирическим путём удалось установить следующее.
Пусть $0 \leqslant a_1 \leqslant a_2 \dots \leqslant a_{12}$, $\sum\limits_{i=1}^{12}a_i=1.$
Тогда $a_1+a_i+a_j$ для произвольных $i,j$, удовлетворяющих $2 \leqslant i <j \leqslant 5 $, принимает максимальное значение при $a_1 = a_2= \dots =a_{12}=\frac{1}{12}.$
Наверняка должно существовать какое-нибудь изящное доказательство этому.

-- Ср дек 10, 2014 16:52:28 --

Хм, это естественным образом сводится к максимизации выражения $x+y+z$ при $0\leqslant x \leqslant y \leqslant z$ и $3x+y+8z=1.$

[Shadow]

Sender в сообщении #943685 писал(а):

Пусть $0 \leqslant a_1 \leqslant a_2 \dots \leqslant a_{12}$, $\sum\limits_{i=1}^{12}a_i=1.$
Тогда $a_1+a_i+a_j$ для произвольных $i,j$, удовлетворяющих $2 \leqslant i <j \leqslant 5 $, принимает максимальное значение при $a_1 = a_2= \dots =a_{12}=\frac{1}{12}.$

Так оно и есть. Пусть съела $S$, не съела $N$. Тогда $S \le 2a_5+a_1, \quad N \ge 7a_5+2a_1$

$\frac{N}{S} \ge \dfrac{7a_5+2a_1}{2a_5+a_1}=3+\dfrac{a_5-a_1}{2a_5+a_1} \ge 3$

А $a_6$ не может быть минимальным ни на каком этапе.