M1538

Условие:

Прямоугольник [latex]atimes b(a>b)[/latex] разбит на прямоугольные треугольники, граничащие друг с другом только по целым сторонам, так что общая сторона двух треугольников всегда служит катетом одного и гипотенузой другого.Докажите, что [latex]frac{a}{b}geq2.[/latex]

Решение:

Пусть наш прямоугольник — [latex]ABCD[/latex]. Докажем, что вершина треугольника разбиения не может лежать внутри прямоугольника. Действительно, допустим противное, пусть хотя бы одна вершина внутри прямоугольника существует. Значит, существуют и стороны треугольников разбиения, которые обладают таким свойством: хотя бы один конец этой стороны лежит внутри прямоугольника. Рассмотрим множество [latex]M[/latex] сторон, обладающих этим свойством. По условию задачи, эта сторона для одного из примыкающих к ней треугольников разбиения служит гипотенузой. Тогда катет этого треугольника, выходящий из этой же точки, а следовательно, тоже принадлежащий множеству [latex]M[/latex], будет короче гипотенузы, т.е. короче кратчайшего отрезка множества [latex]M[/latex]. Противоречие. Итак, все вершины треугольников разбиения лежат на границе прямоугольника.

Теперь рассмотрим самую длинную из сторон треугольников разбиения: пусть это сторона [latex]m[/latex]. Она принадлежит одной из сторон прямоугольника. Действительно, иначе [latex]m[/latex] служила бы катетом для некоторого треугольника, а его гипотенуза был бы ещё длиннее. Пусть [latex]m[/latex] лежит на стороне [latex]AB[/latex] прямоугольника (см. рисунок).

Рассмотрим треугольник разбиения, гипотенузой которого служит [latex]m[/latex]. Вершина его прямого угла может лежать только на стороне [latex]CD[/latex]. Высота этого треугольника равна стороне [latex]BC[/latex]. Но высота [latex]h[/latex] прямоугольного треугольника не превышает половины гипотенузы, следовательно, [latex]mgeq 2h[/latex], откуда [latex]ABgeq 2BC[/latex], что и требуется.

А.Шаповалов, Н.Константинов

M1472

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

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

Условие.

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

[latex]1[/latex]	[latex]2[/latex]	[latex]3[/latex]	[latex]…[/latex]	[latex]n-1[/latex]	[latex]n[/latex]
[latex]n[/latex]	[latex]1[/latex]	[latex]2[/latex]	[latex]…[/latex]	[latex]n-2[/latex]	[latex]n-1[/latex]
[latex]n-1[/latex]	[latex]n[/latex]	[latex]1[/latex]	[latex]…[/latex]	[latex]n-3[/latex]	[latex]n-2[/latex]
[latex]…[/latex]	[latex]…[/latex]	[latex]…[/latex]	[latex]…[/latex]	[latex]…[/latex]	[latex]…[/latex]
[latex]3[/latex]	[latex]4[/latex]	[latex]5[/latex]	[latex]…[/latex]	[latex]1[/latex]	[latex]2[/latex]
[latex]2[/latex]	[latex]3[/latex]	[latex]4[/latex]	[latex]…[/latex]	[latex]n[/latex]	[latex]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](1)[/latex] Можно ли выписать две перестановки чисел [latex] 1,2,…,n [/latex] одну под другой так, чтобы суммы чисел по столбцам давали различные остатки от деления на [latex]n[/latex]?

[latex](2)[/latex] Пусть [latex]n[/latex] штырьков радиолампы и [latex]n[/latex] соответствующих гнезд розетки, в которую она втыкается, расположены по кругу в вершинах правильного [latex]n[/latex]-угольника. Можно ли штырьки и гнезда занумеровать числами [latex]1,2,…,n[/latex] так, чтобы при любом втыкании лампы в розетку ровно один штырек попадал в гнездо с тем же номером?

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

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

M1344

Задача из Научно-популярного физико-математическом журнала «Квант». Она была опубликована в февральском выпуске 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].
Итак, ответы на вопросы а) и б) задачи положительны, на вопрос в) — отрицателен.

А.Григорян

M1489

Для каких прямоугольников $latex m\times n $ на клетчатой бумаге, в клетках которых расставлены нули и единицы, можно получить из любой расстановки любую другую, если разрешается изменять числа одновременно в каждой строке, каждом столбце и на каждой прямой, параллельной диагоналями клеток (в частности, в угловых клетках)?

Решение: это всегда возможно для прямоугольников $latex m\times n $, лишь если $latex m $ и $latex n $ не больше 3. поскольку операцию можно выполнять в обратном порядке, достаточно выяснить, для каких таблиц $latex m\times n $ из любой расстановки можно получить таблицу из одних едениц.

Легко видеть, что для прямоугольников $latex 1\times n $, $latex 2\times n $ и $latex 3\times n $ заменами знаков можно получить таблицу из одних единиц: на рисунке 1 указан порядок, в котором нули, стоящие в некоторых клетках, можно заменить на единицы(цветные линии показывают какой именно — вертикальный или диагональный — «ход» следует делать).

С другой сторны, в прямоугольнике $latex m\times n $, где m и n не меньше 4, можно выделить фигуру из восьми клеток, показанных на рисунке 2 штриховкой; четность количества единиц не меняется в этих клетках при всех разрешенных преобразованиях — является, как говорят, инвариантом. Таким образом, если в одной из таких фигур стоит нечетное число единиц, то прийти к таблице заполненной единицами, невозможно.

Представляем читателям выяснить, образуют ли такие таблицы из 8 клеток полную систему инвариантов, также следует ли из четности количества единиц в каждой из них возможность преобразовать таблицу в состояние «все единицы», а заодно выяснить, сколько существует классов (неэквивалентных друг другу) таблиц относительно разрешенных в условии преобразований.

А.Галочкин

M1437

Докажите, что если последовательность удовлетворяет следующим условиям: Читать далее