Mathreshka

В городе Цветочном В площадей и Р улиц (Р ≥ В+1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все исходящие из неё улицы. Докажите, что вначале можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.

Сложность: 5/10

Источник: Всероссийская олимпиада школьников по математике, 1994, 10 класс

Двое играют на доске 19 х 94 клеток. Каждый по очереди отмечает квадрат по линиям сетки (любого возможного размера) и закрашивает его. Выигрывает тот, кто закрасит последнюю клетку. Дважды закрашивать клетки нельзя. Кто выигрывает при правильной игре и как надо играть?

Дополнение. Кто выигрывает при правильной игре в случае произвольного m x n поля?

Сложность: 4/10

Источник: 57-я Московская математическая олимпиада, 1994, 8 класс

Предположим, что клетки доски удалось раскрасить требуемым образом. Тогда клетки a3, c1, e1, g1, i3 «заставляют» цвета в клетках b4, b2, d2, f2, h2, h4 чередоваться:

достаточно крайних 4 рядов клеток

Клетки c3 и g3 однозначно устанавливают цвета в клетках d4 и f4. Но тогда клетка e3 имеет ровно два синих и ровно два красных угловых соседа. Противоречие.

Клетки доски 9 х 9 окрашены в красный и синий цвета. Докажите, что найдётся или клетка, у которой ровно два красных угловых соседа, или клетка, у которой ровно два синих угловых соседа.

Угловыми соседями называются клетки, у которых есть общий угол (точка), но нет общих сторон.

Сложность: 4/10

Источник: Всероссийская олимпиада школьников по математике, 2002, 8 класс

Mathreshka

Mathreshka

Interesting problems from job interviews and maths contests. For more please visit our telegram channel @mathreshka (https://t.me/mathreshka)