Второй открытый Зеленоградский турнир 2006

Сборник задач (часть 1)

Задача 1 Легко доказать, что не существует равностороннего треугольника с целой длиной стороны и одновременно с целой площадью. Однако у "почти равностороннего треугольника" 5-5-6 площадь равна 12. Почти равносторонний треугольник - это треугольник у которого две стороны равны, а третья отличается от первых двух не более чем на единицу. Найдите & #1089;умму периметров всех почти равносторонних треугольников с целыми сторонами и площадью, чей периметр не превышает миллиард (1.000.000.000).

Задача 2 Если в ящике лежит 21 мячик, 15 из которых синие и 6 красные, и мы берем наугад два мячика, то можно заметить, что вероятность вытащить 2 синих мячика P(CC) = (15/21)*(14/20) = 1/2. Следующее такое распределение мячиков, для которого вероятность вытащить два синих мячика равна ровно 50% - это коробка, наполненная 85 синими мячиками и 35 красными. Найдя первое распределение, l 2;оторое содержит в общей сложности более 10^12 = 1.000.000.000.000 мячиков, определите число синих мячиков в этом распределении.

Задача 3 Рассмотрим дробь n/d, где n и d натуральные числа. Если n < d и НОД(n, d)=1, то дробь называется правильной. Если написать подряд все правильные дроби в неубывающем порядке для d <= 8, то получим следующий ряд: 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 Легко заметить, что между 1/3 и 1/2 находится ровно 3 правильные дроби. Сколько правильных дробей лежит между 1/3 и 1/2 в упорядоченном наборе правильных дробей для d <= 10000?

Задача 4 Выражение 1^1 + 2^2 + 3^3+ ... + 10^10 = 10405071317. Найдите последние 10 цифр выражения 1^1 + 2^2 + 3^3+ ... + 1000^1000

Задача 5 Цифры куба натурального числа, 41063625 (345^3), можно переставить таким образом, что мы получим в результате ещё два куба натуральных числа: 56623104 (384^3) и 66430125 (405^3). В действительности число 41063625 - это минимальное натуральное число для которого перестановка цифр дает ровно 3 других куба. Найдите минимальное натуральное число (являющееся кубом натурального числа) д ;ля которого перестановка цифр дает ровно 5 различных кубов натуральных чисел.

Задача 6 Функция Эйлера phi(n) используется для определения количества чисел меньше n, которые взаимно просты с n. Например, числа 1, 2, 4, 5, 7 и 8 все меньше девяти и взаимно просты с девятью, phi(9) = 6. Интересно, что phi(87109) = 79180, и можно увидеть, что число 79180 может быть получено путем перестановки цифр числа 87109. Найдите значение n, меньше 10 миллионов, для которого phi(n) получается из n путе&# 1084; перестановки цифр и отношение n/phi(n) - минимально.

Задача 7 Простое число 41, можно записать в виде суммы 6 последовательно идущих простых чисел. 41 = 2 + 3 + 5 + 7 + 11 + 13 и это является самой длиной суммой последовательно идущих простых чисел дающих простое число меньше 100. Самая длинная сумма последовательно идущих простых чисел меньше 1000 и дающих в результате простое число содержит 21 слагаемое и равна 953. Какое про& #1089;тое число меньше одного миллиона, может быть записано в виде суммы последовательно идущих простых чисел максимальной длины? (Число 1 в данной задаче не является простым.)

Задача 8 145 - необычное число, так как 1! + 4! + 5! = 1 + 24 + 120 = 145. Найдите сумму всех чисел, которые равны сумме факториалов их цифр. (Замечание: числа 1 = 1! и 2 = 2! не включаются в эту сумму)

Задача 9 Перестановка - это упорядоченный набор некоторых объектов. Например, 3124 - это одна из возможных перестановок цифр 1, 2, 3 и 4. Если все перестановки упорядочить по возрастанию, то такое упорядочивание называется лексиграфическим порядком. Перестановка для цифр 0, 1 и 2 в лексиграфическом порядке выглядит так: 012, 021, 102, 120, 201, 210 Найдите миллионную перестановку в лексиграфическом порядке чисел 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Задача 10 Если посчитать аккуратно, то можно заметить, что в прямоугольной сетке 2х3 содержится 18 различных прямоугольников. Не существует прямоугольной сетки, которая содержит ровно 2 миллиона различных прямоугольников. Найдите площадь прямоугольной сетки в которой содержится число прямоугольников наиболее близкое к двум миллионам.

Входные данные

В данной задаче нет входных данных

Выходные данные

Выведите ответ в виде набора строчек, на отдельной строчке сначала номер задачи, затем её ответ. Если ответ будет неверным, то вы получите в результате Wrong Answer.

Начисление очков

За каждую решенную задачу вы получите ровно 1 очко (то есть максимум 10, если будут решены все 10 задач).

Пример

Выходные данные:
1 6174046
2 6568127473
5 806257
8 51146700

Это просто пример как должны выглядеть выходные данные. Если все 4 ответа (на 1, 2, 5 и 8 задачи) правильные, то вы получите 4 очка.