Документ взят из кэша поисковой машины. Адрес оригинального документа : http://olympiad.cs.msu.su/wp-content/uploads/2012/04/solutions_2012_main.pdf Дата изменения: Sat Apr 14 11:25:36 2012 Дата индексирования: Sat Apr 9 22:12:19 2016 Кодировка: Windows-1251

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики Олимпиада по прикладной математике и информатике для школьников 31 марта 2012 г.

В задачах 1, 2 разрешается пользоваться любой моделью алгоритма (программа на языке программирования, блок-схема или словесное описание). Помните, что
правильный алгоритм без обоснования его корректности засчитывается не полностью!

Для экономии места решения задач 1, 2 (для всех классов) записаны на языке программирования Python, главная визуальная особенность которого в отсутствии явных операторных скобок. Группа операторов с одинаковым отступом является блоком, например, телом цикла, условного оператора или определения функции. В Python котором есть встроенные типы ?строка?, ?список? и ?словарь?. Список содержит индексированные данные любых типов (в том числе может содержать списки и словари); обращение к элементу списка производится по индексу, например S pisok[5]. Операция S pisok[N achalo : K onec] возвращает подсписок (не включая элемент с индексом K onec), при этом оба параметра можно опускать, чтобы подсписок выбирался с нулевого и/или до последнего элемента соответственно. Словарь структура данных, также хранящая данные любых типов, но при этом в роли индекса выступают константы любых типов; например, S lovar["AaB b"], S lovar[3] и т. п. Строка неизменяемый список символов, который для удобства записывается в виде


soderzhimoe_stroki

. Python имеет множество встроенных строковых методов, в частности, вызов вида S trok a.split() возвращает список слов, из которых состояла строка. Более подробные сведения о языке програмирования Python можно получить, например, из учебника: http://ru.wikibooks.org/wiki/Учебник_Python_2.6. Прилагаемые программы можно рассматривать в отрыве от конкретного языка программирования: это своего рода компактный псевдокод, определяющий реализацию алгоритма.

8 класс

1. Гравицаппа. Гравицаппу можно изготовить из нескольких деталей по прилагающейся инструкции. Если соответствующей детали нет, е?, в свою очередь, можно изготовить из других деталей по другому разделу той же инструкции. Известно. что для любой пары деталей k, i верно следующее: если для изготовления детали i используется деталь k, то для изготовления детали k не может использоваться деталь i. Написать программу, которая проверяет, можно ли из имеющегося набора деталей изготовить гравицаппу (при анализе должно учитываться количество требуемых деталей).


Первая строка набор имеющихся деталей (раздел?нные пробелом натуральные числа, необязательно различные, в диапазоне от 1 до 999 числом не более 10000). Вторая и последующие строки содержат правила из инструкции вида ?ЦелеваяДеталь Деталь1 Деталь2 ...?, задающие способ сборки ЦелевойДетали. Последняя строка определяет правило сборки самой гравицаппы в виде ?0 Деталь1 Деталь2 ...? (ноль вместо номера детали). Каждая составная деталь собирается единственным способом.
Ввод: Вывод:

Yes

или

No

Пример:

Ввод:

2 4 3 2 1 0

3 3 6 7 2 1

5 5 7 9

55677788899 5 88 7

234 Yes

Вывод:

Ввод:

4 4 2 0

4 6 4 2

446 66 4 466 No

Вывод:

Первый пришедший в голову алгоритм: взять список деталей для гравицаппы (последняя строка ввода) и выкидывать из него имеющиеся в наборе детали, а если некоторой детали в наборе нет, подставить в список вместо не? е? составляющие части. Если список опустеет гравицаппа собрана. Если же некоторой детали нет в наборе (никогда не было или кончились), и собрать е? нельзя, потому что она несборная, гравицаппу собрать нельзя. В таком алгоритме не учитывается, что некоторую деталь можно собрать из других несколькими принципиально различными способами. Если же способ сборки любой составной детали только один, а в наборе присутствуют как составные детали, так и их части, не имеет значения, в какой момент будет использована составная деталь из набора, а в какой она же, но собранная из частей. Главное, чтобы при наличии в наборе составной детали, использовалась именно она, а не части (которые, возможно понадобятся для деталей другого вида ).
Решение.

#!/usr/bin/python # coding: utf8 List=raw_input().split() Rules={} # Набор имеющихся деталей # Словарь вида R[ЦелеваяДеталь]=[Деталь1 Деталь2 ...]


