Условия и идеи решений задач



Скачать 257,25 Kb.
Дата20.05.2015
Размер257,25 Kb.
ТипРешение

Нижегородская (XI открытая) городская математическая олимпиада школьников

НИУ Высшая Школа Экономики – Нижний Новгород, 24 ноября 2013 года

УСЛОВИЯ И ИДЕИ РЕШЕНИЙ ЗАДАЧ


8 класс

1. Год проведения нынешней открытой городской олимпиады делится на её номер: 2013:11=183. Каким будет год последней олимпиады (если она и дальше будет проводиться ежегодно), для номера которой это свойство тоже будет выполнено?

Ответ: 4004 год. Решение: Пусть N  номер олимпиады. Тогда год его проведения равен (2013−11)+N=2002+N. Пусть год проведения делится на номер, т.е. 2002+N делится на N. Значит, 2002 делится на N. Тогда наибольший номер будет равен 2002, а годом проведения этой олимпиады будет 4004=2002+2002.

2. На окружности с центром Р и радиусом R отмечены точки О1, О2 и О3, которые являются центрами трёх окружностей радиуса R. Эти три окружности, кроме точки Р, пересекаются ещё второй раз между собой соответственно в точках А (первая и вторая окружности), В (вторая и третья окружности) и С (третья и первая окружности). Докажите, что ВС=О1О2.

Доказательство: Заметим, что РО1СО3 и РО2ВО3 – ромбы, т.к. все четыре стороны у них равны R (в частности, это могут оказаться и вырожденные ромбы в случае совпадения точек В и С с Р). Тогда отрезки О1С, РО3 и О2В равны и параллельны, значит, О1СВО2 – параллелограмм (возможно, вырожденный, если все четыре точки окажутся на одной прямой). Следовательно, ВС=О1О2, т.е. длина отрезка ВС не зависит от положения точки О3 при фиксированном положении точек О1 и О2.

Комментарий: Но … в приведённом выше решении есть серьёзная ошибка. К сожалению, здесь мы сталкиваемся с типичной ошибкой, допускаемой школьниками. Из равенства и параллельности отрезков АВ и CD не следует, что ABCD – параллелограмм. Возможно, что параллелограммом окажется четырёхугольник ABDC или же все четыре точки окажутся на одной прямой, т.е. получим «вырожденный» параллелограмм.

Таким образом, в нашей задаче из равенства и параллельности отрезков О1С и О2В ещё не следует, что параллелограммом будет именно четырёхугольник О1СВО2 (возможно вырожденный). Это будет верно только в случае сонаправленности (коллинеарности) векторов и , что в нашей задаче как раз и будет верным, т.к. эти векторы равны вектору . Но подобное рассуждение относится к концу школьной программы 8-го класса. Поэтому полный балл за решение задачи, возможно, будет ставиться только в случае объяснения расположения точек или другого верного рассуждения, а приведённое выше решение будет оцениваться из 6 баллов. Например, если подсчётом углов будет показано равенство треугольников (возможно вырожденных) О1О2Р и СВО3, откуда следует нужное нам равенство отрезков О1О2 и ВС, то за подобное рассуждение уже можно будет получить 7 баллов.

3. Разрежьте клетчатую фигуру, представленную на рисунке, на две равные части двумя разными способами.

Решение: см. три возможных разрезания на рисунке справа.

4. Докажите для любых действительных чисел a0 и b неравенство: .

Доказательство 1: Перенесём все числа в левую часть и преобразуем её: . Получим верное неравенство, значит, и исходное равносильное ему неравенство также будет верным.

Доказательство 2:

Дважды применим неравенство Коши () для двух пар неотрицательных чисел: .

Комментарий: Второе доказательство фактически является переложением первого доказательства через выделение полных квадратов на язык неравенства Коши, т.к. само по себе неравенство Коши равносильно выделению полного квадрата: . Важно только учесть, что b может оказаться отрицательным числом, значит, надо грамотно провести оценки, пользуясь модулем. Кроме того, если сразу умножить обе части неравенства на положительное число a2, то после переноса в левую часть всех слагаемых получим многочлен, в котором увидеть сумму двух полных квадратов будет значительно легче, догадавшись представить 2 суммой единиц: .

5. В треугольнике ABCB=60°. На сторонах AB и BC нашлись такие точки P и Q соответственно, что AP=CQ и AP+PQ=AC. Докажите, что треугольник ABC – равносторонний.

Доказательство: Построим отрезок PC', равный и параллельный отрезку QC, так, что C'PQC – параллелограмм. Тогда, из параллельности, следует, что APC'=ABC=60 и AP=CQ=C'P. Следовательно, треугольник APC' – равносторонний, откуда AC'=AP. Но тогда AC=AP+PQ=AC'+CAC по неравенству треугольника. Следовательно, в силу равенства левой и правой частей полученного неравенства точка C' лежит между A и C, значит, BAC=РAC'=60, т.е. в треугольнике ABC уже два угла равны 60°, значит, и все три угла равны 60, тогда он  равносторонний.

