Задача 5.6. У Пети есть канат длины 1. За один ход он может разрезать любую из уже имеющихся частей каната на две части и записать на доске произведение длин этих двух частей. Докажите, что как бы он ни разрезал канат, сумма всех чисел на доске никогда не превысит \( \frac{1}{2} \).

Решение:

Пусть изначально у Пети есть канат длины 1. Он еще ничего не разрезал, и на доске ничего нет. Сумма чисел на доске равна 0.

Первый ход:

Петя разрезает канат длины 1 на две части с длинами \( x \) и \( 1-x \), где \( x ∈ (0, 1) \). На доску записывается произведение длин этих частей: \( x · (1-x) \).

Максимальное значение функции \( f(x) = x(1-x) = x - x^2 \) достигается при \( x = \frac{1}{2} \) и равно \( \frac{1}{2} · (1 - \frac{1}{2}) = \frac{1}{4} \).

Таким образом, после первого хода сумма чисел на доске не превышает \( \frac{1}{4} \).

Второй ход:

Петя выбирает одну из частей, например, длины \( x \), и разрезает ее на две части с длинами \( y \) и \( x-y \), где \( y ∈ (0, x) \). На доску записывается новое произведение: \( y · (x-y) \).

Новая сумма на доске будет равна \( x(1-x) + y(x-y) \).

Рассмотрим максимальное значение \( y(x-y) \). Оно достигается при \( y = \frac{x}{2} \) и равно \( \frac{x}{2} · (x - \frac{x}{2}) = \frac{x}{2} · \frac{x}{2} = \frac{x^2}{4} \).

Новая сумма тогда будет \( x(1-x) + \frac{x^2}{4} = x - x^2 + \frac{x^2}{4} = x - \frac{3x^2}{4} \).

Рассмотрим, как изменяется сумма. При разрезании части длины \( L \) на части \( l_1 \) и \( l_2 \) (где \( l_1 + l_2 = L \)), к сумме добавляется \( l_1 · l_2 \). Максимальное значение \( l_1 · l_2 \) равно \( (\frac{L}{2})^2 = \frac{L^2}{4} \).

Пусть \( S_k \) — сумма чисел на доске после \( k \) разрезаний. Изначально \( S_0 = 0 \).

После первого разрезания части длины 1 на \( x \) и \( 1-x \), на доске появляется \( x(1-x) \). \( S_1 = x(1-x) ≤ \frac{1}{4} \).

При втором разрезании, например, части длины \( x \) на \( y \) и \( x-y \), добавляется \( y(x-y) ≤ \frac{x^2}{4} \). Новая сумма \( S_2 = x(1-x) + y(x-y) ≤ x(1-x) + \frac{x^2}{4} \).

Рассмотрим инвариант. Пусть \( L \) — длина каната. Пусть \( S \) — сумма произведений на доске. После разрезания части длины \( L_i \) на \( L_{i1} \) и \( L_{i2} \), сумма увеличивается на \( L_{i1}L_{i2} \). Максимум этого произведения равен \( (\frac{L_i}{2})^2 = \frac{L_i^2}{4} \).

Рассмотрим другой подход. Пусть \( l_1, l_2, …, l_k \) — длины частей каната, на которые он был разрезан. Изначально \( ∑ l_i = 1 \).

При разрезании части \( l_j \) на \( l_{j1} \) и \( l_{j2} \), мы заменяем \( l_j \) на \( l_{j1} \) и \( l_{j2} \). При этом \( l_{j1} + l_{j2} = l_j \). На доску записывается \( l_{j1} · l_{j2} \). Новая сумма на доске — \( S_{new} = S_{old} - l_j + l_{j1}l_{j2} \).

Рассмотрим, что происходит с величиной \( \frac{1}{2} - S \) (где \( S \) — сумма чисел на доске).

Изначально \( S = 0 \), \( \frac{1}{2} - S = \frac{1}{2} \).

После первого разрезания на \( x \) и \( 1-x \), \( S = x(1-x) \). \( \frac{1}{2} - S = \frac{1}{2} - x(1-x) = \frac{1}{2} - x + x^2 \).

Мы хотим показать, что \( S ≤ \frac{1}{2} \).

Пусть \( l_1, l_2, …, l_n \) — длины частей каната. \( ∑ l_i = 1 \).

После \( n-1 \) разрезаний, на доске будет \( n-1 \) чисел. Сумма этих чисел равна \( S = · l_i l_j \) для некоторого набора пар \( (i, j) \).

