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

[avva]

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

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

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

Comments

[kikzan.livejournal.com]

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

[revliscap.livejournal.com]

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

[avva.livejournal.com]

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

[avva.livejournal.com]

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

[utnapishti.livejournal.com]

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

[avva.livejournal.com]

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

[xxxxx.livejournal.com]

ты ещё спроси, годится ли пустой промежуток (из нуля дней, см. пользователя spamsink)

[revliscap.livejournal.com]

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

[revliscap.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, потом найти противоречия... Но то не ко мне, наверно, а к какому-нибудь Гаусу или Фурье.

[revliscap.livejournal.com]

если кушать по 1му огурцу в день, то 42-28 = 14 огурцов в остатке, то есть в течении 28 дней существует 14 дней, когда будет съедаться по 2 огурца в день

если 14 дней с 2мя огурцами идут подряд, то в оставшиеся дни существует период с 13 огурцами подряд

а если 14 дней с 2мя огурцами идут не подряд, то так же существует период с 13ю огурцами

[gg59.livejournal.com]

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

[utnapishti.livejournal.com]

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

[webface.livejournal.com]

В один день может быть и более чем 2 огурца.

[(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 огурцов.

[gg59.livejournal.com]

Давайте проверим, добавлять по огурцу. Едим дополнительный огурец в первый день - первый промежуток меняется с 1 по 12, но количестов промежутков сохраняется; если едим во второй - первый промежуток с 1 по 12, второй промежуток со 2 по 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, противоречие.

[a-shen.livejournal.com]

Странно, у меня даже с бумажкой получается максимум 25 дней

[botev.livejournal.com]

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

[gg59.livejournal.com]

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

[moon-aka-sun.livejournal.com]

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

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

[dmitrmax.livejournal.com]

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

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

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

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