?

Log in

задачка про огурцы - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка про огурцы [июл. 12, 2016|01:30 pm]
Anatoly Vorobey
[Tags|, ]

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

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

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

Comments:
From: kikzan
2016-07-12 10:34 am
То есть, как ни ешь огурцы, но если съесть 42 за 28 дней, обязательно будет промежуток целого количества дней, за который съедено 13 огурцов?
(Ответить) (Thread)
[User Picture]From: avva
2016-07-12 10:39 am
Именно так, только вы забыли условие про минимум 1 каждый день. Кроме того, нет никаких подвохов типа огурца, съеденного наполовину в один день и наполовину в другой. Все "честно". 28 целых чисел, каждое из которых не меньше 1, сумма 42, найдется идущая подряд выборка с суммой 13.

Edited at 2016-07-12 10:40 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: revliscap
2016-07-12 10:35 am
28+13=41, то есть такой промежуток существует в пределах 42 дней
(Ответить) (Thread)
[User Picture]From: avva
2016-07-12 10:40 am
Я не очень понял ваш комментарий :) но дней вообще-то 28.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: utnapishti
2016-07-12 10:41 am
В смысле, ровно 13, верно?
(Ответить) (Thread)
[User Picture]From: avva
2016-07-12 10:42 am
Да, сейчас добавлю это слово.
(Ответить) (Parent) (Thread)
[User Picture]From: arctic_fox_1480
2016-07-12 10:48 am
нужно доказать невозможность распределения огурцов таким образом чтобы не получался ряд дней насчитывающий 13 огурцов?
(Ответить) (Thread)
[User Picture]From: avva
2016-07-12 10:48 am
Да!
(Ответить) (Parent) (Thread)
[User Picture]From: xboctram
2016-07-12 10:57 am
13 огурцов= 5 дней подряд по 2 и 3 дня по одному
(Ответить) (Thread)
From: natomist
2016-07-12 11:04 am
В самом худшем случае я могу 14 дней есть по 2 огурца, а 14 дней по одному огурцу. Как не чередуй эти дни все равно будет достаточно единиц в ряду, что бы найти интервал который в сумме даст 13. Если я в какой-то день съем больше 2-х огурцов, то количество единиц в ряду станет ещё больше.
Вот такое мое не строгое доказательство.

Конечно в идеале бы нужно предположить, что существует такой ряд из 28 чисел, которые бы дали бы в сумме 42 и на котором бы не возможно было бы выделить субряд, который давал бы в сумме 13, потом найти противоречия... Но то не ко мне, наверно, а к какому-нибудь Гаусу или Фурье.
(Ответить) (Thread)
[User Picture]From: gg59
2016-07-12 11:28 am
Если мы в течение 28-ми дней каждый день едим по огурцу, то у нас набирается 16 промежутков, когда огурцов съедается тринадцать: с 1 по 13 день, со 2 по 14, с 3 по 15, и т.д., с 16 по 28.
Оставшимися огурцами мы можем "испортить" только 14 таких промежутков (42 - 28 = 14 оставшихся у нас огурцов).
Это значит, что промежутков с 13 огурцами всегда будет как минимум два.
(Ответить) (Thread)
[User Picture]From: utnapishti
2016-07-12 11:33 am
они же пересекаются, эти промежутки
как правило, один "дополнительный" огурец испортит сразу несколько промежутков
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2016-07-12 11:47 am
каждый день мы съедаем минимум по 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 огурцов.
(Ответить) (Thread)
From: baca6u
2016-07-12 06:31 pm
Съев в 13 день два огурца мы не портим промежуток с 1 по 13, мы создаем промежуток со 2-го по 13 день в который мы съедаем 13 огурцов. Не годится. Чтобы испортить этот промежуток достаточно хорошо, надо съесть на 13-й день 14 огурцов. Получается с 1-го по 12-й - 12 огурцов, в 13-й - 14. Итого получается 26 огурцов за 13 дней. Остается промежуток с 14-го по 28 в который у нас есть 42-26=16 огурцов за 14 дней. То есть по одному каждый день и еще два добавочных в один или два дня. Куда бы мы их (эти два лишних) не поставили, промежуток с 13-ю огурцами будет точно, слишком много единиц.
Вторая часть, конечно, не слишком строгая, но я зуб даю, что это так.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2016-07-12 11:55 am
Пусть 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, противоречие.
(Ответить) (Thread)
[User Picture]From: botev
2016-07-12 12:06 pm
это смотря какие огурцы, конечно. бывают такие огурцы, что одним на целый день наедаешься, а бывают и такие, что хоть десять штук съешь, все одно через час снова жрать охота. бывает еще, откусишь — и видишь, что горький. с другого конца откусишь — может быть не горький, а может быть снова горький! так вот и выкинешь огурец, а он денег стоит. опять же соленые, малосольные, маринованные — это все тоже необходимо учитывать. можно еще в салат порезать, хотя я не очень люблю. лучше уж вообще без огурцов, ну их нахуй.
(Ответить) (Thread)
[User Picture]From: ok_66
2016-07-12 04:28 pm
У Носова эта тема подробно раскрыта.
(Ответить) (Parent) (Thread)
[User Picture]From: moon_aka_sun
2016-07-12 12:32 pm
Тут приходит программист. Напишем программу, которая перебирает все варианты разбиения 42 огурцов на 28 дней...
__