while True: Rule=raw_input().split() Rules[Rule[0]]=Rule[1:] if Rule[0] == "0": break print Rules Work=Rules["0"] while Work: Detail=Work.pop() if Detail in List: List.remove(Detail) continue if Detail not in Rules: print "No" break Work.extend(Rules[Detail]) else: print "Yes"

# # # # # # # # # # # # # # # #

Строим словарь Список слов Первое слово - ЦелеваяДеталь Последняя строка: сборка гравицаппы Каких деталей не хватает для гравицаппы? Гравицаппа вс? ещ? не собрана Забираем нужную деталь из списка ...есть в наборе? используем е? перейд?м к другой детали ...нет в наборе и нельзя сделать из других? cобрать гравицаппу нельзя дальше можно не пробовать Добавим составляющие снятой детали в список (выход из whilе не с помощью break) Все детали или их составляющие оказались в наборе

Цепь состоит из N прямолинейных отрезков различной целой длины, соедин?нных попарно в замкнутую ломаную. Написать программу, определяющую, можно ли из этих отрезков составить квадрат (при этом цепь размыкать нельзя, сгибать и ломать отрезки нельзя, все отрезки цепи без исключения должны войти в квадрат без наложений).
2. Цепь. Ввод: Вывод:

Число N , на следующей строке N целых чисел длин отрезков цепи.
Yes

или No, в зависимости от того, можно или нельзя составить соответствующую фигуру.
Пример 1: Ввод:

6 132244
Вывод:

Yes
Ввод:

Пример 2:

5 13233
Вывод:

Единственный ?подводный камень? этой задачи соображение о том, что первое и последнее звено цепи не обязательно должны замыкаться на углу фигуры. В самом деле, цепь вида 2, 4, 4, 4, 2 образует квадрат, при этом первое и последнее звено встречаются в середине стороны.
Решение.

No


Рассмотрим решение задачи на примере прямоугольника (случай квадрата аналогичен). Первая сторона может начинаться почти где угодно (правда, е? длина должна быть строго меньше полупериметра). Вторая сторона должна в сумме с первой составлять полупериметр, третья быть равной первой (о четв?ртой стороне заботиться уже не надо). Все стороны могут состоять из одного или более звеньев цепи. Таким образом, внешний цикл перебор всех возможных начал первой стороны, внутренний перебор возможных длин первой стороны. Внутри циклов надо проверить, можно ли сложить вторую сторону длиной P oluperimetr - P ervayaS torona и третью длиной P ervayaS torona.
# !/usr/bin/python # coding: utf8 def locate(Lnk, Start, Length): # (определение функции) '''Проверить, можно ли в цепи Lnk найти последовательность звеньев, начиная со звена Start, суммарной длины Length. Вернуть начало следующей стороны, в случае неуспеха - 0.''' h,D=Lnk[Start],Start while h

3. Отрезки. На сторонах треугольника AB C вовне треугольника построены квадраты AB B1A2, B C C1B2, C AA1C2. Доказать, что сумма длин отрезков B A1 и B C2 равна суммe длин отрезков C A2 и AC1. Решение. Существует такой поворот плоскости относительно точки A на 90 , при котором точка A2 переходит в точку B , а точка C переходит в точку A1. Значит, длины отрезков C A2 и B A1 равны. Это можно было бы установить и из равенства треугольников AA2 C и AB A1 по двум сторонам AA2 = AB , AC = AA1 и углу между ними:

A2 AC = A2 AB + B AC = 90 + B AC = B AC + C AA1 = B AA1 .

Аналогично устанавливается, что
4. Суммы квадратов. a = x2 + x2 + x2 b = x2 1 2 3 4

AC1 = B C2

, откуда и вытекает требуемое.

