Задача 109708
|
|
 |
Условие
Докажите, что можно разбить все множество натуральных чисел на 100 непустых подмножеств так, чтобы в любой тройке a, b, c, для которой a + 99b = c, нашлись два числа из одного подмножества.
Решение
Выделим в i-е множество (1 ≤ i ≤ 99) все чётные числа, дающие при делении на 99 остаток i – 1, а в сотое множество – все нечётные числа. Очевидно, что среди любых чисел a, b и c, удовлетворяющих уравнению a + 99b = c, чётное количество нечётных. Если среди них два нечётных, то они из сотого множества, иначе a и c из одного множества, так как они чётные и дают одинаковые остатки от деления на 99.
