Условие
Среди натуральных чисел от 1 до 1200 выбрали 372 различных числа так,
что никакие два из них не различаются на 4, 5 или 9. Докажите,
что число 600 является одним из выбранных.
Решение
Лемма.
Среди любых 13 подряд идущих натуральных чисел
можно выбрать не более четырех так, что никакие два из них не различаются
на 4, 5 или 9.
Доказательство.
Разобьем 13 чисел
a ,
a+1
,
a+12
на 9 групп
(из одного или двух чисел) и запишем группы по кругу
в следующем порядке:
{a+4
}, {a,a+9
}, {a+5
}, {a+1
,a+10
}, {a+6
}, {a+2
, a+11
},{a+7
},{a+3
,a+12
}, {a+8
} .
Если выбрано 5 или более чисел, то некоторые два из них окажутся в одной группе или в соседних
группах.
Однако из двух соседних групп можно выбрать не более одного числа.
Лемма доказана.
Отметим 4 средних числа 599, 600, 601, 602,
а все остальные числа от 1 до 1200 разобьем на
(1200
-4)
/13
=92
группы по 13 последовательных чисел (это возможно, так как 598 делится на 13).
Из леммы следует, что в группах по 13 чисел можно выбрать не более
92
· 4
=372
-4
числа требуемым в условии образом.
Значит, отмеченные 4 числа выбраны.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
2007 |
|
Этап |
|
Вариант |
4 |
|
Класс |
|
Класс |
9 |
|
задача |
|
Номер |
07.4.9.8 |
