В базе данных есть несколько статей, каждая содержит не более 100 страниц. Руководитель поручает двум редакторам проверить все статьи, распределив их между собой (каждую статью целиком одному редактору). Оказалось, что при любом распределении хотя бы одному редактору достанется не более 80 страниц. Найдите максимальное общее количество страниц во всех статьях.

Разбираемся с задачей

Смотри, у нас есть несколько статей, и каждая из них может быть максимум 100 страниц. Их проверяют два редактора, и статьи не делятся – каждая идет целиком к одному из них. Знаем, что как бы мы ни распределили статьи, у одного из редакторов будет не больше 80 страниц.

Что нужно найти? Максимально возможное общее число страниц во всех статьях.

Логика решения

Давай представим, что у нас есть две статьи. Если мы отдадим одну статью первому редактору, а вторую – второму, то у каждого будет по одной статье. Если же мы отдадим обе статьи одному редактору, то у него будет две статьи, а у другого – ни одной.

Задача говорит, что при ЛЮБОМ распределении хотя бы одному редактору достанется не более 80 страниц. Это значит, что если бы у нас было, например, 160 страниц (две статьи по 80 страниц), то мы могли бы распределить их так: первый редактор берет 80 страниц, а второй – тоже 80 страниц. Но условие задачи говорит, что это невозможно, потому что хотя бы у одного должно быть НЕ БОЛЕЕ 80 страниц.

Представим, что у нас есть только одна статья. Мы можем отдать ее любому из двух редакторов. Если статья 100 страниц, то у одного редактора будет 100, а у другого 0. Это не подходит под условие «хотя бы одному достанется не более 80 страниц». Значит, одна статья не может быть 100 страниц, если мы хотим выполнить условие.

А если у нас две статьи? Допустим, статьи А и Б. Если мы отдадим обе статьи одному редактору, то у него будет А+Б страниц, а у второго 0. У второго 0 – это меньше 80, так что это условие выполняется. Значит, нужно найти такое максимальное общее число страниц, чтобы при любом распределении между двумя редакторами, один из них получил не более 80 страниц.

Пусть у нас есть N статей. Обозначим их количество страниц как $$S_1, S_2, ..., S_N$$.

Условие гласит, что для любого распределения статей между двумя редакторами (Редактор 1 и Редактор 2) существует хотя бы один редактор, у которого сумма страниц $$\le 80$$.

Представим себе самое «неравномерное» распределение, когда один редактор получает как можно больше страниц, а второй – как можно меньше.

Если бы у нас было две статьи, то суммарно могло бы быть максимум 100 + 100 = 200 страниц. Мы могли бы отдать одну статью (100 стр) первому редактору, а вторую (100 стр) — второму. Тогда у каждого будет по 100 страниц. Но это не удовлетворяет условию, что хотя бы у одного должно быть $$\le 80$$ страниц.

Подумаем иначе. Пусть максимальное общее количество страниц равно X. Мы делим эти X страниц между двумя редакторами.

Если бы мы могли распределить статьи так, чтобы у каждого редактора было более 80 страниц, это бы противоречило условию. Значит, какое бы распределение мы ни взяли, у одного из редакторов будет $$\le 80$$ страниц.

Рассмотрим крайний случай: у нас есть две статьи, каждая по 100 страниц. Общее количество страниц = 200. Мы можем дать обе статьи одному редактору, тогда у него будет 200 страниц, а у второго 0. В этом случае у второго редактора 0 страниц, что $$\le 80$$. Условие выполняется.

Но что если мы хотим найти максимальное общее количество страниц?

Пусть общее количество страниц равно X. Мы делим их между двумя редакторами. Пусть у первого редактора $$X_1$$ страниц, а у второго $$X_2$$ страниц. Причем $$X_1 + X_2 = X$$.

Условие: при любом распределении, $$\min(X_1, X_2) \le 80$$.

Рассмотрим случай, когда у нас есть статьи, которые в сумме дают 160 страниц. Например, две статьи по 80 страниц. Редактор 1 получает 80, Редактор 2 получает 80. $$\min(80, 80) = 80$$. Условие выполняется. Максимальное общее количество страниц тогда 160.