6. В вершинах квадрата расставлены произвольным образом 4 различных натуральных числа. На каждой стороне и диагонали квадрата записывают числа, равные НОДу (наибольшему общему делителю) чисел, стоящих в концах соответствующего отрезка. Могло ли оказаться так, что сумма четырёх чисел в вершинах равна сумме шести чисел на сторонах и диагоналях?

Ответ: Нет. Решение 1: Докажем, что для двух различных натуральных чисел n и k (пусть n>k) выполняется неравенство НОД(n,k)(n+k)/3, при этом равенство выполняется только в случае n=2k. Если n=2k, то НОД(n,k)=k=(2k+k)/3=(n+k)/3. Если n2k, то НОД(n,k)n/3<(n+k)/3. Предположим, что для четырёх чисел в вершинах (a, b, c, d) выполняется нужное нам равенство. Тогда a+b+c+d = НОД(a,b) + НОД(a,c) + НОД(a,d) + НОД(b,c) + НОД(b,d) + НОД(c,d) (a+b)/3+(a+c)/3+(a+d)/3+(b+c)/3+(b+d)/3+(c+d)/3 = a+b+c+d. Значит, во всех шести неравенствах должны быть равенства, что может выполняться согласно доказанному выше только в случае, когда в каждой паре одно число больше другого в два раза. Тогда наибольшее из чисел в два раза больше каждого из остальных, т.е. в наборе должно быть три одинаковых числа.

Решение 2: В силу симметрии числа можно упорядочить по убыванию: a>b>c>d. НОД двух различных натуральных чисел не превышает меньшего из них и не превышает половины большего из них. Тогда НОД(a,b)≤a/2, НОД(a,c)≤a/2, НОД(a,d)≤d, НОД(b,c)≤b/2, НОД(b,d)≤b/2, НОД(c,d)≤c/2, значит, НОД(a,b) + НОД(a,c) + НОД(a,d) + НОД(b,c) + НОД(b,d) + НОД(c,d) ≤ a/2+a/2+d+b/2+b/2+c/2 = a+b+c/2+d < a+b+c+d, т.е. сумма шести НОДов меньше суммы четырёх исходных чисел.

9 класс

1. На доске выписаны все натуральные делители некоторого точного квадрата n2 по возрастанию . Докажите, что сумма не может равняться 2013. (задача предложена Дмитрием Лиминым, 11 класс, лицей №180 г.Н.Новгорода)

Решение: Предположим, что сумма  нечётное число. Тогда это два числа разной чётности с произведением  чётным числом. Значит, n² делится на 2, следовательно, имеет делитель 2, равный . Но число является нечётным, т.е. число делится на 2, но не делится на 4, что невозможно для точного квадрата. Противоречие.

2. Некоторая окружность, центр которой совпадает с центром вписанной в треугольник окружности, пересекает каждую сторону треугольника в двух различных точках. Докажите, что она высекает на всех трёх сторонах равные отрезки.

Доказательство 1: При симметрии относительно биссектрисы угла ABC, которая проходит через центр вписанной окружности, данная окружность перейдёт сама в себя, а прямая BA перейдёт в прямую BC. Следовательно, отрезок, высекаемый окружностью на AB, симметричен отрезку, высекаемому ею на BC, т.е. эти отрезки равны. Аналогично, равны и все три требуемых отрезка.

Доказательство 2: Пусть радиус вписанной окружности равен r, а радиус новой окружности равен R. Тогда на каждой стороне треугольника новая окружность высекает отрезок фиксированной длины , что очевидным образом получается при рассмотрении треугольника KPI, где I – центр вписанной окружности, KP – высекаемый отрезок. Если взять середину М отрезка КР, которая одновременно будет точкой касания вписанной окружности, то из прямоугольного треугольника MPI по теореме Пифагора найдём . Тогда отрезок КР=2МР=.Отсюда получаем, что все высекаемых отрезка будут иметь одну и ту же длину.

3. На острове рыцарей и лжецов (рыцари всегда говорят правду, лжецы всегда лгут) за круглым столом собралась компания из 2013 человек. Каждый заявил, что среди половины остальных, сидящей от него справа, лжецов столько же, сколько рыцарей среди половины остальных, сидящей от него слева. Сколько могло быть рыцарей за столом?

Ответ: 0 или 1007 рыцарей. Решение: Возможен случай, когда за столом собрались только лжецы,  тогда действительно каждый лжец соврал, т.к. в половине справа от него 1006 лжецов, а в половине слева от него 0 рыцарей, т.е. высказывание является неверным. Рассмотрим теперь случай, когда за столом сидит хотя бы 1 рыцарь. Тогда пусть справа от него n лжецов и соответственно (1006-n) рыцарей, а слева - n рыцарей. Значит, кроме него за столом ещё (1006-n)+n=1006 рыцарей. Таким образом, за столом будет 1007 рыцарей, каждый из которых сказал правду вне зависимости от соответствующего ему числа n, рассмотренного выше. При этом каждый лжец действительно соврал, т.к. из его высказывания аналогичным образом получается, что за столом должны сидеть 1006 рыцарей, но там сидят 1007 рыцарей.