Натуральные числа a и b таковы, что (a + b)/2 = 2012, причем и + x2 + x2 . Известно также, что все числа xi натуральны и 5 6 попарно различны. В ответе указать пример такой шестерки чисел x1, x2, x3, x4, x5, x6. 2 2 2 2 2 2 2 2 2 Решение. Поскольку 7 + 21 + 39 = 2011, 9 + 29 + 33 = 2011, 21 + 27 + 29 = 2011, 2 2 2 2 2 2 2 2 2 2 2 и 2 + 28 + 35 = 2013, 4 + 29 + 34 = 2013, 8 + 10 + 43 = 2013, 13 + 20 + 382 = 2013 (указаны все возможности с точностью до перестановки слагаемых для a = 2011, b = 2013), то в качестве примера шестерки можно взять (7, 21, 39, 2, 28, 35) или (7, 21, 39, 8, 10, 43). Для сокращения перебора полезно заметить, что квадрат числа при делении на 4 дает в остатке только 0 или 1. Так как 2011 3 (mod 4), то в этом случае надо искать квадраты нечетных чисел, Так как 2013 1 (mod 4), то в этом случае надо искать квадраты двух четных и одного нечетного чисел.
5. Игра ?Попробуй, обнули!"

Имеется выражение

|Ax3 + B x2 + C x + D| ћ E + F x4 + Gy .

Двое по очереди выбирают некоторую переменную (A, B , C , D, E , F , G, x или y) и присваивает ей некоторое вещественное значение. Первый выиграет, если в итоге (при подстановке выбранных значений переменных) получится значение 0, иначе выиграет второй. Кто выигрывает при правильной игре? Какова стратегия этого игрока? Ответ. Выигрывает первый игрок. Решение. Разобьем буквы на пары (A, B ), (C, F ), (D , E ), (G, y ). Первый игрок первым ходом присваивает x значение 0. Далее на выбор вторым игроком значения одной из переменных первый присваивает нулевое значение второму элементу той же пары. Значение выражения в итоге неизбежно станет равным |Aћ0+B ћ0+C ћ0+D|ћE +F ћ0+Gy = |D| ћ E + Gy = 0, то есть выиграет первый игрок.
6. Раскраски правильного тетраэдра. Сколько существует попарно неравных правильных единичных тетраэдров, у которых каждая грань и каждое ребро раскрашены в один из 4 цветов (красный, оранжевый, желтый, зеленый) так, что для любой пары граней цвета этих граней и цвет ребра, разделяющего эти грани, попарно различны?


Тетраэдры считаются равными, если их можно совместить с полным совпадением цветов и граней, и ребер. Ответ. 128. Решение. Легко видеть, что любые две грани тетраэдра смежны, а всего граней 4. Значит, для раскраски граней будут использованы все 4 цвета. Выберем в качестве основания тетраэдра плоскость красного цвета, тогда боковые грани будут окрашены в оранжевый, желтый и зеленый цвета либо по часовой, либо против часовой стрелки (всего имеется две различных раскраски граней). Осталось каждое ребро раскрасить в цвет, отличный от цветов содержащих ребро граней имеется 2 способа окраски каждого ребра, и их можно выбирать независимо для разных ребер. Так как общее число ребер тетраэдра равно 6, то в итоге получаем 2 ћ 26 = 128 различных раскрасок. На факультете учатся 2012 студентов. Каждый из них либо рыцарь (всегда говорит правду), либо лжец (всегда лжет). Декан факультета может за один шаг выбрать произвольного студента и спросить у него, является ли такой-то студент факультета лжецом. Сможет ли декан факультета выяснить, кто из 2012 студентов факультета рыцарь, а кто лжец, если а) больше ничего не известно, б) известно, что на факультете рыцарей больше, чем лжецов. Какое наименьшее число шагов гарантированно дает декану необходимую информацию? Ответ. a) Нет. б) Да, 2011 шагов. Решение. Нетрудно заметить, что студенты с номерами i и j дадут друг о друге одинаковые ответы декану: ?нет" , если они оба лжецы или оба рыцари, и ? да" , если один из них лжец, а другой рыцарь. Поэтому декану нет смысла задавать одной и той же паре студентов больше одного вопроса. Более того, при отсутствии у декана дополнительной информации всегда будет иметься (по крайней мере) два противоположных способа распределения меток ?рыцарь" , ?лжец" по всем студентам, и, следовательно, в пункте а) ответ отрицательный. В пункте б) ответ положительный: декан может спросить мнение одного студента обо всех остальных, и, сравнив количества ответов ? да" и ответов ?нет" , определить (зная, что ответов про рыцарей хотя бы на 1 больше), рыцарю или лжецу задавал он вопросы и, следовательно, правдивыми или лживыми были все ответы. Заметим, что при этом декану понадобится сделать 2011 шагов. Покажем, что это и есть минимальное количество шагов, гарантированно дающее декану необходимую информацию. Пусть декан задал студентам некоторое количество вопросов. Назовем компонентой связности каждое максимальное по включению студентов множество студентов, о которых у декана уже есть зависимая информация (так, например, если декан задал вопрос одному из студетов i, j о другом и задал вопрос одному из студетов i, k о другом, то студенты i, j , k оказываются в одной компоненте связности). В начальный момент (пока декан не задавал никому вопросов), имеется 2012 компонент связности, содержащих каждая по одному студенту. С каждым вопросом декан уменьшает количество компонент связности не более чем на 1. Значит за менее чем 2011 вопросов он уменьшит число компонент связности не более чем на 2010, и число компонент связности будет не меньше 2. Рассмотрим следующую ситуацию. Пусть на каждый вопрос, после которого имеется не менее трех компонент связности, декан слышит ответ ?нет" . Тогда, получив ответ на этот вопрос, декан не сможет в точности сказать, кто из студентов
7. Кто есть кто?