Рассмотрим доказательство от противного. Пусть сумма на доске превысила \( \frac{1}{2} \). Это значит, что \( ∑_{i=1}^{k} l_i l_{i+1} > \frac{1}{2} \) (где \( l_i \) — это длины частей каната, и мы умножаем соседние).

Это не совсем так. Когда мы разрезаем часть длины \( L \) на \( y \) и \( L-y \), мы добавляем \( y(L-y) \). Максимум этого — \( (\frac{L}{2})^2 = \frac{L^2}{4} \).

Пусть \( S_k \) — сумма чисел на доске после \( k \) шагов. \( S_0 = 0 \). \( S_1 = x(1-x) ≤ \frac{1}{4} \).

Рассмотрим величину \( 1 - ∑_{i=1}^n l_i^2 \), где \( l_i \) — длины частей каната.

Изначально, \( l_1 = 1 \). \( 1 - 1^2 = 0 \).

После первого разрезания на \( x \) и \( 1-x \): \( 1 - (x^2 + (1-x)^2) = 1 - (x^2 + 1 - 2x + x^2) = 1 - (1 - 2x + 2x^2) = 2x - 2x^2 = 2x(1-x) \).

Заметьте, что \( x(1-x) \) — это число, которое мы записали на доску. И \( 2x(1-x) = 2 · S_1 \).

Теперь, если мы разрезаем часть длины \( L \) на \( y \) и \( L-y \), то \( L^2 \) заменяется на \( y^2 + (L-y)^2 \).

Изменение \( L^2 - (y^2 + (L-y)^2) = L^2 - (y^2 + L^2 - 2Ly + y^2) = 2Ly - 2y^2 = 2y(L-y) \).

Таким образом, каждый раз, когда мы разрезаем часть каната длины \( L \) на \( y \) и \( L-y \), величина \( 1 - ∑ l_i^2 \) увеличивается ровно в 2 раза, и это увеличение равно \( 2 · y(L-y) \).

\( 1 - ∑ l_i^2 = 2 · S \), где \( S \) — сумма чисел на доске.

Значит, \( S = \frac{1 - ∑ l_i^2}{2} \).

Нам нужно доказать, что \( S ≤ \frac{1}{2} \). Это эквивалентно \( \frac{1 - ∑ l_i^2}{2} ≤ \frac{1}{2} \), что равносильно \( 1 - ∑ l_i^2 ≤ 1 \), или \( -∑ l_i^2 ≤ 0 \), что верно, так как \( l_i^2 ≥ 0 \).

Однако, нам нужно доказать, что \( S ≤ \frac{1}{2} \).

У нас \( S = \frac{1 - ∑ l_i^2}{2} \). Мы хотим, чтобы \( \frac{1 - ∑ l_i^2}{2} ≤ \frac{1}{2} \). Это означает \( 1 - ∑ l_i^2 ≤ 1 \), что верно.

Похоже, я что-то упускаю. Давайте пересмотрим. Максимум \( y(L-y) \) равен \( \frac{L^2}{4} \).

Рассмотрим, как меняется сумма \( S \). Пусть \( S_k \) — сумма после \( k \) шагов.

\( S_0 = 0 \).

Шаг 1: Разрезаем 1 на \( x \) и \( 1-x \). \( S_1 = x(1-x) \). Макс \( S_1 = \frac{1}{4} \).

Шаг 2: Разрезаем \( x \) на \( y \) и \( x-y \). Добавляем \( y(x-y) \).

\( S_2 = x(1-x) + y(x-y) \). Макс \( y(x-y) \) равен \( \frac{x^2}{4} \).

\( S_2 ≤ x(1-x) + \frac{x^2}{4} = x - x^2 + \frac{x^2}{4} = x - \frac{3x^2}{4} \).

Максимум \( x - \frac{3x^2}{4} \) достигается при \( x = \frac{-1}{2 · (-\frac{3}{4})} = \frac{1}{2} · \frac{4}{3} = \frac{2}{3} \).

Максимальное значение \( S_2 = \frac{2}{3} - \frac{3}{4} (\frac{2}{3})^2 = \frac{2}{3} - \frac{3}{4} · \frac{4}{9} = \frac{2}{3} - \frac{1}{3} = \frac{1}{3} \).

\( \frac{1}{3} ≤ \frac{1}{2} \).

Похоже, сумма растет, но остается меньше \( \frac{1}{2} \).

Рассмотрим величину \( T = ∑ l_i − · l_i l_j \), где \( l_i \) — длины кусков каната. \( ∑ l_i = 1 \).

Пусть \( S \) — сумма чисел на доске. При разрезании куска \( L \) на \( y \) и \( L-y \), мы добавляем \( y(L-y) \).

