Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2002/03/21.pdf Дата изменения: Fri Dec 23 19:26:52 2005 Дата индексирования: Tue Oct 2 00:12:18 2012 Кодировка: Windows-1251 Поисковые слова: созвездие лебедя

ЗАДАЧНИК

'КВАНТА'

21

Ввиду геометрического смысла задачи начальное n, для которого реализуется ее утверждение, равно 2. Тогда четыре точки, две красные и две синие, разделили окружность на четыре дуги. Если длина минимальной дуги равна l, то возможны два варианта для последовательно выписанных длин четырех дуг: (l, l + 1, l + 2, l + 1) и (l, l + 1, l, l + 1). И в том, и в другом варианте n-угольник с красными вершинами и n-угольник с синими вершинами будут 'двуугольниками', т.е. удвоенными хордами (хорда с красными концами и хорда с синими концами), и притом равной длины. Периметры таких двуугольников равны, а площади их тоже раны, ибо равны нулю. Обратимся к общему случаю. Выпишем последовательно длины 2n дуг, на которые разделена окружность: l1, l2 , l3 ,K, l2n . (1) При этом li - li +1 l2 n - l1 = 1. Наряду смотрим две другие по n чисел: l1 + и

= 1 для 1 ? i < 2n , а также с последовательностью (1) распоследовательности, содержащие
l2 , l3 + l4 , K, l2
n -1

+ l2 + l2

n

(2) . (3)

l2 n + l1, l2 + l3 , K, l2

n -2

n -1

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

б) человек заведомо хитрый, если он назвал честными не 300 человек; в) если а сказал, что b честный и S a не равно S b , то а хитрый. Действительно, если а был бы честным, то и b был бы честным и на все вопросы они дали бы одинаковые ответы. Исключим уже определенных хитрых из рассмотрения. Тогда оставшиеся люди разобьются на группы по 300 человек такие, что все люди из одной группы говорят про всех людей из этой же группы, что они честные, а про всех людей из остальных групп что они хитрые. Докажем это. Пусть а про 300 человек сказал, что они честные. Все эти люди дали такие же ответы (в противном случае они были бы заведомо хитрыми по способу в)). Никто другой не может сказать ни про одного из этих 300 человек, что он честный (способ а)). Так как максимальное количество групп по 300 человек три, то количество обнаруженных хитрых не меньше 100. Докажем, что при правильной стратегии хитрых мы сможем выявить не больше 100 хитрых людей. Хитрые должны создать две группы по 300 человек, и каждый из них должен говорить, что в его группе все честные, а все остальные хитрые. На более сложные вопросы типа 'Правда ли, что размер обуви самого высокого честного плюс количество букв в имени самого старого хитрого равняется простому числу?' каждый человек должен отвечать так, как он ответил бы, если бы его группа состояла из честных, а все остальные были бы хитрыми. Н.Васильев, Б.Гинзбург

>C

>C

М1799*.Натуральные числа х и у таковы, что сумма ху + х + у дает квадрат целого числа. Докажите, что найдется натуральное число z такое, что каждая из семи сумм xy + z, yz + x, zx + y, yz + y + z, zx + z + x, xy + yz + zx и xy + yz + zx + x + y + z дает квадрат целого числа.
Предъявим выражение натурального числа z в явном виде. Положим z = x + y + 2m + 1, где m = xy + x + y . Выпишем семь равенств:

М1798. Известно, что в некотором городе живут 1000 человек и ровно 300 из них честные. Остальных назовем хитрыми. На некоторые вопросы хитрые отвечают правду, а на некоторые лгут по своему усмотрению. Сколько хитрых людей мы можем обнаружить, задавая жителям произвольное число вопросов, при условии, что жители все друг о друге знают?
Мы сможем обнаружить 100 хитрых людей. Спросим каждого жителя про честность каждого, в том числе и про его собственную честность. Для каждого человека а обозначим множество людей, про которых а сказал, что они честные, через S a . Введем три способа определения заведомо хитрых людей: а) человек заведомо хитрый, если он сказал про себя, что он хитрый;

xy +

>C

Справедливость каждого из этих равенств проверяется непосредственно, и вместе с тем утверждение задачи доказано. Пар чисел х и у, удовлетворяющих условиям задачи, существует бесконечно много. В.Произволов

> C zx + z + x = > x + m + 1C , xy + z = > m + 1C , yz + x = > y + mC , zx + y = > x + mC , xy + yz + zx = > x + y + mC yz + zx + x + y + z = > x + y +
yz + y + z = y + m + 1 ,
2 2 2 2 2

2

,

m +1 .

C

2

6 Квант ? 3