Что если одна статья 100 страниц, а другая 60? Общее = 160.

Варианты распределения:

1. Редактор 1: 100 стр, Редактор 2: 60 стр. $$\min(100, 60) = 60 \le 80$$. Условие выполняется.
2. Редактор 1: 60 стр, Редактор 2: 100 стр. $$\min(60, 100) = 60 \le 80$$. Условие выполняется.

Получается, что если общее число страниц равно 160, мы можем найти такое распределение, что у каждого редактора будет не более 80 страниц, или у одного из них будет меньше 80 страниц.

Давайте проверим, может ли общее количество страниц быть больше 160.

Предположим, общее количество страниц X. Если мы можем найти такое распределение, что $$X_1 > 80$$ И $$X_2 > 80$$, то это противоречит условию. Значит, для любого распределения $$X_1 + X_2 = X$$, обязательно $$X_1 \le 80$$ ИЛИ $$X_2 \le 80$$.

Это означает, что невозможно, чтобы оба редактора получили более 80 страниц. То есть, невозможно, чтобы $$X_1 > 80$$ И $$X_2 > 80$$.

Если $$X_1 > 80$$ и $$X_2 > 80$$, то $$X_1 + X_2 > 80 + 80 = 160$$.

Следовательно, чтобы условие выполнялось, не должно существовать такого распределения, при котором оба редактора получают более 80 страниц. Это значит, что общее количество страниц X не может быть таким, чтобы можно было найти $$X_1, X_2$$ (соответствующие суммарному количеству страниц статей) такие, что $$X_1 > 80$$ и $$X_2 > 80$$.

Самое большое число страниц, которое может быть у одного редактора, если общее число страниц X, это X (если весь объем отдаем одному). Но это противоречит условию, если X > 80.

Давайте вернемся к условию: «при любом распределении хотя бы одному редактору достанется не более 80 страниц».

Если бы общее количество страниц было, скажем, 161. Тогда мы могли бы распределить их как 81 и 80. В этом случае у первого редактора 81 страница, что больше 80. У второго 80 страниц, что $$\le 80$$. Условие выполняется.

А если общее количество страниц 170? Мы могли бы распределить как 100 и 70. У второго 70 $$\le 80$$. Условие выполняется.

Что если 200 страниц? Распределяем как 100 и 100. У первого 100 > 80. У второго 100 > 80. Вот это уже противоречие!

Значит, общее количество страниц не может быть таким, чтобы при любом распределении оба редактора получили больше 80 страниц.

Если общее количество страниц X, и мы можем найти такое распределение $$X_1, X_2$$ ($$X_1+X_2=X$$), что $$X_1 > 80$$ и $$X_2 > 80$$, то это неверно.

Следовательно, для любого распределения $$X_1, X_2$$ должно выполняться: $$X_1 \le 80$$ или $$X_2 \le 80$$.

Представим, что у нас есть две статьи: одна на 100 страниц, другая на 100 страниц. Общее = 200.

Если редактор 1 берет обе статьи, у него 200 страниц ( > 80), у редактора 2 - 0 страниц ( $$\le 80$$). Условие выполняется.

Если редактор 1 берет одну статью (100 стр), а редактор 2 – другую (100 стр), то у обоих по 100 страниц. Оба > 80. Это противоречие!

Значит, мы не можем иметь две статьи по 100 страниц. Максимальное количество страниц в одной статье – 100.

Пусть общее количество страниц равно X. Если $$X > 160$$, то всегда найдется такое распределение, что у каждого будет больше 80 страниц.

Доказательство: Пусть $$X > 160$$. Мы можем представить $$X$$ как $$X_1 + X_2$$, где $$X_1$$ и $$X_2$$ – это суммы страниц статей, которые мы распределяем.

Если общее количество страниц X, то мы можем разбить его на две части $$X_1$$ и $$X_2$$ ($$X_1 + X_2 = X$$). Условие, что при любом распределении хотя бы один редактор получает $$\le 80$$, эквивалентно тому, что не существует такого распределения, при котором оба редактора получают $$> 80$$ страниц.

