Выбрана 1 задача 
Убрать все задачи
Даны 1000 линейных функций: fk(x) = pkx + qk (k = 1, 2, ..., 1000). Нужно найти значение их композиции f(x) = f1(f2(f3(...f1000(x)...))) в точке x0. Докажите, что это можно сделать не более чем за 30 стадий, если на каждой стадии можно параллельно выполнять любое число арифметических операций над парами чисел, полученных на предыдущих стадиях, а на первой стадии используются числа p1, p2, ..., p1000, q1, q2, ..., q1000, x0.
Решение
|
|
 |
Условие
В каждую клетку бесконечной клетчатой плоскости записано одно из чисел 1, 2, 3, 4 так, что каждое число встречается хотя бы один раз. Назовём клетку правильной, если количество различных чисел, записанных в четыре соседние (по стороне) с ней клетки, равно числу, записанному в эту клетку. Могут ли все клетки плоскости оказаться правильными?
Решение
Предположим, что при некоторой расстановке чисел все клетки оказались правильными.
Пусть в клетку A записано число 4, тогда в одной из соседних с A клеток, например, в клетку B, записано число 4, а в одну из клеток C, D, E – число 1. Если 1 записана в клетке C, то в клетку F также записано 4, что невозможно: у клетки B две соседних
клетки с числом 4. Аналогично число 1 не может быть записано в клетку E. Значит, 1 – в клетке D. Аналогично 1 – в клетке
G, а тогда в клетках U и V – опять четверки. Итак, числа 4 порождают цепочки ...-1-4-4-1-4-4-... .
Из того, что в клетку K записано число 4, следует, что в
M записано 4, в N записано 1, и тогда однозначно восстанавливаются
числа в выделенных строках и столбцах (см. рис.).
Без ограничения общности, пусть 2 записано в F, а 3 – в H.
Рассматривая клетку H, получаем, что в клетку P записано число 2. Но в этом случае у клетки F с числом 2 в соседних клетках три различных числа. Противоречие.
Ответ
Не могут.
