задачка про огурцы

[avva]

Рассказали отличную задачку с очень простым условием. Вроде раньше не сталкивался с ней.

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

Рассказавший мне эту задачу приятель добавил также, что "есть простое решение, которое можно придумать и объяснить, ничего не записывая на бумаге".

Comments

[kikzan.livejournal.com]

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

[avva.livejournal.com]

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

[revliscap.livejournal.com]

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

[avva.livejournal.com]

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

[utnapishti.livejournal.com]

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

[avva.livejournal.com]

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

[arctic-fox-1480.livejournal.com]

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

[avva.livejournal.com]

Да!

[xboctram.livejournal.com]

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

[natomist.livejournal.com]

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

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

[gg59.livejournal.com]

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

[utnapishti.livejournal.com]

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

[(Anonymous)]

каждый день мы съедаем минимум по 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 огурцов.

[baca6u.livejournal.com]

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

[(Anonymous)]

Пусть 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, противоречие.

[botev.livejournal.com]

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

[ok-66.livejournal.com]

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

[moon-aka-sun.livejournal.com]

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

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

[ok-66.livejournal.com]

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

[dmitrmax.livejournal.com]

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

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

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

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

[uleysky.blogspot.com (from livejournal.com)]

Задачу можно сформулировать в общем виде. 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. При решении, действительно, не пострадала ни одна бумажка, так как цепочка шариков и операции над ней легко представимы в уме )

[old-radist.livejournal.com]

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

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

[mikev.livejournal.com]

расположим огурцы последовательно в порядке поедания и перенумеруем натуральными числами от 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.

[vnesov.livejournal.com]

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

[(Anonymous)]

Пусть 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 огурцов (или меньше) на оставшиеся две недели, а по условию задачи мы должны съедать не менее огурца в день.

[larisaka.livejournal.com]

О, помню, я один раз была на такой диете, только там были не огурцы, а капуста, то есть капустный суп, а остальное точь-в точь. Решения не помню, даже если оно и было, потому что соображать перестаешь день на четвертый.

[al-evilproof.livejournal.com]

Самый простой и тупой, сразу, устно:

28 огурцов минимум съедаем по любому. Надо 42.
За первые 13 дней съели 13.
Осталось 15 дней за которые надо съесть 29 огурцов.
Жуем 14 дней по 2 в день и в последний день один последний огурец.

[lenamarkova.livejournal.com]

42 огурца за 28 дней, но минимум один в день - это например14 дней по 2 огурца и 14 по одному.
Если 14 по 2 есть подряд, то в 14 по одному будет промежуток, где есть 13 огурцов. Если 14 по 2 разбавить днями по 1, то тоже получается 13. Но даже если к ряду 14 по 2 присоединить ряд где по одному, то на стыке рядов получится 12+1.
Если есть по 3 огурца в день подряд, то это будет 7 дней, остальное образует ряд по 1 огурцу, там можно найти 13 подряд, или к 12 (3х4) опять же добавляется 1 из ряда, где по одному.
Если есть по 4, то тоже получится либо 12+1, либо 13 в ряду по 1, но в любом случае, если смешивать по 2 и больше, останется больше, чем 13 по одному подряд, и единичек достаточно, чтобы 13 огурцов получилось в любой из разбитых единичками комбинаций для 42 огурцов за 28 дней.

[(Anonymous)]

42 - 28 = 14, т.е. половину дней я ем 1 огурец и половину 2, и никак иначе. А дальше - из 28 двоек и единиц по-любому можно набрать 13 подряд (и даже несколькими способами).

[ravli.livejournal.com]

это я был

всё-таки странно,

[a-shen.livejournal.com]

оценка кажется излишне большой: если у нас в интервале 0..42 выбираются точки, при этом нельзя выбрать отличающихся на 13, то в каждой группе 0-13-26-39 1-14-27-40 2-15-28-41 3-16-29-42б 4-17-30 5-18-31...12-25-38 можно выбрать по две точки, всего 26 точек, то есть максимально возможное число дней 25 (а не 27, как было бы, если оценка в задаче была бы точной) 

[timur0.livejournal.com]

Рассмотрим количество съеденных огурцов нарастающим итогом, т.е. сколько съел всего на этот день. Рассмотрим остатки от деления этих чисел на 13. Всего есть 28 остатков, значит какой-то остаток встретится три раза. Разности будут кратны 13; если одна из разностей 13, то все доказано. Если нет, то это 26 и 39, а их разность как раз 13, что нам и нужно.

[huzhepidarasa.livejournal.com]

Положим, что ни одного такого промежутка нет.

Поскольку он съедал по крайней мере 1 огурец в день, то

- количество огурцов, съеденных за первый день
- количество огурцов, съеденных за первые два дня
- количество огурцов, съеденных за первые три дня
...
- количество огурцов, съеденных за первые 28 дней (= 42)

будут все разные, итого 28 чисел от 1 до 42.

Далее, никакая пара этих чисел не отличается ровно на 13. Поэтому

- количество огурцов, съеденных за первый день. плюс 13
- количество огурцов, съеденных за первые два дня, плюс 13
...
- количество огурцов, съеденных за первые 28 дней, плюс 13 (= 42+13 = 55)

тоже все разные числа, и все попарно отличаются от предыдущих 28 чисел.

Итого есть 56 разных чисел от 1 до 55.

Вот и опаньки.

тест

[(Anonymous)]

Тоже так решил.
Есть 28 разных чисел от 1 до 42. Доказать, что найдутся два с разницей 13. Рассмотрми остаток от деления на 13. Всего 28 чисел (28 = 13 + 13 + 2), значит, найдутся 3 числа с одинаковым остатком. Максимально чисел с одинаковым остатком может быть 4 (т.к. 4 * 13 больше 42). имеем <= 4 корзинки и в них 3 яблока. Очевидно, найдутся 2 яблока, лежащих рядом.

[(Anonymous)]

В комментариях есть "математические" решения, но по условию нужно ведь решение Простое!

Представим себе ряд из 28 дней, в каждый из которых съедено по одному огурцу. В таком ряду безусловно есть 13 дней подряд с 13 съеденными огурцами. Но у нас остаётся ещё 14 огурцов, чтобы добавить.

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

[huzhepidarasa.livejournal.com]

Вы забыли про слово «подряд».

[anton likhtarov (from livejournal.com)]

Представим ряд из 42 огурцов. Нам нужно расставить 27 "границ" между днями в позициях после 1го, 2го, ..., 41го огурца. Рассмотрим остатки от деления на 13. Начало и конец в позициях 0 и 42, так что из позиций 13, 26, 39 можно выбрать только одну (26 или 39), так же одну из 3, 16, 29 (3 или 16). Для позиций 1, 14, 27, 40 можно выбрать максимум две границы. Тоже самое для 2, 15, 28, 41. Для 4, 17, 30, и так далее до 12, 25, 38 можно так же выбрать по две. В результате можно расставить максимум 12*2 + 2 = 26 границ, на одну меньше чем требуется.

[anton likhtarov (from livejournal.com)]

Похоже 3, 16, ... посчитал дважды, так что работает даже для 26-и дней