Страница:
<< 9 10 11 12 13 14 15 >> [Всего задач: 215]
Лист клетчатой бумаги размером 5×n заполнен карточками размером
1×2 так, что каждая карточка занимает целиком две соседние клетки. На каждой карточке написаны числа 1 и –1. Известно, что произведения чисел по строкам и столбцам образовавшейся таблицы положительны. При каких n это возможно?
Решение
Так как произведение чисел в каждом столбце положительно, то минус единицы встречаются в каждом столбце, а значит, и во всей таблице чётное число раз. Следовательно, общее число карточек чётно, а общее число клеток в таблице (которое вдвое больше) делится на 4. Итак, 5n делится на 4; стало быть, n делится на 4.
Покажем теперь, что для любого n = 4k возможно требуемое размещение карточек. Для этого достаточно разместить карточки на листе размером 5×4 (см. рис.) и повторить это расположение k раз.
Ответ
При n, кратном 4.
В таблицу 8×8 вписаны все целые числа от 1 до 64. Доказать, что при
этом найдутся два соседних числа, разность между которыми не меньше 5.
(Соседними называются числа, стоящие в клетках, имеющих общую сторону.)
Решение
Рассмотрим горизонтальную строку таблицы, содержащую число 1, и вертикальный столбец, содержащий число 64. Мы можем, двигаясь сначала по строке, а потом по столбцу, пройти от клетки, в которой написано число 1, к клетке, в которой написано число 64, причём наш путь будет состоять не более чем из 14 ходов (ходом мы называем переход из любой клетки в соседнюю).
Предположим, что разность между каждыми двумя соседними числами в
таблице меньше 5. Тогда за 14 или меньшее число ходов, которые мы сделали при переходе от 1 к 64, к исходному числу 1 прибавится не более чем 14×4 = 56. Между тем 64 – 1 = 63. Противоречие.
|
|
|
Сложность: 3+
Классы: 9,10
|
В таблицу 9×9 вписаны все целые числа от 1 до 81. Доказать, что найдутся два соседних числа, разность между которыми не меньше 6.
Решение
Где-то в таблице стоит 1, а где-то 81. Соединим эти числа цепочкой, переходя от одного числа к другому (стоящему в соседней клетке), сделав минимальное число переходов (их будет не более 16). Если в таблице разность между соседними меньше 6, то число переходов в цепочке ровно 16, иначе нашелся бы переход с разностью, большей 5. Значит, 1 и 81 стоят в противоположных углах таблицы, а в цепочке стоят числа 1, 6, 11, 16, 21, ..., 81. Рассмотрим другую минимальную цепочку, соединяющую 1 и 81. В ней тоже должны стоять числа 1, 6, 11, 16,..., 81. Но в таблице все числа различны. Противоречие.
|
|
|
Сложность: 3+
Классы: 10,11
|
В таблице A размером 10×10 написаны какие-то числа. Обозначим сумму всех чисел в первой строке через s1, во второй – через s2 и т.д. Аналогично сумму чисел в первом столбце обозначим через t1, во втором – t2 и т.д. Составлена новая таблица B размером 10×10, в неё вписаны числа следующим образом: в первой клетке первой строки пишется наименьшее из чисел s1 и t1, в третьей клетке пятой строки пишется
наименьшее из чисел s5 и t3, аналогично записана вся таблица. Оказалось, что можно так занумеровать клетки таблицы B числами от 1 до 100, что в клетке с k-м номером будет стоять число, меньшее или равное k. Какое максимальное значение может принимать при этих условиях сумма всех чисел таблицы A?
Решение
Пример таблицы A, для которой сумма всех чисел равна 955.
Таблица
B в этом случае совпадает с
A.
Оценка. Перенумеровав столбцы и строки и, возможно, отразив таблицу относительно диагонали, сделаем так, что
t10 – наибольшее из чисел
s1, ...,
s10,
t1, ...,
t10. Тогда в десятом столбце стоят числа
s1, ...,
s10. Сумма чисел в этих клетках не превосходит суммы номеров клеток, в которых они стоят, а значит, не больше чем
91 + ... + 100 = 955. С другой стороны, эта сумма равна сумме всех чисел таблицы
A. Следовательно, сумма всех чисел таблицы
A не превосходит 955.
Ответ
955.
В некоторых клетках квадратной таблицы n×n стоят звёздочки. Известно, что если вычеркнуть любой набор строк (только не все), то найдётся столбец ровно с одной невычеркнутой звёздочкой. (В частности, если строки совсем не вычёркивать, то столбец ровно с одной звёздочкой существует.) Доказать, что
если вычеркнуть любой набор столбцов (только не все), то найдётся строка
ровно с одной невычеркнутой звёздочкой.
Решение
Заметим, что после перестановки строк и столбцов данной таблицы получаем таблицу, удовлетворяющую условиям задачи. Возьмём столбец с одной звёздочкой
(такой существует) и поменяем его с первым столбцом, а также строку, в которой стоит эта звёздочка, поменяем с первой строкой. Затем вычеркнем первую строку и применим утверждение задачи. А после этого переставим строку и столбец со звёздочкой со второй строкой и вторым столбцом. Далее вычеркнем первые две и поступим аналогично. Будем продолжать процесс, пока не упорядочим всю таблицу.
Полученная таблица, во-первых, содержит звёздочки на диагонали, а во-вторых, не содержит звёздочек под диагональю. Если теперь вычеркнуть несколько столбцов и номер последнего не вычеркнутого столбца k, то в строчке с номером k ровно одна звёздочка.
Страница:
<< 9 10 11 12 13 14 15 >> [Всего задач: 215]
Тема:
Все темы
>>
Алгебра и арифметика
>>
Текстовые задачи
>>
Таблицы и турниры
>>
Числовые таблицы и их свойства