4. Сколько существует решений ребуса ? (Одинаковые буквы – одинаковые цифры, разные буквы – разные цифры.)

Ответ: 864 решения. Доказательство: Заметим, что у нас используются 9 цифр, значит, среди них нет нуля и они принимают все 9 ненулевых значений. Кроме того, после сокращения одинаковых множителей получим , при этом пропали Р и М, которые обязаны принимать значения 5 и 7, иначе эти простые множители не сократятся и выражение не будет равно 1/2 (получаем два варианта для букв Р и М.) В разложении на простые множители всех других ненулевых 7 цифр остались четыре тройки и семь двоек. При этом тройки должны сократиться, значит, 3 и 6 идут в одну часть дроби, а 9  в другую. Кроме того, в числителе должны оказаться три двойки, а в знаменателе  четыре. 1 случай.) Если в числитель взять 3 и 6, тогда туда ещё пойдёт 4. Для букв Т, Е, О эти три цифры дадут 3!=6 вариантов. Оставшиеся четыре буквы знаменателя принимают значения 1, 2, 8, 9  всего 4!=24 варианта. С учётом двух вариантов букв Р и М получим 2624=288 решений ребуса. 2случай.) Если в числитель пойдёт 9, то две оставшиеся цифры равны либо 1 и 8, либо 2 и 4. Тогда для каждого из этих случаев аналогично будет по 288 решений. Значит, всего 3288=864 решений ребуса.

Комментарий: Действительно известно много теорем, носящих имя Архимеда, в частности, о знаменитой теореме Архимеда, изучаемой в школе без названия и связанной с отношением 1:2, можно прочитать в книге М.Б.Балка и В.Г.Болтянского «Геометрия масс» (библиотечка «Квант», выпуск 61, с.9).

5. Боря и Вова играют в следующую игру на изначально белой доске 88. Боря ходит первым и каждым своим ходом закрашивает в чёрный цвет любые четыре белые клетки. После каждого его хода Вова закрашивает полностью в белый цвет какой-нибудь ряд (строку или столбец). Боря стремится закрасить как можно больше клеток, а Вова стремится ему помешать. Какое наибольшее количество чёрных клеток может оказаться на доске после хода Бори?

Ответ: 25 клеток. Решение: Пусть Вова каждым своим ходом делает белым ряд с наибольшим количеством чёрных клеток. Тогда, как только Боря добьётся ряда из не менее чем четырёх чёрных клеток (такой ряд будем называть «богатым»), Вова будет удалять минимум четыре клетки, значит, следующим ходом Боря не сможет увеличить количество чёрных клеток в сравнении со своим предыдущим ходом. И далее при наличии богатых рядов Вова удаляет минимум 4 чёрных клетки, а Боря после этого добавляет четыре, значит, увеличить свой максимальный результат не сможет. При этом перед первым и всеми последующими моментами создания богатого ряда при их отсутствии на доске была максимум 73=21 чёрная клетка  семь рядов по 3 чёрных клетки, т.к. только что Вова сделал белым ряд этого направления. Таким образом, Боря всегда создаёт конструкцию с максимум 25 чёрными клетками. Покажем теперь, что Боря может добиться 25 чёрных клеток. Выделим на доске 24 клетки так, как показано на рисунке,  по три в каждом ряду. Пусть Боря закрашивает всегда только клетки этого множества, пока среди них есть белые клетки. Тогда Вова сможет удалить максимум три чёрные клетки, значит, количество чёрных клеток после каждой пары их ходов будет хотя бы на одну больше. Значит, в некоторый момент Боря сможет сделать чёрными все эти клетки (и ещё, возможно, какие-то). Тогда после хода Вовы останется не менее 21 чёрной клетки, а Боря своим следующим ходом добьётся минимум 25 чёрных клеток. Значит, при правильной игре обоих максимальное количество чёрных клеток на доске будет равно 25.

6. ABCDEFGH правильный восьмиугольник. M, N, K середины отрезков AC, DE и АF соответственно. Докажите, что отрезки MN и CK равны и перпендикулярны. (задача предложена Григорием Коноваловым, 10 класс, лицей №165 г.Н.Новгорода)

Доказательство: Из свойств правильного восьмиугольника следует, что при повороте на 90 (на нашем чертеже это поворот по часовой стрелке) относительно центра многоугольника О точки А, С и D перейдут соответственно в точки С, Е и F. Значит, перпендикулярны и равны отрезки в парах АС, СЕ и AD, CF, т.е. равны по длине и перпендикулярны соответствующие вектора в этих парах. Заметим теперь, что вектор , а вектор . Учитывая указанные выше равенство длин и перпендикулярность векторов, получаем, что при повороте на 90 (по часовой стрелке) вектора и перейдут в вектора и , значит, их полусуммы перейдут друг в друга, т.е. вектора и равны по длине и перпендикулярны.
10 класс