рыцарь, а кто лжец, так как в минимальной по числу студентов компоненте связности все студенты могут быть как рыцарями, так и лжецами. Рассмотрим теперь такой вопрос декана, после которого имеется в точности две компоненты связности. Ясно, что до этого вопроса имелось в точности три компоненты связности, и после этого вопроса студенты каких-то двух компонент связности K1 и K2 (из трех имеющихся компонент связности) оказались в одной компоненте связности K . Пусть в K не менее 1007 студентов. Тогда, услышав на свой последний вопрос ответ ?нет" , декан не сможет определить, являются ли все студенты из отличной от K компоненты рыцарями или они все являются лжецами (оба варианта возможны, так как в каждом число лжецов меньше числа рыцарей). Пусть теперь в K не более 1006 студентов. Тогда, услышав на свой последний вопрос ответ ? да" , декан не сможет определить, являются ли все студенты из множества K1 рыцарями, а все студенты из множества K2 лжецами, или же все студенты из множества K2 являются рыцарями, а все студенты из множества K1 лжецами (оба варианта возможны, так как в каждом число лжецов меньше числа рыцарей). Таким образом, задав не более 2010 вопросов, декан не сможет во всех случаях определить, кто из студентов лжец, а кто рыцарь, и 2011 вопросов и составляют искомое минимальное число шагов, гарантирующее декану успех.


Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики Олимпиада по прикладной математике и информатике для школьников 31 марта 2012 г. 9 класс

В задачах 1, 2 разрешается пользоваться любой моделью алгоритма (программа на языке программирования, блок-схема или словесное описание). Помните, что
правильный алгоритм без обоснования его корректности засчитывается не полностью!

Гравицаппу можно изготовить из нескольких деталей по прилагающейся инструкции. Если соответствующей детали нет, е?, в свою очередь, можно изготовить из других деталей по другому разделу той же инструкции. Известно. что для любой пары деталей k, i верно следующее: если для изготовления детали i используется деталь k, то для изготовления детали k не может использоваться деталь i. Написать программу, которая проверяет, можно ли из имеющегося набора деталей изготовить гравицаппу (при анализе должно учитываться количество требуемых деталей).
1. Гравицаппа.

Первая строка набор имеющихся деталей (раздел?нные пробелом натуральные числа, необязательно различные, в диапазоне от 1 до 999 числом не более 10000). Вторая и последующие строки содержат правила из инструкции вида ?ЦелеваяДеталь Деталь1 Деталь2 ...?, задающие способ сборки ЦелевойДетали. Последняя строка определяет правило сборки самой гравицаппы в виде ?0 Деталь1 Деталь2 ...? (ноль вместо номера детали). Каждая составная деталь собирается единственным способом.
Ввод: Вывод:

Yes

или

No

Пример:

Ввод:

2 4 3 2 1 0

3 3 6 7 2 1

5 5 7 9

55677788899 5 88 7

234 Yes

Вывод:

Ввод:

4 4 2 0

4 6 4 2

446 66 4 466


Вывод:

No

Решение:

см. решение задачи 1 для 8 класса.

Цепь состоит из N прямолинейных отрезков различной целой длины, соедин?нных попарно в замкнутую ломаную. Написать программу, определяющую, можно ли из этих отрезков составить прямоугольник (при этом цепь размыкать нельзя, сгибать и ломать отрезки нельзя, все отрезки цепи без исключения должны войти в прямоугольник без наложений).
2. Цепь. Ввод: Вывод:

Число N , на следующей строке N целых чисел длин отрезков цепи.
Yes

или No, в зависимости от того, можно или нельзя составить соответствующую фигуру.
Пример 1: Ввод:

6 132345
Вывод:

Yes
Ввод:

Пример 2:

5 13233
Вывод:

No

Решение:

см. решение задачи 2 для 8 класса.

На сторонах треугольника AB C вовне треугольника построены квадраты AB B1A2, B C C1B2, C AA1C2. Доказать, что сумма длин отрезков B A1 и B C2 равна суммe длин отрезков C A2 и AC1. Решение: см. решение задачи 3 для 8 класса.
3. Отрезки.

Натуральные числа a и b таковы, что (a + b)/2 = 2012, причем и + x2 + x2 . Известно также, что все числа xi натуральны и 5 6 попарно различны. В ответе указать пример такой шестерки чисел x1, x2, x3, x4, x5, x6. Решение: см. решение задачи 4 для 8 класса.
4. Суммы квадратов. a = x2 + x2 + x2 b = x2 1 2 3 4

Сколько существует попарно неравных правильных единичных кубов, у которых каждая грань и каждое ребро раскрашены в один из 4 цветов так, что для любой пары смежных граней цвета этих граней и цвет ребра, разделяющего эти грани, попарно различны? Кубы считаются равными, если их можно совместить с полным
5. Раскраски куба.


совпадением цветов и граней, и ребер. Для раскраски граней обязательно использовать все 4 цвета Ответ. 12480. Решение. По условию для раскраски граней использованы все 4 цвета. Т. к. каждого цвета не более 2 граней (для каждой грани только одна грань с ней не смежна), получаем, что имеется по 2 грани каких-то двух цветов (всегда можно положить куб на горизонтальную плоскость так, чтобы они были боковыми) и по одной грани оставшихся двух цветов (они тогда будут сверху и снизу). Понятно, что таких раскрасок будет ровно столько, сколько способов выбрать 2 цвета из 4-х, т.е. ровно 6 штук. Фиксируем раскраску граней. И положим куб так, как указано выше. Заметим, что раскраска граней переходит в себя при повороте на 180 относительно вертикальной оси симметрии куба. Раскрасим правильным образом 4 ребра передней грани и 2 горизонтальных ребра левой боковой грани. Таких раскрасок ровно 26, т. к. каждое ребро можно раскрасить в один из двух цветов, ?не занятых" инцидентными гранями. При указанном повороте эти 6 ребер переходят в оставшиеся 6 ребер куба. Назовем раскраску симметричной, если при таком повороте раскраска ребер куба переходит в себя. Очевидно, имеется 26 симметричных раскрасок ребер и 26 ћ (26 - 1)/2 несимметричных раскрасок ребер. Итак, всего имеется различных раскрасок граней и ребер куба, удовлетворяющих условию задачи, ровно 6 ћ (26 + 26 ћ (26 - 1)/2) = 6 ћ 25 ћ (2 + 26 - 1) = 6 ћ 32 ћ 65 = 12480. в целых числах уравнение
Ответ. 6. Уравнение в целых числах.

При каждом значении параметра a (a
x = 0,

R

) решить
a = 12,

x3 + 3a2 x + 3a2 - 5a = 0.

1 Если a = - 5 , то x = -1, если a = 0 или a = 5 , то 3 то x = 1, при других a целочисленных решений нет. Решение. Перегруппируем уравнение по степеням a:

если

a=

1 3

или

(3x + 3)a2 - 5a + x

3

(1)

Рассмотрим два случая. 1 1) x = -1, уравнение (1) линейное, a = - 5 . 2) x = -1, уравнение (1) квадратное. Его дискриминант должен быть неотрицателен:
D = 25 - 12x4 - 12x3 0, 25 . 12 Обозначим f (x) = x4 + x3, g(x) = f (-x) = x4 - x3. Легко видеть, что функция f (x) строго возрастает при неотрицательных что среди таких x условию (2) удовлетворяют лишь x = 0, x = 1. Функция g(x) строго возрастает при натуральных x: x4 + x3 g (x + 1) - g (x) = 4x3 + 3x2 + x > 0. (2)

целых x, так


