Клетчатая фигура Ф обладает таким свойством: при любом заполнении клеток прямоугольника m×n числами, сумма которых положительна, фигуру Ф можно так расположить в прямоугольнике, чтобы сумма чисел в клетках прямоугольника, накрытых фигурой Ф, была положительна (фигуру Ф можно поворачивать). Докажите, что данный прямоугольник может быть покрыт фигурой Ф в несколько слоев.

   Решение

Существуют ли 1998 различных натуральных чисел, произведение каждых двух из которых делится нацело на квадрат их разности?

   Решение

Али-Баба стоит с большим мешком монет в углу пустой прямоугольной пещеры размером m×n клеток, раскрашенных в шахматном порядке. Из любой клетки он может сделать шаг в любую из четырёх соседних клеток (вверх, вниз, вправо или влево). При этом он должен либо положить одну монету в этой клетке, либо забрать из неё одну монету, если, конечно, она не пуста. Может ли после прогулки Али-Бабы по пещере оказаться, что на чёрных клетках лежит ровно по одной монете, а на белых монет нет?

   Решение

В квадрате 6×6 отмечают несколько клеток так, что из любой отмеченной можно пройти в любую другую отмеченную, переходя только через общие стороны отмеченных клеток. Отмеченную клетку называют концевой, если она граничит по стороне ровно с одной отмеченной. Отметьте несколько клеток так, чтобы получилось   а) 10,  б) 11,  в) 12 концевых клеток.

   Решение

На отрезке  [0, 1]  отмечено несколько различных точек. При этом каждая отмеченная точка расположена либо ровно посередине между двумя другими отмеченными точками (не обязательно соседними с ней), либо ровно посередине между отмеченной точкой и концом отрезка. Докажите, что все отмеченные точки рациональны.

   Решение

Темы:    [ Метод координат на плоскости ] [ Системы линейных уравнений ] [ Принцип крайнего (прочее) ] [ Линейная и полилинейная алгебра ] [ Доказательство от противного ]

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

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

Условие

На отрезке  [0, 1]  отмечено несколько различных точек. При этом каждая отмеченная точка расположена либо ровно посередине между двумя другими отмеченными точками (не обязательно соседними с ней), либо ровно посередине между отмеченной точкой и концом отрезка. Докажите, что все отмеченные точки рациональны.

Решение 1

  Обозначим координаты концов отрезка и отмеченных точек через x₀, x₁, ..., x_n+1  (0 = x₀ < x₁ < ... < x_n+1 = 1).  Условие задачи означает выполнение n равенств вида  x_i = ½ (a_i + b_i)  (i = 1, 2,..., n),  где каждый из символов a_i и b_i означает какое-то из чисел x_j  (j = 0, 1, ..., n + 1),  при этом можно считать, что  a_i < x_i < b_i.
  Во все правые части этих равенств, в которых присутствует x₁, подставим его значение из первого равенства. Получим новый набор равенств (с теми же левыми частями, что и в старом), правые части которых уже не содержат x₁. Если при этом в правой части второго равенства появится член вида αx₂, то перенесём его в левую часть и разделим обе части на  1 – α  (ниже мы докажем, что  α ≠ 1).  Второе равенство теперь имеет вид:
x₂ = β₃x₃ + β₄x₄ + ... + β_nx_n + β_n+1,  где β_i – некоторые рациональные числа.
  Рассмотрим теперь все равенства, кроме первого и второго. Во все правые части, содержащие x₂, подставим его значение из второго равенства, затем используем третье равенство, чтобы выразить x₃ через переменные x₄, ..., x_n, и подставим это значение во все равенства, начиная с четвёртого. Опять же, нужно доказать, что при этом не придется делить на нуль.
  Повторяя эту операцию n раз, придём к равенству  x_n = γ  (в правой части не осталось ни одного неизвестного!). Нетрудно понять, что на каждом шаге все коэффициенты рациональны. Действительно, в начале это так, а при наших операциях мы используем лишь сложение, умножение, вычитание и деление.
  Итак, x_n рационально. Далее, x_n–1 выражено через x_n и рациональные числа, значит, оно тоже рационально, и т. д. Следовательно, все числа рациональны.
  Осталось доказать, что ни на каком шаге не приходится делить на нуль.
  В любой момент каждое равенство будет иметь вид  x_i = δ₁x₁ + δ₂x₂ + ... + δ_nx_n + δ_n+1.  Докажем, что при этом
   1) все коэффициенты δ_k  (k = 1, 2, ..., n + 1) неотрицательны;
   2) хотя бы один коэффициент δ_k c  k > i  не равен нулю.
  Действительно, для исходного набора это верно. Делая очередную подстановку из j-го равенства  (j < i),  мы заменяем коэффициент δ_j на 0, а любой другой коэффициент δ_k на  δ_k + λδ_k,  где λ – коэффициент при x_k в j-м равенстве. Неотрицательность при этом сохраняется, а наибольший номер ненулевого коэффициента не уменьшается, следовательно, он останется большим, чем i. При переносе в левую часть члена δ_ix_i получаем в правой части положительное число. Действительно, все x_k положительны, а все коэффициенты δ_k неотрицательны, причём по крайней мере один из них строго положителен. Значит, левая часть тоже положительна, поэтому  1 – δ_k > 0.  При делении обеих частей равенства на положительное рациональное число
1 – δ_k  все перечисленные свойства также сохраняются.

Решение 2

  Пусть x₁, x₂, ..., x_n – координаты отмеченных точек. Условие, что точка находится посередине между двумя другими, записывается в виде линейного уравнения  x_i = ½ (a + b), где a и b – координаты других точек или концов отрезка (то есть 0 или 1). Таким образом, координаты наших точек являются решениями некоторой системы линейных уравнений (*) с рациональными коэффициентами и рациональными свободными членами (будем называть такую систему рациональной). Нужно доказать, что эта система не может иметь иррационального решения (то есть решения, значение хотя бы одной переменной в котором иррационально). Для этого достаточно доказать, что решение системы (*) единственно (если рациональная система линейных уравнений имеет единственное решение, то это решение рационально).
  Пусть x₁, x₂, ..., x_n и y₁, y₂, ..., y_n – два разных решения рассматриваемой системы уравнений. Тогда числа  t₁ = x₁ – y₁,  t₂ = x₂ – y₂,  ...,  t_n = x_n – y_n  образуют ненулевое решение соответствующей однородной системы, то есть системы (*), в которой все свободные члены заменили на нули.
  Иными словами, для каждого i выполняется линейное уравнение  t_i = ½ (a + b),  где a – одно из чисел t_j  (j ≠ i)  или нуль и b – одно из чисел t_j  (j ≠ i)  или нуль. Рассмотрев число t_i, имеющее максимальный модуль, приходим к противоречию.

Решение 3

  Предположим, что существует удовлетворяющий условию задачи набор точек, содержащий иррациональное число α.
  Рассмотрим множество действительных чисел как линейное пространство над множеством рациональных чисел. Существует его линейное преобразование, оставляющее на месте все рациональные числа и переводящее α в число, большее 1. При этом преобразовании набор отмеченных точек перейдёт в другой набор, удовлетворяющий условиям задачи, но содержащий точки, лежащие правее единицы. Однако это невозможно: самая правая из этих точек не может лежать посередине между двумя другими.

Замечания

То, что в решении 1 ни на каком шаге не приходится делить на нуль, принципиально: например, система линейных уравнений
    x₁ = 2x₂ – 2,
    x₂ = ½ x₁ + 1
имеет следующее иррациональное решение:  

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