То есть, как ни ешь огурцы, но если съесть 42 за 28 дней, обязательно будет промежуток целого количества дней, за который съедено 13 огурцов?

Именно так, только вы забыли условие про минимум 1 каждый день. Кроме того, нет никаких подвохов типа огурца, съеденного наполовину в один день и наполовину в другой. Все "честно". 28 целых чисел, каждое из которых не меньше 1, сумма 42, найдется идущая подряд выборка с суммой 13.

Edited at 2016-07-12 10:40 (UTC)

28+13=41, то есть такой промежуток существует в пределах 42 дней

Я не очень понял ваш комментарий :) но дней вообще-то 28.

В смысле, ровно 13, верно?

Да, сейчас добавлю это слово.

нужно доказать невозможность распределения огурцов таким образом чтобы не получался ряд дней насчитывающий 13 огурцов?

Да!

13 огурцов= 5 дней подряд по 2 и 3 дня по одному

В самом худшем случае я могу 14 дней есть по 2 огурца, а 14 дней по одному огурцу. Как не чередуй эти дни все равно будет достаточно единиц в ряду, что бы найти интервал который в сумме даст 13. Если я в какой-то день съем больше 2-х огурцов, то количество единиц в ряду станет ещё больше.
Вот такое мое не строгое доказательство.

Конечно в идеале бы нужно предположить, что существует такой ряд из 28 чисел, которые бы дали бы в сумме 42 и на котором бы не возможно было бы выделить субряд, который давал бы в сумме 13, потом найти противоречия... Но то не ко мне, наверно, а к какому-нибудь Гаусу или Фурье.

Если мы в течение 28-ми дней каждый день едим по огурцу, то у нас набирается 16 промежутков, когда огурцов съедается тринадцать: с 1 по 13 день, со 2 по 14, с 3 по 15, и т.д., с 16 по 28.
Оставшимися огурцами мы можем "испортить" только 14 таких промежутков (42 - 28 = 14 оставшихся у нас огурцов).
Это значит, что промежутков с 13 огурцами всегда будет как минимум два.

они же пересекаются, эти промежутки
как правило, один "дополнительный" огурец испортит сразу несколько промежутков

каждый день мы съедаем минимум по 1 огурцу.

возьмем дни с 1 по 13. Как нам испортить это промежуток? Берем максимально затрагивающий остальные промежутки вариант - съедаем в 13-й день 2 огурца.

теперь берем промежуток с 2 до 14. мы знаем что в 13-й день мы хотим съесть 2 огурца. значит на само деле промежуток со второго дня закончится раньше - на 13-день. как нам его испортить? съесть на 13-й день не 2 а 3 огурца.

и т.д.

с 3 дня съедаем на 13 4
с 4 - 5
с 5 - 6
...
с 12 - 13.

получили на 13 день интервал в один день с 13 огурцами. надо его испортить. съедаем 14 огурцов на 13 день.

итого мы съели 13 дополнительных огурцов. и смогли испортить только 13 интервалов. остался один огурец и последовательность из 15 дней по одному огурцу. в какой бы день его не съесть найдется промежуток в 13 огурцов.

Съев в 13 день два огурца мы не портим промежуток с 1 по 13, мы создаем промежуток со 2-го по 13 день в который мы съедаем 13 огурцов. Не годится. Чтобы испортить этот промежуток достаточно хорошо, надо съесть на 13-й день 14 огурцов. Получается с 1-го по 12-й - 12 огурцов, в 13-й - 14. Итого получается 26 огурцов за 13 дней. Остается промежуток с 14-го по 28 в который у нас есть 42-26=16 огурцов за 14 дней. То есть по одному каждый день и еще два добавочных в один или два дня. Куда бы мы их (эти два лишних) не поставили, промежуток с 13-ю огурцами будет точно, слишком много единиц.
Вторая часть, конечно, не слишком строгая, но я зуб даю, что это так.

Пусть s_i - число огурцов, съеденных за первые i дней(i = 0..28). Все s_i - различные целые числа от 0 до 42 включительно. Нам нужно доказать, что обязательно найдутся i, j такие, что s_j - s_i = 13.

Рассмотрим следующие пары чисел: 0-13, 1-14, 2-15,..., 12-25, 26-39, 27-40, 28-41, 29-42(всего 13 + 4 = 17 пар), они не пересекаются, кроме того числа с 30 по 38 остались без пары(9 чисел). Если требуемых i, j не существует, то из каждой пары в s_i-х может быть не более одного числа, поэтому всего чисел может быть не более 17+9=26, а у нас их 29, противоречие.

это смотря какие огурцы, конечно. бывают такие огурцы, что одним на целый день наедаешься, а бывают и такие, что хоть десять штук съешь, все одно через час снова жрать охота. бывает еще, откусишь — и видишь, что горький. с другого конца откусишь — может быть не горький, а может быть снова горький! так вот и выкинешь огурец, а он денег стоит. опять же соленые, малосольные, маринованные — это все тоже необходимо учитывать. можно еще в салат порезать, хотя я не очень люблю. лучше уж вообще без огурцов, ну их нахуй.

У Носова эта тема подробно раскрыта.

Тут приходит программист. Напишем программу, которая перебирает все варианты разбиения 42 огурцов на 28 дней...
__

