МАТЕМАТИКА

Укладачі завдань:

Міністерство освіти і науки, молоді та спорту України,

Інститут інноваційних технологій і змісту освіти.

На виконання завдання відводиться 4 години. Кожна задача оцінюється в 7 балів. Використання калькуляторів та інших електронних засобів забороняється.

7 клас

Рівень «Б»

1. Знайдіть усі такі чотирицифрові числа abcd , для яких виконується рівність   abcd + abc +ab + a = 2013 .

2. Серед 25 монет є рівно 2 фальшиві. Є чарівна скринька, в яку можна покласти 2 монети, і вона покаже кількість фальшивих монет у цій парі. Покажіть, як можна визначити обидві фальшиві монети не більше, ніж за 14 таких операцій.

3. Андрійко, Миколка, Оленка, Сергійко й Даринка посіли п’ять перших місць на математичній олімпіаді (жодне з місць не було розділено між декількома учасниками). Кожен з них знає, яке місце він зайняв. Оленка знає, що різниця місць Сергійка й Андрійка (у вказаному порядку) дорівнює двом. Також вона знає, що Даринка зайняла не перше місце, і тому Оленка може відновити розподіл місць між цією п’ятіркою учасників олімпіади. Яке місце зайняла Даринка?

4. Петрик послідовно виписує в рядок на дошці остачі від ділення деякого натурального числа на 10, 11, 12, …, 20. Виявилося, що кожне наступне записане число більше за попереднє. Доведіть, що в рядку записано
11 послідовних цілих чисел (тобто кожне наступне число більше за попереднє на 1).

5. Прямокутне приміщення розділене на 16 прямокутних кімнат. Комендант виміряв периметри восьми кімнат. Сім з восьми результатів його вимірювань схематично (тобто без урахування справжніх розмірів кімнат) показано на малюнку праворуч, а результат восьмого позначено через x .

Знайдіть значення x .

8 клас

Рівень «Б»

На виконання завдання відводиться 4 години. Кожна задача оцінюється в 7 балів. Використання калькуляторів та інших електронних засобів забороняється.

1. Чебурашка та Крокодил Гена з’їли торт. Чебурашка їв удвічі повільніше за Крокодила Гену, але почав їсти на хвилину раніше. З’ясувалося, що вони з’їли порівну. За який час Чебурашка сам з’їв би цей торт?

2. Керівник математичного гуртка дав учням завдання виписати в порядку зростання всі чотирицифрові числа abcd , в яких

1 ≤ a < b < c < d ≤ 9 .

Яке число буде записаним на 53-му місці?

3. На дошці написані числа 1, 2, 3, ... , 4027, 4028. Миколка та Андрійко по черзі закреслюють числа, причому Миколка ходить першим. За один хід можна закреслити тільки одне з раніше незакреслених чисел. Андрійко хоче, щоб після його 2013-го ходу на дошці залишилися два послідовні числа (тобто числа, різниця яких дорівнює 1). Чи завжди він зможе цього досягти?

4. Дано гострокутний трикутник ABC . Кола k₁ і k₂ проходять через вершину A і дотикаються до прямої BC в точках B і C відповідно. Висота BK трикутника ABC перетинає коло k₁ у точці P, відмінній від B, а висота CL перетинає коло k₂ в точці Q ,відмінній від C . Доведіть, що точки A, P і Q лежать на одній прямій.

5. Знайдіть усі пари простих чисел p і q , для яких число p³ + q² є кубом деякого натурального числа. На виконання завдання відводиться 4 години.

9 клас

Рівень «Б»

На виконання завдання відводиться 4 години. Кожна задача оцінюється в 7 балів. Використання калькуляторів та інших електронних засобів забороняється.

1. Сума двох натуральних чисел дорівнює 20132013, і якщо в одному з них закреслити останню цифру, то отримаємо друге число. Знайдіть усі такі пари чисел.

2. Відомо, що     a ≠ b  та рівняння

ax²⁰¹³ + x²⁰¹² + b = 0 і bx²⁰¹³ + x²⁰¹² + a = 0

мають спільний дійсний корінь. Знайдіть a + b .

3. У трапеції ABCD з основами AD і BC , AD > BC , діагоналі AC і BD перетинаються в точці E . Дотична до описаного кола трикутника BCE , проведена в точці E , перетинає пряму AD в точці F , причому точка D лежить між точками A і F . Відомо, що AF = a , AD = b. Знайдіть довжину відрізка EF .

4. Доведіть, що для довільних додатних дійсних чисел x , y і z має місце нерівність

