Привычка все усложнять...

[pcyanide]

До чего же маститые ученые привыкли все усложнять! Таких случаев я находил множество, и очень жалею, что не набрел на dxdy сайт раньше, так как обязательно поделился бы. Но, better later than never!

Сегодня, находясь в романтическом предновогоднем настроении (и это несмотря на изнывающую австралийскую жару!) набрел на публикацию: 16 веселых приложений принципа Дирихле. Повеселимся и мы по поводу задачи 13 (и не только из-за ее номера):

Гари тренируется в троеборье. Он тренировался в течение каждого из 30 дней, выполнив всего 45 тренировок. Доказать, что найдется несколько последовательных дней, в течение которых он выполнил в точности 14 тренировок.

Вот решение, вычерпанное автором публикации из конспектов некоего профессора Gary MacGillivray:

Пусть $S_i$ суммарное количество тренировок за первые $i$ дней. ($S_1$ за 1-й день, $S_2$ — за 1й+2й и т.д).
Поскольку тренировки имели место каждый день,

$$ 1 \le S_1 < S_2 < ... < S_{30} = 45 \qquad (1) $$

Прибавив к каждому члену неравенств по 14, получим:

$$ 15 \le S_1+14 < S_2+14 < ... < S_{30}+14 = 59 $$

Объединив числа из множеств $\{S_i\}$ и $\{S_i+14\}$, получаем 60 целых положительных чисел, не превосходящих 59 отсюда ( вследствие того самого принципа) следует, что в этом множестве найдется два равных числа. Так как оба множества состоят из различных элементов, равные числа должны быть из различных множеств: $S_i = S_j + 14$, или $S_i - S_j = 14$. Так как $(S_i - S_j)$ — это количество тренировок за $(i-j)$ последовательных дней от $i+1$-го по $j$-й, утверждение доказано.

Как хитро! Никогда бы не сообразил!

———————————————————————————————————————————————————————

А если в сумме не 45, а 55 тренировок? Заменим (1) на

$$ 1 \le S_1 < S_2 < ... < S_{30} = 55 \qquad (2) $$

60 чисел в диапазоне от 1 до 69? Да здесь не то, что голуби, даже более возвышенные принципы не помогут!

Однако буду рассуждать не как высокооплачиваемый американский профессор, а как человек без ученной степени и со скудной прибылью, зато с российским менталитетом.

Рассмотрим остатки от деления $\{S_i\}$ на 14. Имеем 30 чисел и 14 возможных остатков. Вот где они, наши голубиные ячейки! Выходит, что три числа $S_i$, $S_j$ и $S_k$ ($i<j<k$) дают одинаковые остатки при делении на 14. Таким образом, $b_1 = S_j-S_i$ и $b_2 = S_k-S_j$ делятся на 14. Так как числа ${b_1}$, ${b_2}$ положительные, их значения не меньше 14.

Допустим $b_1>14$ и $b_2>14$, тогда $b_1 \ge 28$ и $b_2 \ge 28$ и следовательно $b_1 + b_2 \ge 56$. Но позвольте, ведь $(b_1 + b_2)$ — это не что иное, как $(S_k - S_i)$, в то время как $S_k - S_i \ge 56$ уж никак не вяжется с (2). Таким образом, наше предположение неверно, отсюда одно из чисел $b_1= S_j-S_i$ и $b_2=S_k-S_j$ равно 14, что из завершает доказательство.

———————————————————————————————————————————————————————

Надеюсь, не я один встречал подобные ляпсусы.

———————————————————————————————————————————————————————

Merry Christmas and Happy New Year!

[kotenok gav]

pcyanide в сообщении #1276304 писал(а):

Надеюсь, не я один встречал подобные ляпсусы.

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

[Red_Herring]

pcyanide в сообщении #1276304 писал(а):

высокооплачиваемый американский профессор

Канадский из Университета Виктория, Британская Колумбия

[pcyanide]

kotenok gav в сообщении #1276317 писал(а):

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

Ошибок, конечно нигде нет. Но первое доказательство выглядит несколько неестественным, к тому не покрывает случая с 55. Вторым методом можно доказать, как с 45, так и с 55 или 56.

[grizzly]

pcyanide в сообщении #1276329 писал(а):

Но первое доказательство выглядит несколько неестественным, к тому не покрывает случая с 55.

Как это? я даже не читая доказательство, могу сказать, что если за 30 дней было проведено 55 (или 56) тренировок, следовательно и 44 тоже было. Имеем "пустой чайник" и предыдущую задачу (точнее -- см. ниже)

[slavav]

grizzly, вы ошиблись. Например, если за 30 дней было проведено 90 тренировок, следовательно и 44 тоже. Но если каждый день по три тренировки, то 14 не составить.

[grizzly]

slavav
А, ну да, там "в точности 14". Значит, глупость сказал, не вникнув. Спасибо!

[pcyanide]

Если рассуждать с чисто математической точки зрения, то противоречие вызвано $S_k - S_i \ge 56$, и это противоречие сохраняется при любом количестве тренировок, не превосходящем 56.