То есть, не должно быть такого, что $$X_1 > 80$$ И $$X_2 > 80$$.

Если $$X_1 > 80$$ и $$X_2 > 80$$, то $$X_1 + X_2 > 160$$.

Значит, если общее количество страниц X больше 160, то возможно найти такое распределение, что $$X_1 > 80$$ и $$X_2 > 80$$. Но это противоречит условию.

Поэтому, общее количество страниц X не может быть больше 160.

Максимальное общее количество страниц, при котором условие выполняется, это 160.

Пример:

У нас есть две статьи. Статья 1 = 80 страниц. Статья 2 = 80 страниц. Общее = 160 страниц.

Распределения:

1. Редактор 1: Статья 1 (80 стр). Редактор 2: Статья 2 (80 стр). У обоих по 80 страниц. $$\min(80, 80) = 80 \le 80$$. Условие выполняется.

Другой пример:

У нас есть три статьи: 50, 50, 60 страниц. Общее = 160 страниц.

Распределения:

1. Редактор 1: 50, 50 (100 стр). Редактор 2: 60 стр. $$\min(100, 60) = 60 \le 80$$. Условие выполняется.
2. Редактор 1: 50, 60 (110 стр). Редактор 2: 50 стр. $$\min(110, 50) = 50 \le 80$$. Условие выполняется.
3. Редактор 1: 60 стр. Редактор 2: 50, 50 (100 стр). $$\min(60, 100) = 60 \le 80$$. Условие выполняется.

Почему не больше 160?

Если бы общее количество страниц было, например, 161. И эти 161 страницы были бы, скажем, одной статьей. Тогда один редактор получает 161 стр (> 80), другой 0 стр ($$\le 80$$). Условие выполняется.

Но тут есть нюанс: «каждая содержит не более 100 страниц».

Если у нас две статьи: 100 стр и 61 стр. Общее = 161 стр.

Распределения:

1. Редактор 1: 100 стр. Редактор 2: 61 стр. $$\min(100, 61) = 61 \le 80$$. Условие выполняется.
2. Редактор 1: 61 стр. Редактор 2: 100 стр. $$\min(61, 100) = 61 \le 80$$. Условие выполняется.

Что если у нас три статьи: 100, 31, 30 страниц. Общее = 161 стр.

Распределения:

1. Редактор 1: 100 стр. Редактор 2: 31+30 = 61 стр. $$\min(100, 61) = 61 \le 80$$. Условие выполняется.
2. Редактор 1: 100+31 = 131 стр. Редактор 2: 30 стр. $$\min(131, 30) = 30 \le 80$$. Условие выполняется.
3. Редактор 1: 100+30 = 130 стр. Редактор 2: 31 стр. $$\min(130, 31) = 31 \le 80$$. Условие выполняется.
4. Редактор 1: 31+30+100 = 161. Редактор 2: 0. $$\min(161, 0) = 0 \le 80$$. Условие выполняется.

Кажется, я упустил что-то важное.

«при любом распределении хотя бы одному редактору достанется не более 80 страниц»

Пусть общее количество страниц равно X. Разделим X на две части $$X_1$$ и $$X_2$$ ($$X_1 + X_2 = X$$). Если мы можем найти такое распределение, что $$X_1 > 80$$ И $$X_2 > 80$$, то это противоречие.

Значит, не должно существовать такого распределения, где оба редактора получают больше 80 страниц.

Самый «худший» случай для выполнения условия – это когда мы можем разделить общее количество страниц X на две части, каждую из которых можно выдать одному редактору, и обе части будут больше 80.

Если X = 160. Мы можем распределить как 80 и 80. Оба $$\le 80$$. Условие выполняется.

Если X = 161. Мы можем распределить как 100 (статья 1) и 61 (статья 2). Тогда у редакторов 100 и 61. $$\min(100, 61) = 61 \le 80$$. Условие выполняется.

Если X = 170. Можно распределить как 100 и 70. $$\min(100, 70) = 70 \le 80$$. Условие выполняется.

Если X = 200. Можно распределить как 100 и 100. У обоих по 100 страниц, что > 80. Это противоречие!

