Задача 66344

Темы:    [ Теория алгоритмов (прочее) ] [ Оценка + пример ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Толпыго А.К.

Кусок сыра надо разрезать на части с соблюдением таких правил:
    вначале режем сыр на два куска, затем один из них режем на два куска, затем один из трёх кусков опять режем на два куска, и т.д.;
    после каждого разрезания части могут быть разными по весу, но отношение веса каждой части к весу любой другой должно быть строго больше заданного числа $R$.
  а) Докажите, что при  $R$ = 0,5  можно резать сыр так, что процесс никогда не остановится (после любого числа разрезаний можно будет отрезать ещё один кусок).
  б) Докажите, что если  $R$ > 0,5,  то процесс резки когда-нибудь остановится.
  в) На какое наибольшее число кусков можно разрезать сыр, если  $R$ = 0,6?

Решение

  а) Исходный кусок разрежем, например, в отношении  $3 : 2$.
  Пусть у нас уже есть несколько кусков весов  $2d > 2c > ... > b > a$,  удовлетворяющих условию задачи, то есть  $a > d$  (возможно, что кусков всего два или три, тогда некоторые веса выписаны дважды). Покажем, что можно сделать ещё один шаг с сохранением условий. Выберем положительное  $h < min(a - d, d- c)$.  Разрежем больший кусок на куски веса  $d + h$  и  $d - h$.  Тогда  $d + h < a$  и  $d - h > c$,  то есть для кусков $2c > ... > b > a > d + h > d - h$  условия по-прежнему выполнены.

  б) Будем считать, что вес исходного куска равен 1. Пусть на некотором этапе у нас есть $k$ кусков, причём самый большой из них имеет вес $M$. Поскольку каждый из остальных кусков больше $\frac{M}{2}$, то сумма всех весов равна 1 и больше  $M(1 + \frac{k-1}{2}) = \frac{(k+1)M}{2}$,  то есть  $M < \frac{2}{k+1}$.
  Пусть процесс продолжается неограниченно долго. В силу доказанного неравенства каждый кусок рано или поздно будет разрезан. Поскольку  $2R > 1$,  найдётся такое натуральное $n$, что  $(2R)^n > 2$.  Зафиксируем веса кусков на момент, когда есть  $n+1$  кусок, и продолжим разрезания, пока все фиксированные веса не будут разрезаны. Пусть  $a \geqslant b$  – соседние фиксированные веса. Так как  $R > 0,5$,  то каждый раз мы режем самый большой кусок $M$, иначе обе части не будут больше $RM$. Поэтому, когда $a$ будет разрезан, $b$ ещё цел. Пусть $a$ разрезан на части веса $c$ и $d$. По условию  $c > Rb$  и  $d > Rb$,  а  $a > 2Rb$.  Написав аналогичные неравенства для всех фиксированных весов, получим что отношение наименьшего фиксированного веса $m$ к наибольшему фиксированному весу $M$ меньше  $2R^{-n} < \frac{1}{2} < R$. Противоречие.

  в) Пример.  54 → {32, 22} → {22, 18, 14} → {18, 14, 11, 11} → {14, 11, 11, 9, 9} → {11, 11, 9, 9, 7, 7}.
  Оценка. Допустим, получилось семь кусков. Зафиксируем момент, когда было четыре куска:  $d \geqslant c \geqslant b \geqslant a$.  Затем было последовательно разрезано три куска. Как показано в б), на каждом шаге разрезается наибольший кусок. Значит, сначала был разрезан кусок веса $d$ – пусть на куски   $x \geqslant y$.  Поскольку  $y > \frac{3}{5}x$,  то  $x < \frac{8}{5}d < \frac{5}{3}d < a$.
  Следовательно, на этом момент наибольшим куском стал $c$, и разрезан будет он. Аналогично после этого будет разрезан кусок $b$. По доказанному в пункте б),  $d > 2Rс = 1,2c$.  Аналогично  $с > 1,2b$,  $b > 1,2a$.  Отсюда  $a < \left(\frac{5}{6}\right)^{3}d < 0,6d$.  Противоречие.

Ответ

в) На 6 кусков.

Замечания

Баллы: 3 + 4 + 4.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
номер/год
Номер	39
Дата	2017/18
вариант
Вариант	осенний тур, сложный вариант, 10-11 класс
задача
Номер	5