Математичні олімпіади і олімпіадні задачі

Завдання 1: На котячої виставці в ряд сидить 10 котів і 19 кішок, причому поруч з будь-кішкою сидить товщий кіт. Доведіть, що ви перебуваєте поблизу котом сидить кішка, яка тонше його.

Нехай кожна кішка вкусить більш товстого кота, який сидів поруч з нею, Будь 9 котів могли отримати не більше 18 укусів, значить кожен кіт виявився укушеним, тобто поряд з ним сидить кішка, яка тонше його.

Доведіть, що якщо цифри десятизначного числа виписати в зворотному порядку, то отримане число не буде в три рази більше початкового.

Припустимо, що таке число знайшлося. Його перша цифра може бути 1, 2 або 3 (бо інакше в три рази більше число буде одинадцятизначне).

Якщо перша цифра 1, то остання - 7 (бо інакше при множенні на три на кінці вийде інше число - див. Таблицю множення на 3). Але тоді звернене число виходить більш ніж в три рази перевершує вихідне.

Якщо перша цифра - 2 або 3, то остання - 4 або 1, тому звернене число виходить занадто мало.

Є 10 монет, серед них рівно дві фальшиві. Детектор R7 за одну операцію досліджує три монети і вказує на одну з них. Відомо, що детектор не може вказати на справжню монету, якщо серед тестованих монет є хоча б одна фальшива. Як за шість тестів виявити обидві фальшиві монети?

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

На дошці написано п'ять двозначних натуральних чисел. Чебурашка кожну хвилину додає до всіх чисел одиницю або (теж до всіх чисел) двійку. Після того, як Чебурашка збільшує числа, К. Гена може стерти будь-яке число, що ділиться на 13, або число, сума цифр якого ділиться на 7 (якщо, звичайно, таке число на дошці є). Доведіть, що при будь-яких діях Чебурашки Гена через деякий час зможе стерти з дошки все числа.

Рішення: Гена може знайти п'ять пар не більше ніж п'ятизначних сусідніх чисел, так, щоб в кожній парі він міг стерти будь-яке число. Чебурашка зможе «провести» через одну таку пару не більше одного числа, а значить все п'ять чисел Гена зможе стерти.

Подібних пар дуже багато, наприклад годяться пари 142 і 143, 312 і 313, 3120 і 3121, 1312 і 1313, 69999 і 70000 ...

На одній стороні вулиці розбитих ліхтарів стояло 150 ліхтарів, причому серед будь-яких трьох ліхтарів, що стоять підряд, хоча б один був розбитий. Після того, як електрик Петров полагодив кілька ліхтарів, серед будь-яких чотирьох ліхтарів, що стоять підряд, залишилося не більше одного розбитого. Доведіть, що електрик полагодив не менше 25 ліхтарів.

Рішення: 1 спосіб. Розіб'ємо ліхтарі на 25 шісток поспіль стоять, і доведемо, що в кожній з них був полагоджений ліхтар. Припустимо, що в якийсь шістці жоден ліхтар ні полагоджений. У такій шістці не менше двох розбитих ліхтарів (оскільки в кожній з двох трійок, що становлять шістку, був розбитий ліхтар), між якими не менше трьох працюючих ліхтарів (так як інакше можна буде вказати чотири ліхтаря, серед яких хоча б два розбитих). Але якраз трьох працюючих ліхтарів поспіль стояти і не може.

2 спосіб Подивимося на ліхтарі до приходу електрика. У кожній трійці поспіль стоять ліхтарів є хоча б один зіпсований, значить все зіпсованих ліхтарів не менше 50. Пронумеруємо перші 50 зіпсованих ліхтарів зліва направо і розіб'ємо на пари: 1-й з 2-м, 3-й з 4-м, і т . Д. (Всього 25 пар) Між ліхтарями однієї пари все ліхтарі цілі, а значить їх не більше двох. Тому один з зіпсованих ліхтарів, що входять в одну пару, треба полагодити.