Панк

kolllak


Истории о путешествиях Кошака

Кошаки по-прежнему жрут траву


Previous Entry Поделиться Next Entry
Вынос мозга
Панк
kolllak
 


Продуктивно сегодня поработал, ага. Там кавычки если что. А все дело в том, что после обеда друг кинул в аську задачку.
Вот условие:

На острове Серобуромалин обитают 13 серых, 15 бурых и 17 малиновых хамелеонов.
Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (серый и бурый становятся оба малиновыми и т.п.).
Может ли случиться так, что через некоторое время все хамелеоны будут одного цвета?


Ну я думал сначала, что-то с подвохом. На сообразительность. Туда-сюда и понял, что тут тяжелый случай.
Попробуйте решить сами без гугла.

Итак, сначала решил решить наскоком. Ну типа ща найду халявную последовательность, которая сойдется к решению.
Т.к. дело происходило в уютном офисе, то протупил над этим полчаса. Вот вроде нашлось, проверяешь и хер-то там.
Стало интуитивно понятно, что надо таки доказать, что решения на самом деле нет. Т.е. при такой популяции они никогда не станут монохромными.
Ну ок. Я даже вспомнил волшебные слова "математическая индукция". Еще час рисовал всякие формулы для n и n+1.
Чем дальше в лес, тем длиньше становились выкладки. Задача явно была проще моих копаний. Поэтому дальше я полез в свойства чисел.
Стал играться с четностью-нечетностью. Что-то стало вырисовываться, но опять мимо. И тут я вгляделся в одно из соотношений
между тварями разных цветов и меня накрыло сатори.



Итак, вот мое решение. "На пальцах", но полагаю достаточно строгое.

Начнем с конца. Предположим, что есть такая последовательность скрещиваний, которая приводит к решению.
Тогда окончательная конфигурация будет:
45 / 0 / 0

Рассмотрим предпоследнее скрещивание. Понятно, что для уничтожения двух цветов на этом шаге их должно быть равное количество
(по X-штук):
45-2*X / X / X

Теперь спустимся еще на ступеньку вниз. Как же получить такой расклад? Обозначим количество хамелеонов, которые мы хотим скрестить за N.
А общее количество для этих цветов за Y и Z. Понятно, что -N для двух этих цветов не имеет смысла. Тогда количество не изменится.
Значит получается единственный вариант:
X = Y - N
X = Z + N*2

Третий цвет: 45 - (Y - N) - (Z + N*2) Но он нас больше не интересует.
А вот и главная формула:
Y - Z = 3*N
У нас все в целых числах, т.е. разница на предпредпоследнем шаге должна быть кратна 3!!! Обозначим ее за D

Теперь рассмотрим еще один предшествующий шаг. Как же мы можем получить эту разницу кратную тройке.
Обозначим количество скрещиваний на этом шаге за M. Твари одного из цветов W.
1)Если для этих цветов применяется -M и -M, то понятно что новая разница тоже кратна 3.
X = Z + 3*N - M
X = Y - M
D = 3*N

2)Второй и третий варианты
X = Z + 3*N +2*M
X = Y - M
D = 3*N + 3*M

Тоже кратно трем!

Дальше, повторяя этот прием, мы должны получить наши исходные данные (13, 15 и 17). Но помним, что на каждом шаге разница между числами
должна всегда быть кратной трем. В рассуждениях выше нигде не использовался номер шага, т.е. они подходят под все итерации.
Так для исходного числа хамелеонов это соотношение не выполняется (дельты: 2, 2 и 4), то делаем вывод, что остров никогда не станет монохромным.
Та -да!
 

Убил я на это часа три. Посмотрел потом в интернетах.
Оказывается этой задачкой коммунисты (1985 г.) мучили 7-классников.
Как было страшно жыть.

PS Решение от автора задачи можно посмотреть здесь.

promo kolllak july 13, 2015 16:33 113
Buy for 20 tokens
Итак, давайте я расскажу вам, почему ваш блог никто не комментирует, почему тревел блогеры бегут из ЖЖ в Инстаграм, и почему форум Винского лучше, чем ваш уютный. Постараюсь быть предельно честным и беспощадным, в том числе и к своему творчеству. 1. Бесполезность Вы только что написали…

  • 1
Да, ты крут :)

Седьмой класс ))

  • 1
?

Log in

No account? Create an account