1. Докажите, что НОК (наименьшее общее кратное) четырёх натуральных чисел a, b, c и d не может равняться ab+cd.

Доказательство: Т.к. НОК делится на каждое из чисел, то сумма ab+cd должна делиться на каждое из четырёх исходных чисел. Тогда cd делится не только на числа c и d, но и на числа a и b, т.к. первое слагаемое делится на a и b. Значит, cd делится на каждое из чисел, т.е. будет не меньше НОК (a,b, cd) ≥ НОК (a, b, c, d). Тогда ab+cd будет больше НОК (a, b, c, d).

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

Ответ: нет. Доказательство: Так как любой правильный многоугольник является вписанным, то все треугольники разбиения вписаны в одну общую окружность. Но если треугольник прямоугольный, то центр его описанной окружности должен совпадать с серединой гипотенузы. Таким образом, вершины при острых углах прямоугольного треугольника, если такой имеется среди треугольников разбиения, должны быть диаметрально противоположны, но в силу нечётности количества вершин нашего правильного многоугольника таких вершин не будет.

3. Найдутся ли три различных действительных числа таких, что при любой расстановке их в качестве трёх коэффициентов у уравнения ax2+bx+c=0 есть корень, причём любой корень является целочисленным?

Решение: Да, например, набор чисел 1, 0, 1. Тогда каждое из шести возможных уравнений x1=0, x+1=0, x21=0, x2x=0, x2+x=0 и x2+1=0 будет иметь корни, причём только целочисленные.

4. Пусть a, b, c, d, e – различные натуральные числа. Докажите, что 288  наибольшее натуральное число, на которое гарантированно делится произведение всех попарных разностей (ab)(ac)(ad)(ae)(bc)(bd)(be)(cd)(ce)(de).

Доказательство: Докажем сначала, что данное произведение делится хотя бы на 5-ю степень двойки. Возможны несколько случаев. 1) Есть не менее 4-х чисел одинаковой чётности, тогда каждая из их попарных разностей будет чётной, а всё произведение будет делиться хотя бы на 26. 2) Два числа одной чётности и три числа другой чётности, среди которых ещё и найдётся пара чисел с одинаковым остатком при делении на 4. Тогда разность чисел первой пары делится на 2, а среди трёх чётных попарных разностей тройки остальных чисел хотя бы одна будет делиться на 4=2². Значит, всё произведение попарных разностей разделится на 1+2+1+1=5-ю степень двойки. Кроме того, по принципу Дирихле, среди наших 5 чисел найдутся 2 числа с одинаковым остатком при делении на 3, тогда их разность делится на 3. Уберём одно из них, тогда среди оставшихся 4-х чисел аналогично найдётся разность, кратная 3. Таким образом, всё произведение гарантированно делится на 2532=288. Заметим теперь, что для набора из первых пяти натуральных чисел данное произведение равно (21)(31)(41)(51)(32)(42)(52)(43)(53)(54)=123412312=2532=288, значит, у нас есть гарантированная делимость только на 288  и это наибольший возможный делитель всего произведения.

5. Точки М и Н – соответственно точка пересечения медиан и ортоцентр треугольника АВС, в котором углы А и В равны соответственно 30 и 45. Докажите, что МН=2МС.

Доказательство 1: Рассмотрим О  центр описанной окружности треугольника АВС. Тогда требуемое нам условие сводится к доказательству того, что МО=МС, т.к. известно, что точки О, М и Н лежат на одной прямой  прямой Эйлера, а ОМ:МН=1:2. Доказательство того, что МО=МС,  см. решения задачи 11.2.

Комментарий: Прямая Эйлера и соотношение ОМ:МН=1:2 являются классическими общеизвестными фактами геометрии, но, к сожалению, игнорируются школьной программой, как и многие другие замечательные теоремы.

Доказательство 2 (аналитическое): Введём систему координат, в которой начало координат будет в точке С’ основании высоты СС’, а у точек В и С будут координаты (1; 0) и (0; 1). Подсчёт углов показывает, что НАВ=А’АВ=90АВА’=9045=45, а НВА=В’ВА=90В’АВ=9030=60. Тогда координаты точек Н и А будут соответственно равны и . Середина Р отрезка АВ будет иметь координаты , точка М в силу отношения РМ:МС=1:2 будет иметь координаты . Подставив координаты точек М, Н и С, нетрудно проверить, что выполняется равенство МН=2МС.

6. Боря и Вова играют в следующую игру на изначально белой доске 1616. Боря ходит первым и каждым своим ходом закрашивает в чёрный цвет любые k белых клеток. После каждого его хода Вова закрашивает полностью в белый цвет какой-нибудь ряд (строку или столбец). Боря выиграет, если после некоторого его хода более половины клеток будут чёрными. При каком наименьшем k Боря может выиграть независимо от игры Вовы?

