Журнал «Квант» — физико-математический журнал для школьников и студентов

ЯНВАРЬ/ФЕВРАЛЬ 1995 г. №1

Условие.

При каких натуральных [latex]n>1[/latex] в таблице

можно выбрать [latex]n[/latex] разных чисел в разных строках и разных столбцах?

Решение и ответ.

Ответ: при нечетном [latex]n[/latex] — можно, при четном — нельзя.

Будем считать, что таблица состоит из клеток [latex](x;y)[/latex], где [latex]x[/latex] и [latex]y[/latex] — целые числа от [latex]1[/latex] до [latex]n[/latex], причем в клетке [latex](x;y)[/latex] стоит число [latex]f(x;y)[/latex] от [latex]1[/latex] до [latex]n[/latex] такое, что: [latex]f(x;y)=x+y(mod n).[/latex]

Т.е. разность [latex]f(x;y)-(x+y)[/latex] делится на [latex]n[/latex]. (Очевидно, это расположение чисел такое же, как в условии).

Если выбраны числа в клетках [latex](x_{i};y_{i})[/latex], стоящих в разных строках и разных столбцах [latex](i=1,2,…,n)[/latex], то среди [latex]x_{i}[/latex] и среди [latex]y_{i}[/latex] каждое число [latex]1,2,…,n[/latex] встречается по разу, поэтому [latex]x_{1}+…+x_{n} = y_{1}+…+y_{n} = n(n+1)/2[/latex].

Если все числа [latex]f(x_{i};y_{i})[/latex] различны по модулю [latex]n[/latex], то и сумма [latex](x_{1}+y_{1})+…+(x_{n}+y_{n})=n(n+1) [/latex]

должна равняться [latex]n(n+1)/2[/latex] по модулю [latex]n[/latex]. Но если [latex]n[/latex] чётно, [latex]n=2k[/latex], то разность [latex]2k(2k+1)-k(2k+1)=k(2k+1)[/latex]

не делится на [latex]n=2k[/latex], так что выбрать числа требуемым образом нельзя.

Если же [latex]n[/latex] нечетно, то достаточно выбрать числа [latex]f(x;y)[/latex] в клетках [latex]x=y[/latex], идущих по диагонали, где все они различны (числа [latex]2,4,…,2n[/latex] дают разные остатки при делении на [latex]n[/latex]).

Замечание.

Эта задача — по существу другая формулировка двух более известных:

Ответ. конечно, тот же, что и в задаче [latex]M1472[/latex].

Н.Васильев, А.Савин

Задача из Научно-популярного физико-математическом журнала «Квант». Она была опубликована в февральском выпуске 1993г. под номером М1344.

Условие задачи

Том Сойер красит забор, состоящий из бесконечной последовательности прямоугольных досок разной ширины и высоты. Каждая доска на 1% уже, чем предыдущая, и выше нее, но не выше 2м. Том начинает с первой доски и затем, если доска выше предыдущей более чем на 2%, красит ее, а в противном случае — пропускает. Может ли забор быть таким, что он покрасит не менее:
а) 40%, б) 50%, в) 60% площади забора?

Решение