Значит, общее количество страниц X не может быть таким, чтобы существовало распределение $$X_1, X_2$$ ($$X_1+X_2=X$$) такое, что $$X_1 > 80$$ и $$X_2 > 80$$.

Максимальное значение X, для которого это условие НЕ нарушается, это 160.

Представим, что у нас есть статьи, суммарно дающие 161 страницу. И мы можем распределить их так, чтобы у каждого было больше 80 страниц. Но условие говорит, что так НЕ должно быть.

Значит, общее количество страниц X должно быть таким, чтобы НЕВОЗМОЖНО было найти такое распределение $$X_1, X_2$$ (соответствующее суммам страниц статей), что $$X_1 > 80$$ и $$X_2 > 80$$.

Если X = 160, то мы можем распределить как 80 и 80. Оба $$\le 80$$. Условие выполняется.

Если X = 161, то мы можем распределить статьи так, что у первого редактора будет 81 страница, а у второго 80. Тогда $$\min(81, 80) = 80 \le 80$$. Условие выполняется.

Если X = 161, и статьи такие, что мы можем распределить их как 80.5 и 80.5 (что невозможно, страницы целые).

Попробуем рассуждать от противного. Допустим, максимальное общее количество страниц X > 160. Тогда мы можем найти такое распределение статей, что оба редактора получат более 80 страниц. Это прямое нарушение условия.

Следовательно, X не может быть больше 160.

Максимальное значение X равно 160.

Проверка:

Если общее количество страниц = 160.

1. Две статьи по 80 страниц. Редактор 1: 80, Редактор 2: 80. $$\min(80, 80) = 80 \le 80$$. OK.
2. Статья 100 страниц, статья 60 страниц. Редактор 1: 100, Редактор 2: 60. $$\min(100, 60) = 60 \le 80$$. OK.
3. Статья 90 страниц, статья 70 страниц. Редактор 1: 90, Редактор 2: 70. $$\min(90, 70) = 70 \le 80$$. OK.

Если общее количество страниц = 161.

1. Статья 100 страниц, статья 61 страница. Редактор 1: 100, Редактор 2: 61. $$\min(100, 61) = 61 \le 80$$. OK.
2. Статья 100 страниц, статья 60 страниц, статья 1 страница. Редактор 1: 100, Редактор 2: 60+1=61. $$\min(100, 61) = 61 \le 80$$. OK.
3. Редактор 1: 100+1 = 101, Редактор 2: 60. $$\min(101, 60) = 60 \le 80$$. OK.
4. Редактор 1: 60+1 = 61, Редактор 2: 100. $$\min(61, 100) = 61 \le 80$$. OK.

А если статьи такие, что мы можем разбить 161 на две части > 80? Например, если у нас есть статьи, которые в сумме дают 161 страницу, и мы можем распределить их так, что одному достанется 81, а другому 80. То есть, 81 > 80, но 80 $$\le 80$$. Условие выполняется.

Ключевая фраза: «при любом распределении хотя бы одному редактору достанется не более 80 страниц».

Это означает, что НЕВОЗМОЖНО найти такое распределение, при котором оба редактора получили бы более 80 страниц.

Пусть общее количество страниц равно X. Если мы можем разделить X на $$X_1$$ и $$X_2$$ так, что $$X_1 > 80$$ И $$X_2 > 80$$, то это нарушает условие. Значит, такого распределения быть не должно.

Сумма $$X_1 + X_2$$ должна быть такой, чтобы НЕ БЫЛО возможности выбрать $$X_1 > 80$$ и $$X_2 > 80$$.

Если $$X_1 > 80$$ и $$X_2 > 80$$, то $$X_1 \text{ (минимальное целое)} = 81$$ и $$X_2 \text{ (минимальное целое)} = 81$$.

Сумма $$X_1 + X_2$$ в таком случае будет минимум $$81 + 81 = 162$$.

Если общее количество страниц X равно 162 или больше, то МОЖНО найти такое распределение, где у обоих редакторов будет больше 80 страниц. Пример: если статьи суммарно дают 162 страницы, мы можем раздать их так, что одному достанется 81, а другому 81. Это нарушит условие.

Значит, максимальное общее количество страниц X должно быть меньше 162.

