Задача 9 (7 баллов). Числа от 1 до 64 расставлены в клетки таблицы 8x8. В каждом квадрате kxk (2 <= k <= 8) выбирается наибольшее число. Могло ли так оказаться, что каждое двухзначное число было выбрано хотя бы один раз?

Решение:

Давайте разберёмся, что такое квадрат kxk и сколько в нём чисел.

1. Что такое квадрат kxk? Это квадрат, состоящий из k строк и k столбцов. Общее количество клеток в таком квадрате равно \( k \times k = k^2 \).
2. Диапазон значений k: В задаче сказано, что \( 2 \le k \le 8 \).
3. Сколько всего двухзначных чисел? Двухзначные числа — это числа от 10 до 99. Их всего \( 99 - 10 + 1 = 90 \) чисел.
4. Сколько всего клеток в таблице? Таблица имеет размер 8x8, то есть всего \( 8 \times 8 = 64 \) клетки.
5. Максимальное число в квадрате kxk: В каждом квадрате kxk выбирается наибольшее число.

Анализ ситуации:

Чтобы каждое двухзначное число было выбрано хотя бы один раз, нам нужно, чтобы эти двухзначные числа были максимальными в каких-то квадратах kxk. Давайте посчитаем, сколько всего чисел мы можем выбрать из всех возможных квадратов.

Для k=2:

• Квадратов 2x2 в таблице 8x8: \( (8-2+1) \times (8-2+1) = 7 \times 7 = 49 \) квадратов.
• В каждом квадрате 2x2 содержится \( 2 \times 2 = 4 \) числа.
• Если в каждом из 49 квадратов 2x2 число 10 было бы наибольшим, то число 10 было бы выбрано 49 раз.

Для k=3:

• Квадратов 3x3 в таблице 8x8: \( (8-3+1) \times (8-3+1) = 6 \times 6 = 36 \) квадратов.
• В каждом квадрате 3x3 содержится \( 3 \times 3 = 9 \) чисел.

Для k=8:

• Квадрат 8x8 — это вся таблица. Есть только \( (8-8+1) \times (8-8+1) = 1 \times 1 = 1 \) такой квадрат.
• В нём \( 8 \times 8 = 64 \) числа.

Основная проблема:

Всего в таблице 64 числа. Из них только \( 64 - 9 = 55 \) чисел являются двухзначными (числа от 10 до 64, так как числа расставлены от 1 до 64). Но у нас есть 90 двухзначных чисел (от 10 до 99).

Даже если бы мы могли выбирать числа из квадратов с k=8, k=7, ..., k=2, и в каждом квадрате мы бы выбирали только одно число, чтобы оно было двухзначным, мы всё равно не смогли бы выбрать все 90 двухзначных чисел, потому что в таблице всего 64 числа.

Более того, задача требует, чтобы в каждом квадрате kxk выбиралось наибольшее число. Если в таблице есть только числа до 64, то никакое двухзначное число больше 64 не может быть выбрано.

Теперь рассмотрим двухзначные числа, которые находятся в диапазоне от 10 до 64. Их \( 64 - 10 + 1 = 55 \) чисел.

Даже если мы предположим, что в каждом квадрате kxk (где k от 2 до 8) максимальным числом оказалось именно одно из этих 55 двухзначных чисел, всё равно у нас есть только 64 числа в таблице, и из них 9 чисел — однозначные (1-9). Остаётся 55 чисел от 10 до 64.

Если бы мы хотели, чтобы каждое из этих 55 чисел было выбрано, нам нужно было бы найти 55 различных квадратов kxk, в каждом из которых это число было бы наибольшим. Но количество таких квадратов, где мы можем выбрать максимум, ограничено.

Ключевой момент: Всего в таблице 64 числа. Среди них 9 однозначных (1-9) и 55 двухзначных (10-64). Если мы хотим, чтобы каждое двухзначное число (от 10 до 99) было выбрано, это уже невозможно, так как двухзначных чисел от 10 до 99 — 90 штук, а в таблице всего 64 числа.

Даже если бы речь шла только о числах от 10 до 64 (их 55), то для того, чтобы каждое из них было выбрано, нам нужно было бы, чтобы оно оказалось наибольшим в каком-то квадрате. Но количество квадратов, в которых мы можем выбрать наибольшее число, ограничено. Например, для квадрата 2x2 мы имеем 49 таких квадратов. Для квадрата 3x3 — 36. И так далее. Общее количество выборов, которые мы можем сделать, очень велико, но сами числа в таблице ограничены.

Простое опровержение: В таблице есть числа от 1 до 9. Эти числа однозначные. В задаче спрашивается, могло ли каждое двухзначное число быть выбрано. Двухзначные числа — это числа от 10 до 99. В таблице есть числа только до 64. Следовательно, числа от 65 до 99 в принципе не могут быть выбраны из этой таблицы.

Ответ: Нет, не могло.