Страница 1 из 1

Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 00:12
Dendr
Последовательность оказалась слишком зубодробительной, а 1 апреля уже прошло.
Поэтому потрадиционнее задачка, со школьной олимпиады, только я позволил себе немного видоизменить условие. Впрочем, она очень уже могла встречаться вам.

Форрест Гамп сидит на автобусной остановке и рассказывает случайным людям про свою жизнь. Его невольные слушатели сменяют один другого, и разговор с каждым Форрест начинает с известной цитаты своей мамы про сравнение жизни и коробки конфет: "Никогда не знаешь, какая попадется". Дабы убедить собеседников в истинности этого утверждения, он действительно достает коробку конфет и предлагает угоститься.

Коробка представляет собой прямоугольник, разбитый на ячейки (четное количество по каждой стороне), в каждой ячейке изначально лежит одна конфета. Форрест разрешает собеседнику взять две соседние конфеты, затем сам берет одну. "Соседние" - это две, разделенные одиночной перегородкой, по горизонтали или по вертикали. Если очередной собеседник видит, что соседних конфет больше не встречается, он вежливо отказывается от своей доли, и Форрест ест конфету в одиночку.

Вопрос - сколько конфет Форрест может гарантировать для себя?

Re: Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 00:47
Леша
Для начала очевино, что Форрест не может гарантировать себе больше половины конфет.

Re: Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 01:10
Леша
С другой стороны для больших коробок Форрест может съесть строго больше одной трети.
А это точно олимпиадная задача? Что-то мне кажется, что без компьютера ее точно не решить.

Re: Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 08:45
Юляша
Ровно половину он и съест. Практически классическая задачка на "четность".

Re: Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 12:57
Юляша
А интересно, сколько максимально конфет может он съесть?

Или, точнее.

Сколько конфет должно быть в коробке, чтобы наш герой мог съесть больше половины? (при содействии прохожих)
Пока что есть вариант в котором в коробке 4х6 герой съедает 14 конфет.

Re: Жизнь как коробка конфет

СообщениеДобавлено: 02 апр 2016, 15:04
Dendr
В условии поправил неоднозначность: сначала свои конфеты берет собеседник (явно не сказано, но брать можно любые, главное, чтобы они были рядом), только потом Форрест.

Re: Жизнь как коробка конфет

СообщениеДобавлено: 03 апр 2016, 10:40
Леша
Юляша писал(а):Ровно половину он и съест. Практически классическая задачка на "четность".

Да, точно. Мне почему-то сначала казалось, что прохожие ему могут не дать съесть половину. Но я был не прав. Если в коробке лежат конфеты из белого и темного шоколада в шахматном порядке, то Форресту достаточно каждый раз есть белую конфету. Прохожему придется есть белую и черную, значит они съедят не больше половины белых. И столько же черных.