Processing math: 100%

M1538

Условие:

Прямоугольник atimesb(a>b) разбит на прямоугольные треугольники, граничащие друг с другом только по целым сторонам, так что общая сторона двух треугольников всегда служит катетом одного и гипотенузой другого.Докажите, что fracabgeq2.

Решение:

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

M1538

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

Рассмотрим треугольник разбиения, гипотенузой которого служит m. Вершина его прямого угла может лежать только на стороне CD. Высота этого треугольника равна стороне BC. Но высота h прямоугольного треугольника не превышает половины гипотенузы, следовательно, mgeq2h, откуда ABgeq2BC, что и требуется.

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

M1472

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

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

Условие.

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

1 2 3 n1 n
n 1 2 n2 n1
n1 n 1 n3 n2
3 4 5 1 2
2 3 4 n 1

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

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

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

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

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

Если выбраны числа в клетках (xi;yi), стоящих в разных строках и разных столбцах (i=1,2,,n), то среди xi и среди yi каждое число 1,2,,n встречается по разу, поэтому x1++xn=y1++yn=n(n+1)/2.

Если все числа f(xi;yi) различны по модулю n, то и сумма (x1+y1)++(xn+yn)=n(n+1)

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

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

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

Замечание.

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

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

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

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

M1344

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

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

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

Решение

Пусть an — высота, bn — ширина n-ой доски; n=1,2,…
Положим q=0.99,p=10.991.02=11.0098.
По условию, bn=b1qn,an2; доска будет окрашена, если отношение площади предшествующей доски к ее площади меньше p.
Заметим, что несмотря на бесконечность количества досок, длина и площадь забора конечны: его длина равна сумме бесконечно убывающей прогрессии b1(1+q++qn+)=b11q, а площадь не превосходит 2b11q,.
Мы не только ответим на вопрос задачи, но и найдем точную оценку сверху доли окрашеной площади забора. Пусть забор таков, что первые N досок окрашены, а за ними идут неокрашеные доски высотой aN=a,N достаточно большое число (см. рисунок). Площадь неокрашеных досок равна D=a(q+q2+)=aq1q, а площадь окрашенных может быть сколь угодно близка к C=a(1+q+q2+)=a1p.
Поскольку CD=1q(1p)q=0.010.991.020.00980.99=1.020.98=5149, этот пример показывает, что доля окрашенных досок может составлять почти 51% (и быть сколь угодно близкой к этому числу); нетрудно видеть, что эта доля может быть и любым меньшим числом.
Докажем, что она не может быть равной или большей 51%. Обозначим через S общую площадь забора, C — площадь окрашенных досок, D=SC — площадь неокрашенных. Будем называть неотмеченными доски, предшествующие неокрашенным.
Пусть n-ая доска отмечена, тогда (n+1)-ая окрашена, и anbnan+1bn=an+1bn+1q. Поэтому площадь всех неотмеченных досок не превосходит Dq. Пусть теперь n-ая доска не отмечена; тогда (n+1)-ая окрашена, и anbnpan+1bn+1. Поэтому площадь всех неотмеченных досок не больше pC. Складывая площади всех — отмеченных и неотмеченных — досок, получим: S=pC+Dq, откуда, заменив S на C+D, получим C(1p)D(1q1)=D(1q)q, т.е. CD1qq(1p)=5149.
Итак, ответы на вопросы а) и б) задачи положительны, на вопрос в) — отрицателен.

А.Григорян

M1489

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

Решение: это всегда возможно для прямоугольников m×n, лишь если m и n не больше 3. поскольку операцию можно выполнять в обратном порядке, достаточно выяснить, для каких таблиц m×n из любой расстановки можно получить таблицу из одних едениц.
Легко видеть, что для прямоугольников 1×n, 2×n и 3×n заменами знаков можно получить таблицу из одних единиц: на рисунке 1 указан порядок, в котором нули, стоящие в некоторых клетках, можно заменить на единицы(цветные линии показывают какой именно — вертикальный или диагональный — «ход» следует делать).
С другой сторны, в прямоугольнике m×n, где m и n не меньше 4, можно выделить фигуру из восьми клеток, показанных на рисунке 2 штриховкой; четность количества единиц не меняется в этих клетках при всех разрешенных преобразованиях — является, как говорят, инвариантом. Таким образом, если в одной из таких фигур стоит нечетное число единиц, то прийти к таблице заполненной единицами, невозможно.
Представляем читателям выяснить, образуют ли такие таблицы из 8 клеток полную систему инвариантов, также следует ли из четности количества единиц в каждой из них возможность преобразовать таблицу в состояние «все единицы», а заодно выяснить, сколько существует классов (неэквивалентных друг другу) таблиц относительно разрешенных в условии преобразований.
А.Галочкин

M1489

M1437

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