Ответ: при k=9. Решение: Пусть Вова каждым своим ходом делает белым ряд с наибольшим количеством чёрных клеток. Тогда, как только Боря добьётся ряда из не менее чем k чёрных клеток (такой ряд будем называть «богатым»), Вова будет удалять минимум k клеток, значит, следующим ходом Боря не сможет увеличить количество чёрных клеток в сравнении со своим предыдущим ходом. И далее при наличии богатых рядов Вова удаляет минимум k чёрных клеток, а Боря после этого добавляет k, значит, увеличить свой максимальный результат не сможет. При этом перед первым и всеми последующими моментами создания богатого ряда при их отсутствии на доске было максимум 15(k1) чёрных клеток  15 рядов по (k1) чёрных клеток, т.к. только что Вова сделал белым ряд этого направления. Таким образом, Боря всегда создаёт конструкцию с максимум 16k15 чёрными клетками. Покажем теперь, что Боря может добиться 16k15 чёрных клеток. Выделим на доске 16(k1) клеток так, как показано на рисунке,  по (k1) в каждом ряду  со сдвигом на одну клетку в каждом следующем ряду. Пусть Боря закрашивает всегда только клетки этого множества, пока среди них есть белые клетки. Тогда Вова сможет удалить максимум (k1) чёрных клеток, значит, количество чёрных клеток после каждой пары их ходов будет хотя бы на одну больше. Значит, в некоторый момент Боря сможет сделать чёрными все эти клетки (и ещё, возможно, какие-то). Тогда после хода Вовы останется не менее 15(k1) чёрных клеток, а Боря своим следующим ходом добьётся минимум 16k15 чёрных клеток. Значит, при правильной игре обоих максимальное количество чёрных клеток на доске будет равно 16k15. Боре надо, чтобы это число было более половины клеток, т.е. более 162/2=128. Тогда 16k15129, откуда k(129+15)/16=9.
11 класс

1. Найдите все пары квадратных трехчленов ax2+bx+c и bx2+cx+a, каждый из которых имеет ровно один действительный корень.

Ответ: ax2+4ax+4a и 4ax2+4ax+a, где a  любое действительное ненулевое число. Решение: Если каждый трехчлен имеет один действительный корень, то их дискриминанты равны нулю. Значит, нам необходимо решить систему уравнений при условии, что старшие коэффициенты трехчленов не равны 0 (т.е. a0 и b0), но тогда из второго уравнения получаем, что и с0. Разделим первое уравнение на второе, что можно делать при ненулевых числах, тогда получим равенство , откуда b3=c3, т.е. b=c. Подставив это условие, получим, что b=c=4a. Тогда наши уравнения примут вид ax2+4ax+4a и 4ax2+4ax+a, у которых по одному корню (2) и (0,5) соответственно.

2. Точки М и О – соответственно точка пересечения медиан и центр описанной окружности треугольника АВС, в котором углы А и В равны соответственно 30 и 45. Докажите, что МО=МС.

Решение 1: Центральный угол СОВ равен 2САВ=60, значит, равнобедренный треугольник ВОС (ВО и ОС – радиусы описанной окружности) является равносторонним. Тогда прямая ВК, проходящая через середину К стороны ОС будет серединным перпендикуляром отрезка ОС и будет параллельна ОА, т.к. центральный угол СОА равен 2СВА=90. Значит, на прямой ВК лежит средняя линия КЕ треугольника АОС, где Е – середина стороны АС. Таким образом, отрезок ВЕ – медиана исходного треугольника АВС, на нём лежит точка пересечения медиан М, и при этом прямая ВЕ совпадает с прямой ВК – серединным перпендикуляром отрезка ОС. Следовательно, точка М лежит на этом серединном перпендикуляре и равноудалена от концов отрезка ОС, т.е. МО=МС, что и требовалось доказать.

Решение 2 (аналитическое): Введём систему координат с началом в точке О так, что радиус описанной окружности равен 1, а координаты точек А, В и С с учётом углов исходного треугольника окажутся соответственно следующими (0; 1), и (1; 0). Тогда точка Р (середина отрезка АВ) имеет координаты . Точка М делит медиану СР в отношении РМ:МС=1:2, значит, абсцисса точки М будет равна , следовательно, М лежит на серединном перпендикуляре к отрезку ОС, т.е. равноудалена от его концов, что и требовалось доказать.

3. Действительные числа x, y и z таковы, что . Верно ли, что x=y=z?

Ответ: нет, например, при x= 2, y=1, z= 0,5 все три суммы будут равны (1). Решение: Преобразуем наши равенства к виду , и . Перемножим эти три равенства и разделим на произведение (xy)(yz)(zx)0 при условии, что все числа  различны. Тогда получим, что x2y2z2=1. После этого остаётся подобрать тройку различных чисел, удовлетворяющих нашим равенствам.

4. Существует ли 2013-значное число вида 22…200…011…133…3, которое делится на 2013?