5. Керівник математичного гуртка намалював на дошці таблицю розміру 30  30 і запропонував учням заповнити її числами 1, 2, … , 900, записуючи щосекунди в якусь порожню клітинку на свій розсуд одне з тих чисел, що не використовувались раніше. Чи зможуть учні виконати завдання так, щоб у будь-який момент ані в жодному рядку, ані в жодному стовпці сума всіх записаних чисел не давала остачу 1 від ділення на 3?

10 клас

Рівень «Б»

На виконання завдання відводиться 4 години. Кожна задача оцінюється в 7 балів. Використання калькуляторів та інших електронних засобів забороняється.

1. Чи можна зобразити на прямій шість відрізків так, щоб серед будь-яких трьох зображених відрізків знайшлися принаймні два, які мають хоча б одну спільну точку, і кожна точка прямої належала щонайбільше трьом зображеним відрізкам? (Вважається, що кінці відрізків належать самим відрізкам.)

2. Знайдіть усі такі пари натуральних чисел m і n , для яких виконується рівність

mn  = 7 .

3. Відомо, що додатні дійсні числа x і y задовольняють нерівність

2x + 7 y  14 . Доведіть, що  +  3.

4. Нехай H — точка перетину висот AQ , BL і CP гострокутного трикутника ABC , K — спільна точка відрізків PQ і BH , M — середина сторони AC , N — середина відрізка BH . Промінь BL перетинає описане коло трикутника ABC в точці D , відмінній від B. Відомо, що KQ = HQ . Доведіть, що прямі MN і AD перпендикулярні.

5. По колу записали 672 натуральних числа a₁, a₂ , … , a₆₇₂ таких, що a₁ +a₂ + ... + a₆₇₂ = 2013 і a_k ≠ 1342 для всіх k , 1 ≤ k ≤ 672 . Доведіть, що завжди можна вибрати декілька записаних поспіль чисел, сума яких дорівнює 1342 .

11 клас

Рівень «Б»

На виконання завдання відводиться 4 години. Кожна задача оцінюється в 7 балів. Використання калькуляторів та інших електронних засобів забороняється.

1.Зобразіть на координатній площині xOy множину всіх точок, координати яких задовольняють рівність

sin x + cos y = sin y + cos х.

2. Розв’яжіть рівняння

х²⁰¹³х²⁰¹⁴=

(тут — ціла частина числа a , тобто найбільше ціле число, яке не перевищує a;  = a   — дробова частина числа a ).

3. У трикутнику ABC AB = 16 см, BC = 25 см, AC = 39 см. Пряма, яка проходить через центр вписаного кола трикутника ABC і середину M сторони BC , перетинає висоту AD цього трикутника в точці P . Знайдіть довжину відрізка AP .

4. Знайдіть усі такі визначені на множині всіх дійсних чисел числові функції f , що для будь-яких x  R і y  R має місце рівність

f (xf ( y))+ f ( y + f (x)) f (x + yf (x))= x .

5. Нехай x₁ — довільне дійсне число, і для всіх натуральних n виконується рівність

=x_n+2.

Доведіть, що серед чисел x₁ , x₂ , … , x₂₀₁₃ принаймні 1005 чисел є ірраціональними.

Розв’язання задач розміщені на сторінці «Юному математику» сайта механіко-математичного факультету Київського національного університету імені Тараса Шевченка http://www.mechmat.univ.kiev.ua/u/school.

ІНФОРМАТИКА

Укладачі завдань:

Міністерство освіти і науки, молоді та спорту України,

Інститут інноваційних технологій і змісту освіти.

8-11 клас

І тур

А – Неуважність

Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із самих престижних ІТ компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, все виконує у останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав не звернувши уваги, що випадково натиснув клавішу caps lock. Таким чином великі букви були набрані маленькими, а маленькі великими. Інші символи він набрав вірно. Степан настільки стомився, що немає сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить, напишіть програму, яка виправляє неуважно набраний текст.

Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.

Формат вихідних даних: вихідний файл має містити виправлений текст.

Приклади

sCHOOL

School

B – День святого Валентина

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали. Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є N однокольорових (що поробиш – бідні студенти) кульок, діаметр i-ї кульки (1 ≤ i ≤ N) дорівнює Di міліметрів. Згідно новим вимогам профкому, залу необхідно прикрасити не менше ніж K кульками. Оскільки профоргу університету не подобається свято закоханих, то вона ввела своє поняття – так званий показник некрасивості – рівний максимально можливому числу Di – Dj при 1 ≤ i, j ≤ M, де M – кількість кульок для зали, а Di – їх діаметр. Допоможіть Степану із N іграшок вибрати М (M ≥ K) так, щоб для вибраних M кульок показник некрасивості був мінімальним.

