Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Комбинаторика, теория чисел

Евгений Высший разум (188283), закрыт 2 месяца назад
Какое наибольшее количество натуральных чисел от 1 до 200 включительно можно выбрать так, чтобы сумма никаких двух из них не делилась на 17?
Лучший ответ
hippie Просветленный (29273) 2 месяца назад
Ответ: 97.

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

Больше выбрать нельзя.
Действительно, разобьём все числа не кратные 17 на пары классов эквивалентности:
числа попадают в один класс если они дают одинаковый остаток от деления на 17,
а классы попадают в одну пару если сумма остатков от деления этих чисел на 17 равна 17 (т.е. классы a и 17-a).
Всего получается 8 пар классов. Если в нашем множестве содержится число из одного из классов, то из парного к ней класса в нём нет чисел. Таким образом в это множество могут попасть числа из не более чем 8 классов. Т.к. каждый класс содержит не более 12 чисел, то всего в данное множество может попасть не более 96 чисел не кратных 17. И кроме них не более одного числа кратного 17.
ЕвгенийВысший разум (188283) 2 месяца назад
Спасибо, попробую разобраться
ЕвгенийВысший разум (188283) 2 месяца назад
С 12- ю я вроде разобрался. А с 8 нет. Вы написали « дают остатки от 1 до 8», а почему, например , не до 9?
ЕвгенийВысший разум (188283) 2 месяца назад
Все, спасибо, я понял
Остальные ответы
Джек Барден Ученик (169) 2 месяца назад
Си Шарп говорит, шо 97
Тут любопытного то , что неэффективный алгоритм будет работать больше миллиона лет
Похожие вопросы