Попарные НОДы (отбор на всеукраинскую олимпиаду)

[Ktina]

а) Дано 64 натуральных числа. Сосчитаем все 2016 их попарных наибольших общих делителей. Могут ли получиться числа 1, 2, 3, ... 2016?

б) Если в условии задачи заменить 64 на меньшее натуральное число $n$, то при каких $n$ такая конструкция может получиться?

[hippie]

а) На простое число 997 делится ровно 2 числа из множества 1, 2, 3, ..., 2016.
Если в исходном множестве на 997 делятся 2 числа, то в множестве НОД на него будет делиться только одно число;
Если же в исходном множестве на 997 делится более двух чисел, то в множестве НОД на него будет делиться не менее трёх чисел.

б) При $n\in \{ 1,2,3\}.$

(Оффтоп)

А в каком году и в какой области предлагали такие задачи?

[Ktina]

hippie в сообщении #538732 писал(а):

а) На простое число 997 делится ровно 2 числа из множества 1, 2, 3, ..., 2016.
Если в исходном множестве на 997 делятся 2 числа, то в множестве НОД на него будет делиться только одно число;
Если же в исходном множестве на 997 делится более двух чисел, то в множестве НОД на него будет делиться не менее трёх чисел.

б) При $n\in \{ 1,2,3\}.$

(Оффтоп)

А в каком году и в какой области предлагали такие задачи?

Первый пункт я решила иначе.
Среди чисел от 1 до 2016 - ровно 1008 чётных. Но чётный НОД может образоваться только между двумя чётными числами. Поскольку 1008 не является треугольником натурального числа, такое не может быть возможным.

(Оффтоп)

Минуточку, сейчас посмотрю...2009-й год, Харьковская область, третий подъезд, третий этаж.
http://ri.kharkov.ua/olympiad/Otbor2009_tur3.pdf (10-й класс, задача 1).

[hippie]

(Оффтоп)

Ktina в сообщении #538844 писал(а):

Минуточку, сейчас посмотрю...2009-й год, Харьковская область, третий подъезд, третий этаж.
http://ri.kharkov.ua/olympiad/Otbor2009_tur3.pdf (10-й класс, задача 1).

БОЛЬШОЕ СПАСИБО за ссылку!!! Она мне очень пригодилась!