Формат вхідних даних: перший рядок вхідного файлу містить два натуральних числа N (2 ≤ N ≤ 100 000) і K (2 ≤ K ≤ N) відповідно. Другий рядок містить N цілих чисел Di (1 ≤ Di ≤ 10⁹) – діаметр i-ї кульки.

Формат вихідних даних: вихідний файл має містити значення показника некрасивості, вибраних M кульок.

Пояснення: Приклад 1 - Існує кілька різних варіантів вибору. Степан може вибрати, наприклад, 6 кульок: 3, 5, 6, 4, 7 і 8
Приклад 2- Степан вибере 4 кульки: 1, 5, 3 і 6.

Приклади

8 5

10 20 10 20 10 10 20 20

10

6 4

21 12 17 28 16 21

5

C –  Степан і Пари

Останнім часом Степан дуже цікавиться парами чисел, а крім пар чисел його цікавить найбільший спільний дільник пари чисел, позначимо його як НСД(x, y). Зараз у Степана є ціле число n і його цікавить така інформація: скільки існує пар цілих чисел (i,j), таких що 1 ≤ i, j ≤ n і виконується рівність i = НСД(i, j). Допоможіть йому у вирішенні нелегкої задачі.

Формат вхідних даних: у першому рядку дано ціле число n

(1 ≤ n ≤ 10⁶).

Формат вихідних даних: єдиний рядок має містити відповідь на задачу.

Зауваження: У першому прикладі підходящою парою є пара (1, 1), так як НСД(1, 1) = 1.У другому прикладі підходять 8 пар чисел:

(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Приклади

1

1

4

8

10

27

D –  Спадок Степана

Степан отримав у спадок від дідуся стоянку з N місць, пронумерованих від 1 до N. Стоянка розбита на дві частини. Перші M місць знаходяться з лівого боку, а інші N - M місць з правого. Кожного дня N жителів цього району паркують свої автомобілі на стоянці Степана. Відомо, що перший житель приходить раніше усіх, потім другий, і так далі, тобто k-й приходить k-м. Також для кожного жителя i відомо, скільки він буде платити, якщо його машину поставлять на j-е місце. Степан придбав розподільник місць, який кожному автомобілю, що приїздить вказує, на який бік паркуватись, після чого автомобіль паркується на мінімальне за номером вільне місце відповідного боку. При цьому Степан вирішив зекономити і не придбав програмне забезпечення для розподільника, тому він працює не оптимально. Степан просить Вас написати програму для цього розподільника, яка максимізує доходи Степана.

Формат вхідних даних: у першому рядку записані два цілих числа N (2 ≤ N ≤ 1000) і M (1 ≤ M < N) – загальна кількість місць на стоянці і кількість місць з лівого боку відповідно. У кожному із наступних N рядків записано по N цілих додатних чисел. j-е число i-го рядка означає, скільки буде платити i-ий житель за місце з номером j на цій стоянці. Кожне з цих чисел не перевищує 10⁶.

Формат вихідних даних: єдиний рядок має містити одне число – максимальний прибуток стоянки.

Зауваження: Не менш чим у 50% тестів N ≤ 30.

Приклади

2 1

3 2

6 4

8

4 1

4 3 1 1

3 1 1 1

1 1 4 1

1 1 1 2

12

E – Конфетна проблема Степана

Степан закохався і вирішив привернути увагу дівчини великою коробкою цукерок. За порадою друзів він поїхав на саму відому кондитерську фабрику ShenRo і дізнався, що великі коробки цукерок мають трикутну форму. Цукерки в цих коробках розташовуються у кілька рядів. У першому ряду знаходиться одна цукерка, у другому – дві, у третьому – три цукерки і так далі. На фабриці випускаються коробки цукерок з любим числом рядів у межах від 1 до N. Степан хоче купити одну із таких коробок. Але є одна проблема: його дівчина засмутиться, якщо кількість цукерок у коробці не буде ділитись націло на M, тому що у цьому випадку комусь із друзів дівчини дістанеться більше цукерок, чим іншим, або ж якісь цукерки залишаться лишніми. Тому Степан вирішив, що число цукерок у коробці має обов’язково ділитись націло на M.

При виборі подарунка Степан зіткнувся з проблемою придбання відповідної коробки цукерок, оскільки можливих варіантів вибору коробки цукерок виявилося надто багато. Не довго думаючи, Степан вирішив звернутись за допомогою до учасників олімпіади.

Вам необхідно по заданих числах N і M знайти число способів вибору коробки цукерок із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів цукерок.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N - максимальна кількість рядів цукерок у коробці і M – кількість друзів дівчини Степана (1 ≤ N, M ≤ 2*10⁹) відповідно.

Формат вихідних даних: вихідний файл має містити одне ціле число – кількість різних способів вибору коробки цукерок.

Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 10⁵ – не менше 55 балів.

Приклади

20 10

4

53 199

0

5705 145

157

ІІ тур

А – Арифметика

Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 10¹⁰⁰⁰), записане Мишком.