Рассмотрим величину \( V = 1 - ∑_{i=1}^n l_i^2 \). Изначально \( V = 1 - 1^2 = 0 \).

Когда кусок \( L \) заменяется на \( y \) и \( L-y \), \( L^2 \) меняется на \( y^2 + (L-y)^2 \). Изменение \( V \) равно \( (y^2 + (L-y)^2) - L^2 = y^2 + L^2 - 2Ly + y^2 - L^2 = 2y^2 - 2Ly = 2y(y-L) \).

Что-то не сходится.

Правильное соотношение: \( (y + (L-y))^2 = L^2 \).

\( y^2 + 2y(L-y) + (L-y)^2 = L^2 \).

\( y^2 + (L-y)^2 = L^2 - 2y(L-y) \).

Изменение \( ∑ l_i^2 \) при разрезании \( L \) на \( y \) и \( L-y \) равно \( (y^2 + (L-y)^2) - L^2 = -2y(L-y) \).

Таким образом, \( 1 - ∑ l_i^2 \) увеличивается на \( 2y(L-y) \).

\( 1 - ∑ l_i^2 = 2S \), где \( S \) — сумма чисел на доске.

\( S = \frac{1 - ∑ l_i^2}{2} \).

Поскольку \( l_i > 0 \) для всех \( i \), и \( ∑ l_i = 1 \), то \( ∑ l_i^2 \) — это сумма квадратов положительных чисел, сумма которых равна 1.

По неравенству Коши-Буняковского или просто по тому, что \( (1 - ∑ l_i)^2 ≥ 0 \) (или \( ( ∑ l_i)^2 ≥ ∑ l_i^2 \) ), мы знаем, что \( (∑ l_i)^2 = 1^2 = 1 \).

\( ∑ l_i^2 ≥ \frac{(∑ l_i)^2}{n} = \frac{1}{n} \).

Если \( n \) — количество кусков, то \( ∑ l_i^2 ≥ \frac{1}{n} \).

Нам нужно показать, что \( S ≤ \frac{1}{2} \), что равносильно \( \frac{1 - ∑ l_i^2}{2} ≤ \frac{1}{2} \), то есть \( 1 - ∑ l_i^2 ≤ 1 \), или \( -∑ l_i^2 ≤ 0 \), что всегда верно.

Но это не доказывает, что \( S ≤ \frac{1}{2} \) с ограничением на \( ∑ l_i^2 \).

Рассмотрим \( ∑ l_i^2 \). Минимальное значение \( ∑ l_i^2 \) равно \( \frac{1}{n} \) (когда все \( l_i = \frac{1}{n} \)). Максимальное значение \( ∑ l_i^2 \) стремится к 1 (когда один \( l_i \) стремится к 1, а остальные к 0).

\( S = \frac{1 - ∑ l_i^2}{2} \).

Чтобы \( S ≤ \frac{1}{2} \), нам нужно \( 1 - ∑ l_i^2 ≤ 1 \), что верно.

Чтобы \( S \) было как можно больше, \( ∑ l_i^2 \) должно быть как можно меньше. Минимальное значение \( ∑ l_i^2 \) достигается, когда кусков много и они равны. Но нам не дано ограничение на количество кусков.

Давайте пересмотрим начальное условие. Петя разрезает канат длины 1. За один ход он может разрезать любую из уже имеющихся частей каната на две части и записать на доске произведение длин этих двух частей.

Пусть \( l_1, …, l_n \) — длины частей каната. \( ∑ l_i = 1 \).

На доске появляются числа \( a_1, a_2, …, a_m \).

Изначально \( m=0 \), \( S=0 \).

Шаг 1: Разрезаем 1 на \( x \) и \( 1-x \). Добавляем \( x(1-x) \) на доску. \( S = x(1-x) ≤ \frac{1}{4} \).

Шаг 2: Разрезаем \( x \) на \( y \) и \( x-y \). Добавляем \( y(x-y) \).

\( S = x(1-x) + y(x-y) \).

Мы знаем, что \( y(x-y) ≤ \frac{x^2}{4} \).

\( S ≤ x(1-x) + \frac{x^2}{4} = x - x^2 + \frac{x^2}{4} = x - \frac{3x^2}{4} \).

Максимум \( x - \frac{3x^2}{4} \) достигается при \( x = \frac{2}{3} \) и равен \( \frac{1}{3} \).

Шаг 3: Разрезаем, например, \( y \) на \( z \) и \( y-z \). Добавляем \( z(y-z) ≤ \frac{y^2}{4} \).

\( S = x(1-x) + y(x-y) + z(y-z) \).

