Ответы Mail.ru: Комбинаторика, теория чисел

hippie (26243) 1 месяц назад

Ответ: 97.

Например, одно число кратное 17 и все числа которые при делении на 17 дают остатки от 1 до 8. (Каждый из этих остатков даёт по 12 чисел.) Всего получается 8*12+1 = 97.

Больше выбрать нельзя.
Действительно, разобьём все числа не кратные 17 на пары классов эквивалентности:
числа попадают в один класс если они дают одинаковый остаток от деления на 17,
а классы попадают в одну пару если сумма остатков от деления этих чисел на 17 равна 17 (т.е. классы a и 17-a).
Всего получается 8 пар классов. Если в нашем множестве содержится число из одного из классов, то из парного к ней класса в нём нет чисел. Таким образом в это множество могут попасть числа из не более чем 8 классов. Т.к. каждый класс содержит не более 12 чисел, то всего в данное множество может попасть не более 96 чисел не кратных 17. И кроме них не более одного числа кратного 17.

ЕвгенийВысший разум

1 месяц назад

С 12- ю я вроде разобрался. А с 8 нет. Вы написали « дают остатки от 1 до 8», а почему, например , не до 9?