Форум мира магии и волшебства

7/9 - решено (6 класс, районная олимпиада)

13/44 (8 класс, городская олимпиада)
Обозначим числа за a и b. Не умаляя общности предположим, что a
(1): b=(a/d1) + (a/d2) + (a/d3), 1(2)  a=(b/f1) + (b/f2) + (b/f3), 1Так как b>a, и b/a=(1/d1)+(1/d2)+(1/d3), то 1/d1 + 1/d2 + 1/d3 >1. Несложно установить, что d1=2, d2=3, а d3=4 либо d3=5.
В первом случае: 1/f1 + 1/f2 + 1/f3 = 12/13. 13 - число простое, значит, одно из чисел f1, f2, f3 делится на 13. И это число, очевидно,
не меньше 13. Значит, f3>=13. Следовательно: 1/f1 + 1/f2 + 1/f3 <= 1/2 + 1/3 + 1/13 < 12/13. Противоречие.
Аналогично проверяется и второй случай.
Следовательно, предположение (a

12/39 (7 класс, городская олимпиада СПб)
Допустим, что из Хрюкфилда пока ещё не добраться до Гавсфорда, но если построить какую-нибудь дорогу, например,
из Пафнутьевки в Большие Лесищи, то возможность добраться сразу появится. Теперь из Хрюкфилда можно будет проехать
в Гавсфорд, и, очевидно, что часть пути должна будет проходить по новой дороге Пафнутьевка - Большие Лесищи. Следовательно,
из Хрюкфилда уже сейчас безо всякого строительства можно добраться до Пафнутьевки.
А что бы было, если бы мы построили дорогу из Больших Лесищ в Пафнутьевку. Из Хрюкфилда опять можно бы было
добраться до Гавсфорда через новую дорогу Большие Лесищи - Пафнутьевка. Такис образом, можно добраться от Пафнутьевки
до Гавсфорда.
Итак, уже сейчас можно доехать от Хрюкфилда до Гавсфорда через Пафнутьевку. Полученное утверждение противоречит
сделанному предположению. Значит, всё-таки можно доехать от Хрюкфилда до Гавсфорда уже сейчас (правда, быть может,
не через Пафнутьевку).

14/48 (8 класс, городская олимпиада)
Пусть количество людей равно n. Расстаывим людей по кругу через равные расстояния (в вершинах правильного n-угольника).
Каждый два человека определяют сторону или диагональ этого многоугольника. Рассмотрим все тройки людей, соответствующих
равнобедренным треугольникам с вершинами в вершинах n-угольника, причем все равносторонние треугольники среди них
возьмём в 3 экземплярах (они встретятся, если n делится на 3). Нетрудно убедиться, что каждая сторона или диагональ
n-угольника входит ровно в 3 равнобедренных треугольника - один как основание, и два раза - как боковая сторона, а в случае
равностороннего - по одному разу из трёх экземпляров. Организуем дежурства, соответствующие равнобедренным треугольникам.
Тогда каждые 2 человека побывают ровно в 3 нарядах.

16/59 (7 класс, районная олимпиада)
Докажем по индукции, что произведение n различных натуральных чисел имеет не меньше n(n-1)/2  + 1 делителей.
Доказательство: очевидно

17/62 (10 класс, городская олимпиада СПб)
Ответ: 64
В интервале [3,19] имеется 7 простых чисел - 3,5,7,11,13,17,19. Обозначим их за p1,p2 ... p7.
Докажем, что удовлетворяющих условию чисел не может быть больше 64.
Для этого забудем пр число p7. Сумма любых чисел набора должна делиться хотя бы на одно из чисел p1 ... p6. Назовём
почти простое число малым по модулю p(i), если его остаток от деления на p(i) лежит в интервале [1, (p(i)-1)/2], и
большим по модулю p(i) в противном случае. Если сумма двух почти простых чисел делится на pi, то сумма их остатков
равна p(i). Значит, одно из чисел должно быть малым, а другое - большим по модулю p(i). Запишем около каждого из
чисел нашего набора последовательность из шести слов "малое" и "большое" в соответствии с остатками при делении
на p1 ... p6. Все полученные последовательности слов разлоичны. Действительно, если сумма двух чисел делится на p(i),
то соответствующие члены последовательности различаются заведомо в i-том слове. Посколько различных последовательностей
из 6 слов не более 2^6=64, то и чисел менее 64.
Теперь докажем, что существует набор из 64 чисел. Воспользуемся Китайской теоремой об остатках: для любых целых чисел
r1 ... r7 существует натуральное число n, сравнимое с r1 по модулю p1 и т.п. с r7 по модулю p7. Выпишем все возможные
последовательности из 7 чисел +1 и -1, в которых чётное число единиц. Таких последовательностей ровно 64 (т.к. первые
шесть членов можно выбирать произвольно, после чего последний выбирается однозначно). Любые две из этих последовательностей
различаются по крайней мере в двух местах, так как если бы они различались в одном, то в одной последовательности было бы
чётное число единиц, а в другой - нечётное, что противоречит выбору. Для каждой из этих последовательностей подберём
натуральное число, сравнимое по модулям p1 ... p7 с её членами. Очевидно, что все полученные числа почти просты.
Сумма двух таких чисел делится на p(i) тогда и только тогда, когда соответствующие последовательности различаются в i-том
члене. А поскольку любые две последовательности различаются хотя бы в двух местах, сумма любых двух чисел построенного
наборы делится на два или более чисел из p1 ... p7.