Страница: << 1 2 [Всего задач: 7]      

На доске написаны 2$n$ последовательных целых чисел. За ход можно разбить написанные числа на пары произвольным образом и каждую пару чисел заменить на их сумму и разность (не обязательно вычитать из большего числа меньшее, все замены происходят одновременно). Докажите, что на доске больше никогда не появятся 2$n$ последовательных чисел.

Решение

  По известной формуле  $1^2 + 2^2 + ... + (2n)^2$ = ⅓ $n(n + 1)(4n + 1)$.  Пусть  $m = \frac{n}{НОД(n,3)}$.  Тогда  $1^2 + 2^2 + ... + (2n)^2$  делится на $m$, но не на 2$m$. Это верно не только для суммы квадратов чисел от 1 до 2$n$, но и для суммы квадратов любых 2$n$ последовательных чисел: если из набора 2$n$ последовательных квадратов удалить квадрат в начале и добавить квадрат в конце, то остаток от деления их суммы на 2$m$ не изменится.
  Если $x$ и $y$ заменить на  $x + y$  и  $x - y$,  то  $x^2 + y^2$  заменится на  $(x + y)^2 + (x - y)^2 = 2x^2 + 2y^2$.  Поэтому в итоге сумма квадратов чисел умножается на 2 на каждом шаге. Сумма квадратов исходных чисел делится на $m$, но не делится на 2$m$. Но на каждом шаге сумма квадратов полученных чисел будет делиться на 2$m$, поэтому это не будут последовательные числа.

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

Для каких $k$ можно закрасить на белой клетчатой плоскости несколько (конечное число, большее нуля) клеток в чёрный цвет так, чтобы на любой клетчатой вертикали, горизонтали и диагонали либо было ровно $k$ чёрных клеток, либо вовсе не было чёрных клеток?

Решение

  Закрасим чёрным сначала $k$ клеток, стоящих подряд вдоль одной из диагоналей, идущей вправо-вниз. Затем сдвинем эту картинку по диагонали вправо-вверх на  $k, 2k, 3k, ..., (k - 1)k$  клеток. Получится множество $A$ из $k^2$ чёрных клеток, которое каждая горизонталь и вертикаль пересекает не более чем по одной клетке, а каждая диагональ имеет с $A$ либо 0, либо $k$ общих клеток (рисунок слева для  $k$ = 3).   При этом всё множество $A$ лежит в квадрате $k^2\times k^2$.

           

  Заметим, что если квадрат $n\times n$ сдвинуть на 2$n$ клеток по вертикали, то не существует диагонали, пересекающей оба эти квадрата (рисунок справа для  $n$ = 3).
  Поэтому, сдвинув множество $A$ на  $2k^2, 4k^2, ..., 2(k-1)k^2$  вверх, мы получим множество $B$ из $k^3$ чёрных клеток, которое каждая горизонталь пересекает не более чем по одной клетке, а каждая вертикаль и диагональ имеет с $B$ либо 0, либо $k$ общих клеток. При этом все множество $B$ лежит в квадрате $2k^3\times 2k^3$.
  Теперь, сдвинув множество $B$ на  $4k^3, 8k^3, ..., 4(k-1)k^3$  вправо, мы получим искомое множество из $k^4$ чёрных клеток.
 (Другими словами, построенное множество состоит из клеток с "координатами"  $(- i+kj+4mk^3, i+kj+2nk^2), 0\leqslant i, j, m, n < k$.)

Ответ

Для всех натуральных $k$.

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

Страница: << 1 2 [Всего задач: 7]