Ответ: существует, например, число . Доказательство 1: Рассмотрим репьюнит R60, состоящий из 60 единиц. По признаку делимости на 3 он делится на 3, т.к. его сумма цифр, равная 60, делится на 3. По признаку делимости на 11 он делится на 11, т.к. его знакочередующаяся сумма цифр, равная 0, делится на 11. Докажем теперь, что он делится на 61. По малой теореме Ферма число 10601 делится на простое число 61. Но 10601==9R60, при этом 9 и 61 – взаимно просты, значит, на 61 делится число R60. Таким образом, нами доказано, что репьюнит R60 делится на простые числа 3, 11 и 61, значит, он делится и на их произведение 31161=2013. Тогда 2013-значное число равно (2101953+1060+3)R60 и делится на 2013 за счёт множителя R60.

Доказательство 2 (не указывающее такое число, но доказывающее его существование с помощью принципа Дирихле): Докажем с помощью принципа Дирихле, что существует репьюнит, содержащий не более 61 единицы и кратный 61. Рассмотрим ряд из 62 репьюнитов: 1, 11, 111, 1111, …, . При делении на 61 эти числа могут давать 61 вариант остатков от 0 до 60. Значит, по принципу Дирихле в этом наборе репьюнитов найдутся два с равными остатками при делении на 61, например, из k и n единиц, где 1k<n62, 1nk=p61. Тогда разность этих репьюнитов делится на 61, т.е. RnRk=Rp10k61, но 10 и 61 взаимно просты, значит, на 61 делится некоторый репьюнит Rp, где 1p61. Кроме того, на 61 разделится и любой репьюнит, состоящий из количества единиц, кратного p, в частности, состоящий из 6р единиц. При этом такой репьюнит разделится на 3, т.к. его сумма цифр 6р делится на 3, а также разделится на 11, т.к. содержит чётное количество единиц и его знакочередующаяся сумма цифр, равная 0, делится на 11. Таким образом, нами доказано, что репьюнит R6р делится на простые числа 3, 11 и 61, значит, он делится и на их произведение 31161=2013. Заметим теперь, что 6р661=366. Рассмотрим теперь число вида , где 2013320133366=915. Оно равно (21020136р+106р+3)R6р и делится на 2013 за счёт множителя R6р.

Комментарий 1: Во втором доказательстве принципиальным является известный факт о том, что для любого простого p, не меньшего 7, существует кратный р репьюнит длины, не большей р. Классическими являются три доказательства этого утверждения. Первое – следствие из малой теоремы Ферма с указанием того, что таким числом является непосредственно репьюнит длины р1. Второе следует из принципа Дирихле. Третье доказательство приведём далее, воспользовавшись леммой о «хороводах» из теории графов: «Если в графе все вершины имеют степень 2, то граф представляет из себя один или несколько непересекающихся циклов» или «Если несколько людей возьмётся за руки, то они составят один или несколько хороводов». Возьмём ряд репьюнитов 1, 11, 111, … и начнём его с нуля. Тогда каждый следующий репьюнит получается из предыдущего с помощью операции «умножить на 10 и прибавить 1». Рассмотрим теперь ориентированный граф остатков для нашей операции. Вершинами графа будут остатки, рёбромстрелкой будет переход с помощью нашей операции к следующему остатку. Например, по модулю 7 наш орграф будет состоять из цикла 0146520 и петли 33, т.е. подчиняется лемме о хороводах. Докажем это для произвольного простого р7. Заметим, что из каждой вершины очевидным образом выходит одна стрелка. Докажем теперь, что и входит одна. Предположим, что остаток a получается из двух различных остатков b и с. Тогда а10b+110c+1(mod p), 10b10c(mod p), значит, в силу взаимной простоты 10 и р (т.к. р – простое число, не меньшее 7) получим, что bc(mod p), т.е. b и с будут равными остатками. Значит, к вершине приходит не более одной стрелки. Но всего р стрелок и р вершин-остатков, к каждой из которых приходит не более одной стрелки. Следовательно, к каждой вершине приходит ровно одна стрелка. Значит, в нашем орграфе степень каждой вершины равна двум по одной стрелке входит и выходит. Тогда граф подчиняется лемме о хороводах и образует из себя один или несколько циклов. Но заметим, что находимся в цикле, начинающемся 0111(mod p), значит, нам постоянно будут встречаться репьюниты с остатком 0, причём длина цикла не превосходит количества остатков р. Т.е. нами доказано, что среди первых р репьюнитов есть репьюнит, кратный р.

Комментарий 2: Все три предъявленных решения связаны с классическими идеями и показывают необходимость изучения подобного рода идей, выходящих за рамки школьной программы. К таковым же относится барицентрический метод, использованный во втором решении задачи 11.5, и идея сжатия нескольких вершин графа в одну, применённая в последней задаче варианта 11.6.

Комментарий 3: Сравним нашу задачу с задачами №5 для 11-го класса олимпиад 2007-го и 2011-го годов. В них мы аналогично первому доказательству также пользовались числом из р1 девятки, которое делится на простое число р согласно малой теореме Ферма.