Максимальное целое число, которое меньше 162, это 161.

Проверим 161:

Пусть общее количество страниц = 161. Можем ли мы распределить их так, чтобы у обоих было > 80?

Если мы разделим 161 на две части, то одна часть будет $$\ge$$ 81, а другая $$\le$$ 80 (если делить 161/2 = 80.5).

Например, 81 и 80. Тогда у одного 81 (>80), у другого 80 ($$\\le 80$$). Условие выполняется, так как у одного $$\le 80$$.

Но мы должны учитывать, что страницы — это статьи, и статьи не делятся.

Пусть у нас есть статьи, суммарно дающие 161 страницу. Например: одна статья 100 стр, другая 61 стр.

Распределения:

1. Редактор 1: 100 стр. Редактор 2: 61 стр. У первого 100 (>80), у второго 61 ($$\\le 80$$). Условие выполняется.
2. Редактор 1: 61 стр. Редактор 2: 100 стр. У первого 61 ($$\\le 80$$), у второго 100 (>80). Условие выполняется.

А если статьи 81, 80? Тогда у одного 81 (>80), у другого 80 ($$\\le 80$$). Условие выполняется.

А если статьи 82, 79? У одного 82 (>80), у другого 79 ($$\\le 80$$). Условие выполняется.

А если статьи 90, 71? У одного 90 (>80), у другого 71 ($$\\le 80$$). Условие выполняется.

Ключевая идея: Если общее количество страниц X, и мы можем найти такое распределение $$X_1, X_2$$ ($$X_1 + X_2 = X$$), что $$X_1 > 80$$ и $$X_2 > 80$$, то это противоречие. Значит, такого распределения быть не должно.

Это означает, что максимальная сумма, которую можно получить, если оба редактора получают более 80 страниц, не должна достигаться.

Если общее количество страниц X, то $$X_1 + X_2 = X$$. Если X = 160, мы можем получить 80 + 80. Оба $$\le 80$$.

Если X = 161, то любая пара $$X_1, X_2$$ такая, что $$X_1+X_2=161$$ будет либо (81, 80), либо (80, 81), либо (100, 61) и т.д. В каждом случае одно из чисел $$\le 80$$.

Если общее количество страниц Х, то либо $$X_1 \text{ (одной из статей)} \text{или их суммы} \text{ будет} > 80, \text{либо} X_2 > 80$$.

Или, другими словами: Невозможно, чтобы $$X_1 > 80$$ и $$X_2 > 80$$ одновременно.

Если $$X_1 > 80$$ и $$X_2 > 80$$, то $$X_1 \text{ (min)} = 81$$ и $$X_2 \text{ (min)} = 81$$. Тогда $$X_1 + X_2 \text{ (min)} = 162$$.

Значит, если общее количество страниц X будет 162 или больше, то ГАРАНТИРОВАННО найдется такое распределение, где оба редактора получат более 80 страниц. Это нарушает условие.

Следовательно, общее количество страниц X не может быть 162 или больше.

Максимальное возможное общее количество страниц равно 161.

Пример:

Общее количество страниц = 161.

Статьи: 100 страниц, 61 страница.

Распределение 1:

Редактор 1: 100 страниц ( > 80)

Редактор 2: 61 страница ( $$\le 80$$)

Условие выполнено (у второго редактора $$\le 80$$).

Распределение 2:

Редактор 1: 61 страница ( $$\le 80$$)

Редактор 2: 100 страниц ( > 80)

Условие выполнено (у первого редактора $$\le 80$$).

Почему 162 не подходит?

Пусть общее количество страниц = 162.

Статьи: 100 страниц, 62 страницы.

Распределение 1:

Редактор 1: 100 страниц ( > 80)

Редактор 2: 62 страницы ( $$\le 80$$)

Условие выполнено.

Статьи: 81 страница, 81 страница.

Распределение:

Редактор 1: 81 страница ( > 80)

Редактор 2: 81 страница ( > 80)

Оба редактора получили более 80 страниц! Это прямое нарушение условия задачи.

Значит, общее количество страниц не может быть 162.

Максимальное общее количество страниц — 161.

Ответ: 161