\( S ≤ x(1-x) + y(x-y) + \frac{y^2}{4} \).

Докажем индукцией по количеству разрезов. База: 0 разрезов, \( S=0 ≤ \frac{1}{2} \).

Предположим, что после \( k \) разрезов сумма \( S_k ≤ \frac{1}{2} \).

На \( (k+1) \)-м шаге мы разрезаем одну из частей \( l_i \) на \( l_{i1} \) и \( l_{i2} \). К сумме \( S_k \) добавляется \( l_{i1} l_{i2} \).

\( S_{k+1} = S_k + l_{i1} l_{i2} \).

Мы знаем, что \( l_{i1} l_{i2} ≤ \frac{l_i^2}{4} \).

\( S_{k+1} ≤ S_k + \frac{l_i^2}{4} \).

Это не помогает.

Рассмотрим значение \( \frac{1}{2} - S \).

Изначально \( \frac{1}{2} - S = \frac{1}{2} \).

При разрезании \( L \) на \( y \) и \( L-y \), \( S \) увеличивается на \( y(L-y) \).

\( (\frac{1}{2} - S_{new}) - (\frac{1}{2} - S_{old}) = ( \frac{1}{2} - S_{old} - y(L-y) ) - (\frac{1}{2} - S_{old}) = -y(L-y) \).

Значит, \( \frac{1}{2} - S \) уменьшается на \( y(L-y) \).

Нам нужно доказать, что \( \frac{1}{2} - S \) всегда неотрицательно.

Изначально \( \frac{1}{2} - S = \frac{1}{2} ≥ 0 \).

В каждый момент \( \frac{1}{2} - S_{k+1} = \frac{1}{2} - S_k - l_{i1} l_{i2} \).

Так как \( l_{i1} l_{i2} ≤ \frac{l_i^2}{4} \), это не гарантирует, что \( \frac{1}{2} - S_{k+1} ≥ 0 \).

Снова обратимся к \( S = \frac{1 - ∑ l_i^2}{2} \).

\( ∑ l_i = 1 \). \( l_i > 0 \).

\( ∑ l_i^2 \) — это сумма квадратов положительных чисел, сумма которых равна 1.

Очевидно, что \( ∑ l_i^2 ≥ 0 \).

Поэтому \( 1 - ∑ l_i^2 ≤ 1 \).

\( S = \frac{1 - ∑ l_i^2}{2} ≤ \frac{1}{2} \).

Единственное, что нужно учесть, это то, что \( ∑ l_i^2 \) может быть равно 0 только если все \( l_i = 0 \), что противоречит \( ∑ l_i = 1 \).

Поэтому \( ∑ l_i^2 > 0 \).

Если \( ∑ l_i^2 \) очень мало (например, один кусок длины 1, остальные близкие к 0), то \( ∑ l_i^2 \) близко к 1. В этом случае \( S \) близко к 0.

Если \( ∑ l_i^2 \) максимально (много равных кусков), то \( ∑ l_i^2 \) стремится к 0 (при бесконечном числе кусков).

Ой, наоборот. Минимальное значение \( ∑ l_i^2 \) достигается при \( l_i = \frac{1}{n} \), и равно \( \frac{1}{n} \).

\( S = \frac{1 - \frac{1}{n}}{2} = \frac{n-1}{2n} \).

Как \( n \) растет, \( S \) приближается к \( \frac{1}{2} \).

Максимальное значение \( ∑ l_i^2 \) достигается, когда есть только один кусок длины 1. Тогда \( ∑ l_i^2 = 1^2 = 1 \). В этом случае \( S = \frac{1-1}{2} = 0 \).

Это говорит о том, что \( S ≤ \frac{1}{2} \) всегда верно, так как \( ∑ l_i^2 ≥ 0 \).

Доказательство:

Пусть \( l_1, l_2, …, l_n \) — длины всех частей каната после всех разрезаний. Тогда \( ∑_{i=1}^n l_i = 1 \) и \( l_i > 0 \) для всех \( i \).

Сумма чисел на доске \( S \) равна сумме произведений длин двух частей, полученных при каждом разрезании. Можно показать, что \( S = \frac{1 - ∑_{i=1}^n l_i^2}{2} \).

Так как \( l_i > 0 \) и \( ∑_{i=1}^n l_i = 1 \), то \( ∑_{i=1}^n l_i^2 ≥ 0 \).

Следовательно, \( 1 - ∑_{i=1}^n l_i^2 ≤ 1 \).

Тогда \( S = \frac{1 - ∑_{i=1}^n l_i^2}{2} ≤ \frac{1}{2} \).

Ответ: Доказано.