Пусть a_n — высота, b_n — ширина n-ой доски; n=1,2,…
Положим [latex]q=0.99, p=\frac{1}{0.99*1.02}=\frac{1}{1.0098}[/latex].
По условию, [latex]b_{n}=b_{1}q^{n}, a_{n}\leq 2[/latex]; доска будет окрашена, если отношение площади предшествующей доски к ее площади меньше p.
Заметим, что несмотря на бесконечность количества досок, длина и площадь забора конечны: его длина равна сумме бесконечно убывающей прогрессии [latex]b_{1}(1+q+…+q^{n}+…)=\frac{b_{1}}{1-q},[/latex] а площадь не превосходит [latex]\frac{2b_{1}}{1-q},[/latex].
Мы не только ответим на вопрос задачи, но и найдем точную оценку сверху доли окрашеной площади забора. Пусть забор таков, что первые N досок окрашены, а за ними идут неокрашеные доски высотой [latex]a_{N}=a, N-[/latex] достаточно большое число (см. рисунок). Площадь неокрашеных досок равна [latex]D=a(q+q^{2}+…)=\frac{aq}{1-q}[/latex], а площадь окрашенных может быть сколь угодно близка к [latex]C=a(1+q+q^{2}+…)=\frac{a}{1-p}[/latex].
Поскольку [latex]\frac{C}{D}=\frac{1-q}{(1-p)q}=\frac{0.01*0.99*1.02}{0.0098*0.99}=\frac{1.02}{0.98}=\frac{51}{49}[/latex], этот пример показывает, что доля окрашенных досок может составлять почти 51% (и быть сколь угодно близкой к этому числу); нетрудно видеть, что эта доля может быть и любым меньшим числом.
Докажем, что она не может быть равной или большей 51%. Обозначим через S общую площадь забора, C — площадь окрашенных досок, [latex]D = S-C[/latex] — площадь неокрашенных. Будем называть неотмеченными доски, предшествующие неокрашенным.
Пусть n-ая доска отмечена, тогда (n+1)-ая окрашена, и [latex]a_{n}b_{n}\leq a_{n+1}b_{n}=\frac{a_{n+1}b_{n+1}}{q}[/latex]. Поэтому площадь всех неотмеченных досок не превосходит [latex]\frac{D}{q}[/latex]. Пусть теперь n-ая доска не отмечена; тогда (n+1)-ая окрашена, и [latex]a_{n}b_{n}\leq pa_{n+1}b_{n+1}[/latex]. Поэтому площадь всех неотмеченных досок не больше pC. Складывая площади всех — отмеченных и неотмеченных — досок, получим: [latex]S=pC+\frac{D}{q}[/latex], откуда, заменив S на C+D, получим [latex]C(1-p)\leq D(\frac{1}{q}-1)=\frac{D(1-q)}{q}[/latex], т.е. [latex]\frac{C}{D}\leq \frac{1-q}{q(1-p)}=\frac{51}{49}[/latex].
Итак, ответы на вопросы а) и б) задачи положительны, на вопрос в) — отрицателен.

А.Григорян

Дана таблица $latex n\times n $, столбцы которой пронумерованы числами от $latex 1 $ до $latex n $. В клетки таблицы расставляются числа $latex 1,2,\cdots,n $ так, что в каждой строке и в каждом столбце все числа различны. Назовем клетку хорошей, если читсло в ней больше номера столбца, в котором она находится. При каких $latex n $ существует расстановка, в которй во всех строках одинаковое количество хороших клеток?

Решение

Найдем общее количество хороших клеток. В первом столбце их $latex n-1 $ (все, кроме клетки с числом 1), во вторм их $latex n-2 $ (все, кроме клетки с числом 1 и 2) и т.д., в последнем столбце таких клкеток нет. Значит, всего их $latex (n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2} $

Поэтому в каждой строке их должно быть по $latex \frac{n-1}{2} $, следовательно, $latex n $ должно быт ьнечетным.

Приведем пример расстановки при нечетном $latex n $. Пусть в первой строке записаны числа в порядке $latex 1,n,n-1,n-2,\cdots,2 $

а каждая следующая строка является циклическим сдвигом предыдущей строки на 1 клетку (см.рис.). Очевидно, в любой строке и в любом столбце каждое из чисел $latex 1,2,\cdots,n $ встречается по одному разу. Рассмотрим $latex m $-ю строку ( $m\in \left \{ 1,2,\cdots,n \right \} $). В ее первых $latex m $ клетках стоят числа $latex 1,2,\cdots,m $ в обратном порядке, поэтому среди этих клеток ровно $latex \left [\frac{m}{2} \right] $ хороших. В ее последних $latex n-m $ клетках(т.е. в столбцах с номерами $latex m+1,m+2,\cdots,n $) стоят числа $latex m+1,m+2,\cdots,n $ в обратном порядке, поэтому среди этих клеток ровно $latex \left [\frac{n-m}{2} \right] $ хороших. Так как числа $latex m $ и $latex n-m $ разной четности, то в $latex m $-й строке ровно $latex \left [\frac{m}{2} \right]+\left [\frac{n-m}{2} \right]=\frac{m}{2}+\frac{n-m}{2}-\frac{1}{2}=\frac{n-1}{2} $ хороших клеток.