Формат вихідних даних: вихідний файл має містити одне число – кількість різних цифр у числі.

Приклади

1233

3

B - Степан і сірники

Степан дуже полюбляє гратись із сірниками. Але він не балується ними, не розпалює вогонь, а розв'язує різні головоломки. Наприклад, він уміє прирівнювати число дев'ять до числа одинадцять, переклавши лише один сірник. Нещодавно батьки Степана подарували йому декілька наборів, кожен з яких складається з дванадцяти сірників. Хлопчик почав збирати з них різні геометричні фігури. Він вже зібрав багато різних фігур, але тепер йому стало цікаво: з яких наборів можливо склеїти каркас паралелепіпеда за допомогою дванадцяти сірників з набору та клею? Ламати сірники не можна і жоден із сірників не повинен виступати за каркас.

Ваше завдання полягає в тому, щоб за відомими довжинами сірників для кожного набору перевірити, чи можна з них склеїти каркас паралелепіпеда.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 100), яке представляє кількість наборів. Далі йдуть N рядків, кожен з яких містить у собі опис набору сірників - дванадцять цілих додатніх чисел не перевищують 10⁹.

Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору сірників виведіть “yes”, якщо з нього можливо склеїти каркас паралелепіпеда, і “no” в іншому випадку.

Приклади

2

1 1 1 1 2 2 2 2 3 3 3 3

1 1 1 1 2 2 2 2 3 3 3 4

yes

no

C - Задача від Степана

Перебираючи свої дитячі іграшки, Степан знайшов набір із N різних прямокутників і згадав задачу, яку йому колись задав старенький вчитель математики. Назвемо прямокутник маленьким, якщо знайдеться інший прямокутник з даного набору, яким можна повністю накрити цей прямокутник. При цьому прямокутники можна повертати, але відповідні сторони мають бути паралельними.

Наприклад, прямокутник зі сторонами 1 і 10 можна повністю накрити прямокутником 10 і 3, але не можна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити не можна, відповідно в наборі із цих трьох прямокутників тільки один маленький. Напишіть програму, яка вирішить згадану Степаном задачу – визначить кількість маленьких прямокутників у даному наборі.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000). У кожному з наступних N рядків міститься два цілих додатних числа – розміри одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників немає однакових.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість маленьких прямокутників у даному наборі.

Приклади

3

1 10

9 9

10 3

1

4

1 7

2 6

3 5

4 4

0

D – Штрафи

Степан нещодавно купив автомобіль, але водійські права ще не отримав. В зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить в ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що ДАІ стоять не на всіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (в країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 карбованців. Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.

Формат вхідних даних: Перший рядок містить два числа N, M (2 ≤ N ≤ 10⁵ , 1 ≤ M ≤ 10⁵). Інші М рядків містять два числа Xi і Yi, які описують дорогу між містом Xi і містом Yi. В останньому рядку написано число A (2 ≤ A ≤ N) – місто в якому живе Степан.

Формат вихідних даних: Виведіть в одному рядку єдине число – кількість карбованців які Степан має мати при собі.

Приклади

6 7

1 2 

2 3

3 1

3 4

4 5

4 6

5 6

6

1000

E – Ремонт

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд все просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати малюнки на сусідніх полосах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином. Кожну полосу шпалер можна описати її частиною – прямокутником довжиною N і шириною M (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось N рядків і М стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами ”.” і ”*” (крапка і зірочка), по одному символу в кожній клітинці.

Вам дано опис двох полос шпалер. Допоможіть Степану, напишіть програму, яка визначатиме, на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі. Степан придбав такі шпалери, що гарантовано завжди можна це зробити.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N і M(1 ≤ N ≤ 20, 1 ≤ M ≤ 100000). Наступні N рядків містять по М символів кожна – опис першої полоси шпалер. Наступні N рядків містять по М символів кожна – опис другої полоси шпалер. Кожен рядок опису шпалер містить тільки символи ”.” і ”*”.

Формат вихідних даних: вихідний файл має містити одне число – на яку мінімальну кількість клітинок потрібно змістити другу полосу вправо, щоб її малюнок співпав з малюнком на першій полосі.

Приклади

2 5

.*.*.

*.*.*

*.*..

.*.**

1

1 5

***..

*..**

2