28 о за 28 д - всё ок. Теперь можем ли мы разместить 14 о, чтоб испортить расклад? Если портить с одного конца, то с другого всё будет ок. Надо портить в середине. Все 14 сразу - не получается, всё равно остаётся одиночный конец. Вплотную 7 и 7 - тоже не выход. Остаётся найти, как 7 могут испортить 14 дней. Думаю, в этом направление надо двигаться...

Семь и семь ничего испортить не могут. Ведь дней не обязательно должно быть 13.

Edited at 2016-07-12 16:30 (UTC)

Запишем на бумаге кол-во огурцов, которые я съел в во все дни по порядку слева направа. Далее идем по этому ряду окном.

Шаг 1. Двигаем вначале правый край окна пока в окне не наберется 13 или более огурцов. Если нашли 13, то задача решена. Если в окне больше 13, то переходим к Шагу 2.

Шаг 2. Передвигаем левый край окна, выкидывая из него дни, пока в окне не останется 13 огурцов или меньше. Если нашли 13, то задача решена. Если меньше, переходим к Шагу 1.

Если на шаге 2 мы будем из окна выкидывать только дни содержащие 1 огурец, то мы непременно получим 13 огурцов в окне. Следовательно, переход из шага 2 к шагу 1 возможен тогда и только тогда, когда из окна вылетел хотя бы один день, содержащие более 1 огурца. Всего таких дней не может быть более 14. Следовательно после 14 перехода к шагу 1, в окне останутся только дни с одним огруцом. То есть мы обязательно найдем такой промежуток обязательно не далее 14-го шага.

Задачу можно сформулировать в общем виде. 3k огурцов съедается за 2k дней, не менее, чем один огурец в день. Нужно показать, что существует непрерывный интервал с ровно k-1 съеденными огурцами (на самом деле, их, минимум, два).

Пусть у нас есть 3k шарика на кольцевой леске. У нас существует 3k группы последовательно идущих шариков по k-1 штук в каждой. Начнём слеплять шарики в большие, каждый раз по двое. После k слеплений у нас останется 2k шариков общей массой 3k, то есть условие, аналогичное огурцам (но пока на кольцевой леске!).

Что происходит при слеплении пары шариков? Очевидно, пропадают два интервала, началом и концом которых служит промежуток между слипшимися шариками. Таким образом, после k слеплений у нас на кольцевой леске останется ровно 3k-2*k=k интервалов, в которых сумма шариков равна k-1.

Теперь разрежем леску в произвольном месте. Такой разрез уничтожит ещё часть наших интервалов. Но, один разрез не может уничтожить больше k-2 интервалов (интервал максимальной длины - k-1, количество промежутков в нём - k-2). Следовательно, у нас останется, как минимум, k-(k-2)=2 интервала с суммой шариков, равной k-1.

Небольшая проверка: k=2, число огурцов - 3k=6, число дней - 2k=4. Существование, как минимум, двух дней, в которые съедается ровно k-1=1 огурец, очевидно.

P.S. При решении, действительно, не пострадала ни одна бумажка, так как цепочка шариков и операции над ней легко представимы в уме )

Edited at 2016-07-12 12:43 (UTC)

>> 3k огурцов съедается за 2k дней...

Однако у вас масштабы!..

расположим огурцы последовательно в порядке поедания и перенумеруем натуральными числами от 1 до 42. Некоторые последовательно идущие пары огурцов (с номерами i и i+1) съедались в один день (пары первого рода), а некоторые в два последовательных дня (пары второго рода). Ясно, что пар первого рода было ровно 14.
Теперь возьмем 13 огурцов подряд, начиная с i-го и кончая i+12-ым. Поскольку i может принимать значения от 1 до 42-12=30, то таких отрезков 30, и никакие три из них не имеют общего конца. Если среди двух пар (i-1,i) и (i+12,i+13) нет пар первого рода, то утверждение доказано. Но для того, чтобы у каждого из 30 отрезков на конце была пара первого рода, таких пар нужно хотя бы 15, а их всего 14.

А если 27 дней, 50 огурцов?

Edited at 2016-07-12 13:55 (UTC)

Пусть x[i] - общее количество огурцов, съеденных к концу i-того дня. x[0] = 0, x[28] = 42. Последовательность монотонно возрастает. Иными словами, в ней (не считая ноль) 28 различных чисел из [1, 42].

Допустим, что не существущет такого промежутка, за который было съедено 13 огурцов, то есть для любых i и j (i < j) x[j] - x[i] != 13.

Следовательно, в последовательности не может встретиться число 13 (Если x[j] = 13, то x[j] - x[0] = 13). Аналогично, в ней не может встретиться число x[1] + 13, x[2] + 13 и так далее. Здесь стоит вспомнить, что у нас 28 чисел от 1 до 42 включительно - то есть, если посмотреть на это с другой стороны, в диапазоне 1..42 есть только 14 чисел, которые не встречаются в этой последовательности. Поэтому у нас нет возможности слишком уж много чисел (меньших 42) исключить из последовательности - максимум мы можем исключить 14. Это означает, что x[14] > 29 - в этом случае, начиная с этого числа мы будем исключать числа, большие 42. Но тогда у нас останется всего 12 огурцов (или меньше) на оставшиеся две недели, а по условию задачи мы должны съедать не менее огурца в день.