5.11.2007. Доказать, что число из 2000 восьмёрок делится на 2008.



Доказательство: Заметим, что согласно малой теореме Ферма число =10250-1 делится на простое число 251, но 9 и 251 – взаимно просты, значит, на 251 делится число из 250 единиц. Тогда на 251 делится и число из в восемь раз большего количества единиц (из 2000), следовательно, число из 2000 восьмёрок делится на 2518=2008.

5.11.2011. Сколько существует 2011-значных чисел, делящихся на 2011?



Ответ: [9102010:2011]. Решение: Заметим, что 2011 – простое число, значит, по малой теореме Ферма самое маленькое 2011-значное число 1020101 (mod 2011), т.е. имеет остаток 1 при делении на 2011, значит, каждое 2011-е число этого ряда будет делиться на 2011, а таких чисел будет [9102010:2011], где [x] – целая часть числа x.
Вывод: К ОЛИМПИАДАМ НАДО ГОТОВИТЬСЯ! В том числе, отрешав задачи предыдущих лет! :
5. Прямая, проходящая через центр О сферы, описанной около правильной треугольной пирамиды SАВС со стороной основания, равной 1, пересекает сферу в точках D и М соответственно. Точки K, L, N, P, E, F  середины отрезков BD, DC, CM, MA, KN и LP соответственно. Докажите, что длина отрезка EF не зависит от положения прямой DM и найдите его длину.

Ответ: . Решение 1: Известно, что вектор, соединяющий середины сторон любого четырёхугольника (выпуклого, невыпуклого, звёздчатого и даже неплоского) равен полусумме векторов на двух других сторонах. Тогда, рассмотрев неплоские четырёхугольники KPLN, BDMA и среднюю линию треугольника DMC, получим, что . Значит, длина отрезка FE будет равна четверти стороны квадрата, т.е. .

Комментарий: 1). На самом деле не является принципиальным то, что нам дана правильная треугольная пирамида и диаметрально противоположные точки D и М, т.к. независимо от этих условий. 2). Нами приведён чертёж для аналогичной планиметрической задачи: «Прямая, проходящая через центр О описанной окружности правильного треугольника АВС со стороной 1, пересекает малые дуги ВС и СА описанной окружности в точках D и М соответственно. Точки K, L, N, P, E, F середины отрезков BD, DC, CM, MA, KN и LP соответственно. Докажите, что длина отрезка EF не зависит от положения прямой DM и найдите длину этого отрезка.»

Решение 2 (барицентрический метод): Рассмотрим систему материальных точек 1A, 1D, 1C и 1М, тогда точка F окажется её барицентром (центром масс), т.к. по теореме о группировке масс барицентр будет находиться в середине отрезка, соединяющего середины двух противоположных сторон, а F по условию является серединой отрезка LP, соединяющего середины отрезков DC и МА. Но заметим теперь, что точки D и М – диаметрально противоположные, значит, их центр масс окажется в точке О. Тогда барицентр всей системы также делит пополам отрезок, соединяющий О с серединой G отрезка АС, а это конкретная точка внутри сферы. Для системы материальных точек 1B, 1D, 1C, 1M аналогично показывается, что её барицентр E является серединой отрезка, соединяющего О с серединой H отрезка ВС. Значит, точки Е и F фиксированные точки внутри сферы, а длина этого отрезка средней линии треугольника OGH равна половине длины GH, которая в свою очередь равна половине АВ, т.к. GH является средней линией треугольника АВС. Таким образом, . Кроме того, нами ещё показано, что положение точек E и F не зависит от положения прямой DM, что, конечно же, является более сильным фактом, чем требуемое в задаче.

6. На клетчатой доске закрасили несколько клеток в красный цвет так, что каждая красная клетка соседствует (по стороне или вершине) хотя бы с тремя красными клетками. После этого для каждой пары соседних красных клеток отметили стрелкой направление хода королём, а в обратную сторону ходить запретили. Оказалось, что король с любой красной клетки может пройти на любую другую красную клетку по стрелкам. Докажите, что вместо одной из стрелок можно поставить знак запрета хода так, чтобы король по-прежнему смог с любой красной клетки пройти на любую другую красную клетку по стрелкам. (Вариация на тему классического факта. См. также задачу М412, журнал «Квант», №7, 1977 г.)

Доказательство: Докажем требуемое утверждение индукцией по количеству красных клеток, используя в рассуждениях ориентированный граф (орграф), где вершины  красные клетки, ориентированные рёбра  стрелки. Т.к. из любой вершины до любой другой есть ориентированный путь, то этот орграф по условию  сильно связен, тогда в нём есть простой цикл, т.е. цикл без повторяющихся вершин. Разрешим присутствие в нашем графе стрелкам-петлям и кратным рёбрам, соединяющим две вершины несколько раз. Важно только, чтобы степень каждой вершины была не менее трёх, а сам орграф был сильно связным.