Поэтому функция f (x) строго убывает при отрицательных целых x, так что среди таких x условию (2) удовлетворяет лишь x = -1, но это значение было исключено в рассматриваемом случае. Подставим x = 0 в уравнение (1): 3a2 - 5a = 0, a {0, 5 }. 3 1 Подставим x = 1 в уравнение (1): 6a2 - 5a + 1 = 0, a { 3 , 1 }. 2 Выписывая найденные целочисленные решения в зависимости от параметра a, получаем ответ. На факультете учатся 2012 студентов. Каждый из них либо рыцарь (всегда говорит правду), либо лжец (всегда лжет). Декан факультета может за один шаг выбрать произвольного студента и спросить у него, является ли такой-то студент факультета лжецом. Сможет ли декан факультета выяснить, кто из 2012 студентов факультета рыцарь, а кто - лжец, если а) больше ничего не известно, б) известно, что на факультете рыцарей больше, чем лжецов. Какое наименьшее число шагов гарантированно дает декану необходимую информацию? Решение: см. решение задачи 7 для 8 класса.
7. Кто есть кто?


Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики Олимпиада по прикладной математике и информатике для школьников 31 марта 2012 г. 10 класс

В задачах 1, 2 разрешается пользоваться любой моделью алгоритма (программа на языке программирования, блок-схема или словесное описание). Помните, что
правильный алгоритм без обоснования его корректности засчитывается не полностью!

Гравицаппу можно изготовить из нескольких деталей по прилагающейся инструкции. Если соответствующей детали нет, е?, в свою очередь, можно изготовить из других деталей по другому разделу той же инструкции. Известно. что для любой пары деталей k, i верно следующее: если для изготовления детали i используется деталь k, то для изготовления детали k не может использоваться деталь i. Написать программу, которая проверяет, можно ли из имеющегося набора деталей изготовить гравицаппу (при анализе должно учитываться количество требуемых деталей).
1. Гравицаппа.

Первая строка набор имеющихся деталей (раздел?нные пробелом натуральные числа, необязательно различные, в диапазоне от 1 до 999 числом не более 10000). Вторая и последующие строки содержат правила из инструкции вида ?ЦелеваяДеталь Деталь1 Деталь2 ...?, задающие способ сборки ЦелевойДетали. Последняя строка определяет правило сборки самой гравицаппы в виде ?0 Деталь1 Деталь2 ...? (ноль вместо номера детали). Каждая составная деталь собирается единственным способом.
Ввод: Вывод:

Yes

или

No

Пример:

Ввод:

2 4 3 2 1 0

3 3 6 7 2 1

5 5 7 9

55677788899 5 88 7

234 Yes

Вывод:

Ввод:

4 4 2 0

4 6 4 2

446 66 4 466


Вывод:

см. решение задачи 1 для 8 класса. 2. Цепь. Цепь состоит из N прямолинейных отрезков различной целой длины, соедин?нных попарно в замкнутую ломаную. Написать программу, определяющую, можно ли из этих отрезков составить прямоугольник (при этом цепь размыкать нельзя, сгибать и ломать отрезки нельзя, все отрезки цепи без исключения должны войти в прямоугольник без наложений).
Решение: Ввод: Вывод:

No

Число N , на следующей строке N целых чисел длин отрезков цепи.
Yes

или No, в зависимости от того, можно или нельзя составить соответствующую фигуру.
Пример 1: Ввод:

6 132345
Вывод:

Yes
Ввод:

Пример 2:

5 13233

см. решение задачи 2 для 8 класса. 3. Отрезки. На сторонах выпуклого четырехугольника AC E G вовне четырехугольника построены правильные треугольники AB C , C DE , E F G, GH A. Доказать, что суммарные длины ломаных H C F AD и DGB E H равны. Решение. Существует такой поворот плоскости относительно точки A на 60 , при котором точка B переходит в точку C , а точка G переходит в точку H . Значит, длины отрезков B G и C H равны. Это можно было бы установить и из равенства треугольников AB G и AC H по двум сторонам AB = AC , AG = AH и углу между ними:
Решение:

Вывод:

No

B AG = B AC + C AG = 60 + C AG = C AG + GAH = C AH.

Аналогично устанавливается, что требуемое.

B E = AD, DG = C F , H E = AF

, откуда и вытекает

4. Игра ?Попробуй, обнули!"

Имеется выражение

A sin ax + B cos bx + C x + D.

