На острове живут хамелеоны пяти цветов. Когда один хамелеон кусает другого, цвет укушенного хамелеона меняется по некоторому правилу, причём новый цвет зависит только от цвета укусившего и цвета укушенного. Известно, что $2023$ красных хамелеона могут договориться о последовательности укусов, после которой все они станут синими. При каком наименьшем $k$ можно гарантировать, что $k$ красных хамелеонов смогут договориться так, чтобы стать синими?

Например, правила могут быть такими: если красный хамелеон кусает зелёного, укушенный меняет цвет на синий; если зелёный кусает красного, укушенный остаётся красным, то есть «меняет цвет на красный»; если красный хамелеон кусает красного, укушенный меняет цвет на жёлтый, и так далее. (Конкретные правила смены цветов могут быть устроены иначе.)

   Решение

Темы:    [ Системы линейных уравнений ] [ Системы алгебраических нелинейных уравнений ] [ Системы алгебраических неравенств ] [ Алгебраические неравенства (прочее) ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

На 2016 красных и 2016 синих карточках написаны положительные числа, все они различны. Известно, что на карточках какого-то одного цвета написаны попарные суммы каких-то 64 чисел, а на карточках другого цвета – попарные произведения тех же 64 чисел. Всегда ли можно определить, на карточках какого цвета написаны попарные суммы?

Решение 1

См. первый способ решения задачи 65874. Для неизвестных чисел  x₁ < x₂ < ... < x₆₄  имеем     Действительно,
x₁x₆₃x₆₄ + x₂x₆₃x₆₄ > x₁x₂x₆₃ + x₁x₂x₆₄.

Решение 2

  Понятно, что 64 неизвестных числа положительны и различны. Если максимум одно из них меньше (не меньше) 2, то попарных сумм и произведений, меньших (не меньших) 4, максимум по 63. Следовательно, определяется, имеются ли два неизвестных числа, меньших 2, или два числа, не меньших 2.
  В первом случае для наименьших чисел x и y выполняется неравенство  (x – 1)(y – 1) < 1,  то есть  xy < x + y.  Поэтому наименьшее число на карточках будет произведением.
  Во втором случае, взяв два наибольших числа x и y, аналогично докажем, что  xy > x + y,  и наибольшее число на карточках будет произведением.

Ответ

Всегда.

Замечания

1. Можно даже определить все исходные числа  x₁ < x₂ < ... < x₆₄.  Как показано, мы знаем x₁x₂ и x₁x₃ (это наименьшие из произведений), а также
x₁ + x₂  и  x₁ + x₃  (наименьшие из сумм). Тогда мы знаем  x₁(x₃ – x₂)  и  x₃ – x₃,  а следовательно, и x₁. Пусть нам уже известны числа x₁, ..., x_k–1. Тогда x₁x_k – наименьшее из неопределённых ещё произведений. Значит, мы знаем и x_k.

8 баллов.

Источники и прецеденты использования