Базы индукции  2 и 3 вершины. Если имеем 2 вершины, тогда между ними в силу сильной связности орграфа есть стрелки противоположного направления. Оставим такие две стрелки, идущие в разные стороны, а одну из остальных сотрём (запретим ход короля). Если имеем 3 вершины (А, В, С), то возможны два случая. Есть гамильтонов цикл АВСА. Тогда удалим любую другую стрелку, которые ещё есть, т.к. каждая вершина имеет степень не менее 3. Если нет гамильтонова цикла, то в силу условия сильной связности должен быть путь вида АВС и путь в обратную сторону СВА, значит, опять удалим любую другую стрелку, которые ещё есть у вершин А и С.



Пусть вершин в графе более трёх. Рассмотрим простой цикл, который в нашем графе клеток очевидным образом содержит не менее трёх вершин в силу того, что у нас цикл ходов короля содержит не менее трёх клеток. Если цикл содержит все вершины, то удалим любую стрелку, не входящую в цикл, а такие стрелки в силу условия есть. Если нет цикла, содержащего все вершины, то изменим наш граф, объявив этот цикл новой вершиной, а стрелками будут стрелки, не входящие в цикл. При этом у нас, возможно, появятся стрелки-петли, начинающиеся и заканчивающиеся в новой вершине, или кратные рёбра, соединяющие две вершины несколько раз. При этом новая вершина удовлетворяет условию, что у неё степень не меньше трёх, т.к. в новую вершину объединились не менее трёх вершин, от каждой из которых осталось ещё хотя бы по одной стрелке. Кроме того, наша «перепланировка» графа могла только сократить некоторые маршруты и он является сильно связным. Значит, мы получили орграф, удовлетворяющий условиям задачи и имеющий меньшее количество вершин. По предположению индукции в нём есть «лишняя» стрелка, которой соответствует стрелка старого графа. Удалим эту стрелку. Убедимся теперь, что наш исходный граф без этой стрелки также является сильно связным. Действительно, рассмотрим любые две вершины А и В исходного графа, не вошедшие в новую «объединённую» вершину, и маршрут, соединяющий их в новом графе и не проходящий через стёртую стрелку. Перенесём этот маршрут в исходный граф. Если этот маршрут не проходил через новую вершину, то он соединяет А и В. В противном случае он разобьётся на две части: до цикла и после цикла. Добавив к нему соответствующую часть цикла, мы получим нужный маршрут, соединяющий А и В в исходном графе и не проходящий через закрытую стрелку. Если А или В оказалась входящей в «объединённую», тогда есть путь, часть которого проходит по циклу, а другая часть по соответствующему участку старого графа. Если обе вершины входят в объединённую, то между ними есть пути по циклу.

Таким образом, в силу принципа математической индукции требуемый нам факт является доказанным.

Похожие:

Условия и идеи решений задач iconК. А. Джафаров методы и модели в экономике Глава Элементы математического программирования Под принятием решений
Под принятием решений понимается сложный процесс, в котором можно выделить 4 основных этапа
Условия и идеи решений задач icon3. Идеи, охватывающие проблему «природа и общество»
Формирование у учащихся географической культуры как составной части общей культуры человека относится к числу наиболее важных задач...
Условия и идеи решений задач iconПрограмма составлена доктором физ мат наук Поповой С. Н
Основные свойства линейных систем обыкновенных дифференциальных уравнений. Теорема существования и единственности. Фундаментальная...
Условия и идеи решений задач iconГ. П. Сикорская Реализация идеи ноосферного образования в Уральском регионе
Давыдов, Ш. А. Амонашвили, В. А. Сухомлинский многие другие. Их идеи, мысли, теории и практика на принципах гуманного прагматизма...
Условия и идеи решений задач iconЛекция по курсу «Методы оптимальных решений» исамостоятельная работа студента в системе учебного процесса»; «Задания и методические разработки для лабораторных и самостоятельных занятий»
Главная его задача – улучшить методическое обеспечение самостоятельной работы студентов при освоении теории оптимальных решений,...
Условия и идеи решений задач iconСовременные подходы к организации обучения дошкольников
Выбранная воспитателем форма обучения должна способствовать формированию интеллектуальных операций, создавать условия для творческого...
Условия и идеи решений задач iconЭвристические правила при решении задач с2
Стереометрические задачи вызывают особое затруднение у учащихся при сдаче егэ по математике. Особенно трудно учащимся выполнить правильное...
Условия и идеи решений задач iconПланиметрия и егэ
Систематизировать знания учащихся по ключевым разделам планиметрии. Создать содержательные и организационные условия для применения...
Условия и идеи решений задач iconПрограмма по биологии Химический лицей «Общая биология 11 класс.»
Предмет и методы экологии. Разделы экологии. Взаимосвязь экологии с другими науками. Роль экологии в решении практических задач....
Условия и идеи решений задач iconРабочая программа учебной дисциплины «математические методы анализа и принятия решений» по направлению подготовки
Мальцева Н. С. Рабочая программа учебной дисциплины «Математические методы анализа и принятия решений». – Новороссийск: нф мгэи,...
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com