Question

Прямоугольник 71× 189 разрезан на квадраты 1×1, 2×2 и прямоугольники 2×3. Суммарное количество квадратов разрезания оказалось равным N, где N>3934. Найдите наименьшее возможное значение N

Answer 1

Ответ:

$N_{min} = 3936$

Объяснение:

Answer 2

Обозначим количество квадратов 1×1 через a, количество квадратов 2×2 через b, а количество прямоугольников 2×3 через c. Тогда имеем систему уравнений:

1. 71 × 189 = a + 4b + 6c (общее количество клеток в прямоугольнике должно быть равно сумме клеток всех квадратов и прямоугольников)
2. a + b + c > 3934 (суммарное количество квадратов разрезания должно быть больше 3934)

Нам нужно найти наименьшее возможное значение суммы a + b + c, удовлетворяющее этим условиям.

Заметим, что каждый прямоугольник 2×3 можно заменить на три квадрата 2×2 (см. рисунок).

diffCopy code
+---+---+---+
|   |   |   |
+---+---+---+
|   |   |   |
+---+---+---+

=>

+---+---+
|   |   |
+---+---+
|   |   |
+---+---+
|   |   |
+---+---+

Таким образом, мы можем заменить все прямоугольники 2×3 на квадраты 2×2 и получить новое разрезание прямоугольника, в котором все квадраты имеют размер 1×1 или 2×2. При этом суммарное количество квадратов разрезания не изменится, т.к. каждый прямоугольник 2×3 содержит три квадрата 2×2.

Новое разрезание прямоугольника будет состоять из (71 × 189 + 2) квадратов 2×2 и некоторого количества квадратов 1×1. Обозначим количество квадратов 1×1 в новом разрезании через x. Тогда у нас будет следующая система уравнений:

1. 71 × 189 + 2 = 4b + x (в новом разрезании прямоугольника все квадраты имеют размер 1×1 или 2×2)
2. x + b > 3934 (суммарное количество квадратов разрезания не изменится)

Мы хотим найти наименьшее возможное значение суммы x + b, удовлетворяющее этим условиям.

Решим первое уравнение относительно b:

b = (71 × 189 + 2 - x) / 4

Подставляем это выражение во второе уравнение и получаем:

x + (71 × 189 + 2 - x) / 4 > 3934

Упрощаем:

x > (3934 - (