Двое по очереди выбирают некоторую переменную (A, a, B , b, C , D или x) и присваивает ей некоторое вещественное значение. Первый выиграет, если в итоге (при подстановке


выбранных значений переменных) получится значение 0, иначе выиграет второй. Кто выигрывает при правильной игре? Какова стратегия этого игрока? Ответ. Выигрывает первый игрок. Решение. Разобьем буквы на пары (A, a), (b, C ), (B , D ). Первый игрок первым ходом присваивает x значение 0. Далее на выбор вторым игроком значения одной из переменных первый присваивает противоположное значение второму элементу той же пары. Поскольку cos 0 = 1, значение выражения в итоге неизбежно станет равным A ћ 0 + B ћ 1 + C ћ 0 + D = B + D = 0, то есть выиграет первый игрок. 5. Странное число. Доказать, что расстояние между точками с только лишь целочисленными координатами на плоскости не может быть равно 20122012...2012 (под радикалом ровно 2012 цифр). Решение. Предположим противное: найдутся точки декартовой плоскости A(x, y ) и B (x , y ) с только лишь целочисленными координатами такие, что |AB | = 20122012...2012 (под радикалом ровно 2012 цифр). Тогда (x - x )2 + (y - y )2 = 20122012...2012 (обозначим число в правой части через m), то есть p2 + q2 = m (p, q целые). Легко видеть, что каждое целое число n можно представить в виде n = 16k + r, где r {0, 1, 2, 3, 4, 5, 6, 7, 8}, k Z. Тогда ясно, что определяемый по n однозначно остаток по делению на 16 числа n2 равен остатку по делению на 16 числа r2 , то есть лежит во множестве чисел M16 = {0, 1, 4, 9}. Следовательно, сумма двух квадратов целых чисел может давать при делении на 16 только такие остатки, какие встречаются среди остатков по делению на 16 сумм двух не обязательно различных чисел из множества M16. Но среди таких остатков нет числа 12, а именно таков остаток по делению на 16 числа m (это легко следует из того, что число 10000 = 54 ћ 24 кратно числу 16 = 24, а число 2012 имеет остаток 12 по делению на 16). Получили противоречие. Утверждение доказано. 6. Кто есть кто? На факультете учатся 2012 студентов. Каждый из них либо рыцарь (всегда говорит правду), либо лжец (всегда лжет). Декан факультета может за один шаг выбрать произвольного студента и спросить у него, является ли такой-то студент факультета лжецом. Сможет ли декан факультета выяснить, кто из 2012 студентов факультета рыцарь, а кто лжец, если а) больше ничего не известно, б) известно, что на факультете рыцарей больше, чем лжецов. Какое наименьшее число шагов гарантированно дает декану необходимую информацию? Решение: см. решение задачи 7 для 8 класса. 7. Четверки. Все упорядоченные четверки попарно различных элементов множества {0, 1, 2, 3} разбили на 12 пар так, что в каждой паре оказались четверки вида (a, b, c, d) и (d, c, b, a). Предлагается выбрать из каждой пары ровно одну четверку и занумеровать выбранные 12 четверок числами 0, 1, . . . , 11 в таком порядке, чтобы для всех целых n и для всех k = 4m + r (m целое, r = 0, 1, 2, 3) нашлась перестановка s(r, n) номеров мест элементов четверки (зависящая от r и n и не зависящая от m) такая, что четверка с номером k + n mod 12 получалась бы из четверки с номером k mod 12 с помощью перестановки s(r, n). (Через k mod 12 обозначается остаток от деления числа k
2012 цифр


на 12, то есть такое целое число t от 0 до 11, что для некоторого целого j верно равенство k = 12j + t). 0: 1: 2: 3: 4: 5: 6: 7: (0, (1, (2, (1, (1, (3, (2, (3,
Один из возможных вариантов ответа:

1, 2, 1, 3, 3, 2, 3, 0,

2, 3, 3, 0, 2, 0, 0, 1,

3 0 0 2 0 1 1 2

), ), ), ), ), ), ), ),

8: (3, 0, 2, 1 9: (0, 2, 1, 3 10: (2, 0, 1, 11: (0, 1, 3,

), ), 3), 2).

Здесь вторая четверка получается из первой циклическим сдвигом влево, третья из второй транспозицией (переменой мест друг с другом) первых двух элементов, четвертая четверка из третьей опять циклическим сдвигом влево, пятая четверка из четвертой транспозицией последних двух элементов, и далее процесс повторяется, причем бесконечно долго, если считать, что после 12-й четверки опять следует первая.