28 о за 28 д - всё ок. Теперь можем ли мы разместить 14 о, чтоб испортить расклад? Если портить с одного конца, то с другого всё будет ок. Надо портить в середине. Все 14 сразу - не получается, всё равно остаётся одиночный конец. Вплотную 7 и 7 - тоже не выход. Остаётся найти, как 7 могут испортить 14 дней. Думаю, в этом направление надо двигаться...
(Ответить) (Thread)
[User Picture]From: ok_66
2016-07-12 04:29 pm
Семь и семь ничего испортить не могут. Ведь дней не обязательно должно быть 13.

Edited at 2016-07-12 16:30 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: dmitrmax
2016-07-12 12:41 pm
Запишем на бумаге кол-во огурцов, которые я съел в во все дни по порядку слева направа. Далее идем по этому ряду окном.

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

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

Если на шаге 2 мы будем из окна выкидывать только дни содержащие 1 огурец, то мы непременно получим 13 огурцов в окне. Следовательно, переход из шага 2 к шагу 1 возможен тогда и только тогда, когда из окна вылетел хотя бы один день, содержащие более 1 огурца. Всего таких дней не может быть более 14. Следовательно после 14 перехода к шагу 1, в окне останутся только дни с одним огруцом. То есть мы обязательно найдем такой промежуток обязательно не далее 14-го шага.
(Ответить) (Thread)
From: uleysky.blogspot.com
2016-07-12 12:42 pm
Задачу можно сформулировать в общем виде. 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)
(Ответить) (Thread)
[User Picture]From: old_radist
2016-07-15 06:45 am
>> 3k огурцов съедается за 2k дней...

Однако у вас масштабы!..
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: mikev
2016-07-12 01:23 pm
расположим огурцы последовательно в порядке поедания и перенумеруем натуральными числами от 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.
(Ответить) (Thread)
From: vnesov
2016-07-12 01:54 pm
А если 27 дней, 50 огурцов?

Edited at 2016-07-12 13:55 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2016-07-12 01:45 pm
Пусть 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 огурцов (или меньше) на оставшиеся две недели, а по условию задачи мы должны съедать не менее огурца в день.
(Ответить) (Thread)
[User Picture]From: larisaka
2016-07-12 02:02 pm
О, помню, я один раз была на такой диете, только там были не огурцы, а капуста, то есть капустный суп, а остальное точь-в точь. Решения не помню, даже если оно и было, потому что соображать перестаешь день на четвертый.
(Ответить) (Thread)
[User Picture]From: al_evilproof
2016-07-12 04:29 pm
Самый простой и тупой, сразу, устно:

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

Edited at 2016-07-12 16:30 (UTC)
(Ответить) (Thread)
[User Picture]From: lenamarkova
2016-07-12 04:54 pm
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 дней.
(Ответить) (Thread)
From: (Anonymous)
2016-07-12 06:48 pm
42 - 28 = 14, т.е. половину дней я ем 1 огурец и половину 2, и никак иначе. А дальше - из 28 двоек и единиц по-любому можно набрать 13 подряд (и даже несколькими способами).
(Ответить) (Thread)
[User Picture]From: ravli
2016-07-12 06:49 pm
это я был
(Ответить) (Parent) (Thread) (Развернуть)
From: a_shen
2016-07-12 07:09 pm

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

оценка кажется излишне большой: если у нас в интервале 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, как было бы, если оценка в задаче была бы точной) 
(Ответить) (Thread)
[User Picture]From: timur0
2016-07-12 07:32 pm
Рассмотрим количество съеденных огурцов нарастающим итогом, т.е. сколько съел всего на этот день. Рассмотрим остатки от деления этих чисел на 13. Всего есть 28 остатков, значит какой-то остаток встретится три раза. Разности будут кратны 13; если одна из разностей 13, то все доказано. Если нет, то это 26 и 39, а их разность как раз 13, что нам и нужно.
(Ответить) (Thread)
From: huzhepidarasa
2016-07-12 08:24 pm
[Спойлер, не давите сюда!]

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

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

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

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

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

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

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

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

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

(Ответить) (Thread)
From: (Anonymous)
2016-07-12 08:48 pm

тест

Тоже так решил.
Есть 28 разных чисел от 1 до 42. Доказать, что найдутся два с разницей 13. Рассмотрми остаток от деления на 13. Всего 28 чисел (28 = 13 + 13 + 2), значит, найдутся 3 числа с одинаковым остатком. Максимально чисел с одинаковым остатком может быть 4 (т.к. 4 * 13 больше 42). имеем <= 4 корзинки и в них 3 яблока. Очевидно, найдутся 2 яблока, лежащих рядом.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2016-07-13 09:07 am
В комментариях есть "математические" решения, но по условию нужно ведь решение Простое!

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

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

(Ответить) (Thread)
From: huzhepidarasa
2016-07-13 04:58 pm
Вы забыли про слово «подряд».
(Ответить) (Parent) (Thread) (Развернуть)
From: Anton Likhtarov
2016-07-15 07:43 am
Представим ряд из 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 границ, на одну меньше чем требуется.

Edited at 2016-07-15 07:44 (UTC)
(Ответить) (Thread)
From: Anton Likhtarov
2016-07-23 11:38 pm
Похоже 3, 16, ... посчитал дважды, так что работает даже для 26-и дней
(Ответить) (Parent) (Thread)