Задачи М2530—М2533; Ф2537—Ф2540

ЗАДАЧНИК «КВАНТА»

Задачи по математике и физике

Этот раздел ведется у нас из номера в номер с момента основания журнала. Публикуемые в нем задачи нестандартны, но для их решения не требуется знаний, выходящих за рамки школьной программы. Наиболее трудные задачи отмечаются звездочкой. После формулировки задачи мы обычно указываем, кто нам ее предложил. Разумеется, не все эти задачи публикуются впервые. Решения задач по математике и физике из этого номера следует отправлять по электронным адресам: [email protected] и [email protected] соответственно или по почтовому адресу: 119296 Москва, Ленинский проспект, 64-А, «Квант». Условия каждой оригинальной задачи, предлагаемой для публикации, вместе с Вашим решением этой задачи присылайте по тем же адресам. Задачи М2531 и М2532 предлагались на III Олимпиаде мегаполисов.

Задачи М2530–М2533, Ф2537–Ф2540

M2530. В остроугольном треугольнике на сторонах BC, CA, AB взяты точки $A_{1}, B_{1}, C_{1}$ соответственно так, что отрезки $AA_{1}, BB_{1}, CC_{1}$ пересекаются в одной точке. Известно, что BC ˜ $AA_{1} CA$ ˜ $BB_{1} AB$ ˜ $CC_{1}$. Докажите, что $AA_{1}, BB_{1}, CC_{1}$ – это высоты треугольника. П.Кожевников

M2531. Пусть k – натуральное число и $1 d_{0} d_{1}$ … $d_{m} 4 k$ – все положительные делители числа 4k. Докажите, что найдется i  ^ 1, …, m ` такое, что $d_{i} d_{i} 1 2$. И.Митрофанов

M2532. Аня и Максим играют в игру на клетчатой доске 100 u 100. Сначала Аня заполняет клетки доски целыми числами от 1 до 10 000 так, что каждое число встречается по одному разу. Затем Максим ставит фишку на одну из клеток самого левого столбца по своему выбору. Далее он за несколько ходов передвигает фишку в самый правый столбец. За один ход он может передвинуть фишку из клетки в любую соседнюю с ней по вершине или стороне. За каждую посещенную клетку (включая изначальную) Максим платит Ане такое число монет, которое написано на этой клетке. Максим хочет заплатить как можно меньше, Аня же хочет получить как можно больше. Сколько монет

заплатит Максим, если каждый из них будет действовать наилучшим для себя образом? Л.Шабанов

$M2533^{*}$. Дан тетраэдр. Пусть a и b – длины двух противоположных ребер тетраэдра, а D и E – величины двугранных углов при этих ребрах; c и d – длины ребер в другой паре противоположных ребер, а J и G – величины двугранных углов при этих ребрах. Докажите, что a + b = c + d тогда и только тогда, когда D E J G. М.Панов

Ф2537. Два одинаковых бруска сцеплены жесткой невесомой штангой и движутся по гладкой горизонтальной поверхности стола (см. рисунок). В некоторый момент бруски начинают въезжать на шероховатый участок стола. Найдите коэффициент трения P брусков о шероховатую поверхность, если они в начале движения имели скорость v, а после прохождения шероховатого участка стола движутся со скоростью u. Длина каждого бруска l, штанги s, шероховатого участка стола l + s. А.Иванов

Ф2538. Зимой помещение отапливается с помощью нагревателя, который на своей

17

ЗАДАЧНИК

Рис. 2

Пусть две параболы $G_{1}$ и $G_{2}$ (с параллельными осями) пересекаются в точках A и B (рис.2). Пусть прямая, проходящая через A, пересекает вторично $G_{i}$ в точке $A_{i} (i = 1,$ 2), а прямая, проходящая через B, пересекает вторично $G_{i}$ в точке $B_{i}$. Тогда $A_{1} B_{1} P A_{2} B_{2}$. А.Антропов, П.Кожевников

M2519. Назовем способ разбиения множества из 2n натуральных чисел на n пар бесквадратным, если ни в одной паре произведение чисел не является квадратом натурального числа. Известно, что для данных 2n различных натуральных чисел существует бесквадратный способ разбиения на пары. Докажите, что в таком случае существует не менее n! бесквадратных способов разбиения этих 2n чисел на пары.

Каждому натуральному числу m поставим в соответствие множество простых чисел P m, каждое из которых входит в разложение числа m в нечетной степени. Например, $P 2^{3}$ ˜ $7^{8}$ ˜ 11 ^ 2; 11 ` $, P 3^{4}$ ˜ $5^{6}$ ‡. Очевидно, произведение натуральных a и b является точным квадратом тогда и только тогда, когда множества P a и P b совпадают. Покрасим данные 2n чисел таким образом: числа, для которых множества P m совпадают, покрасим в один и тот же цвет, а для которых множества P m отличаются – в разные цвета. Поскольку существует бесквадратное разбиение на пары, в каждый цвет покрашено не более n чисел. Докажем следующую лемму, из которой сразу последует решение задачи.

«КВАНТА»

Лемма. Пусть 2n (различных) объектов покрашены в несколько цветов так, что в каждый цвет покрашено не более n объектов. Тогда существует не менее n! способов разбить эти объекты на разноцветные пары (т.е. так, чтобы в каждой паре были объекты разных цветов). Доказательство леммы. Проведем индукцию по n. База n = 1 очевидна. Докажем переход от n – 1 к n. Выберем цвет c, который встречается среди данных объектов наибольшее количество раз, т.е. пусть имеется k объектов цвета c, а объектов любого другого цвета не более k. Возьмем объект A цвета c и подберем для него пару B любого цвета d, отличного от c; это можно сделать 2n – k способами. При этом 2n k t n, так как k d n. Удалив пару A, B, мы получаем множество из 2 n 1 объектов. Проверим, что их покраска удовлетворяет условию леммы. Действительно, предположим противное, и объектов какого-то цвета e не меньше n. Цвет e отличен от c и d, так как после удаления A и B объектов каждого из цветов c и d осталось не более n – 1. Тогда k t n, и до удаления объектов A и B цвета c и e занимали по n объектов – противоречие (по меньшей мере еще есть объект B цвета d). Таким образом, мы можем воспользоваться предположением индукции. Значит, на каждый способ выбрать объект B для полученного множества из 2 n 1 объектов имеется не менее n 1! разбиений на разноцветные пары. Итого для множества из 2n объектов – не менее n n 1! разбиений на разноцветные пары. Лемма доказана, что завершает решение задачи. Укажем подход к другому решению. Введем вспомогательный граф: числам поставим в соответствие вершины (итого 2n вершин), а ребрами соединим пары вершин, для которых произведение чисел не равно точному квадрату. Нетрудно доказать, что в таком графе выполнено следующее условие переключения: если есть пара ребер AB и CD, где A, B, C, D – некоторые четыре различные вершины, то либо также есть пара ребер AC и BD, либо есть пара ребер AD и BC (условие пере-