Две задачи

[alexey_rom]

Позаимствовано из блога Concrete Nonsense (там есть решения). Первая простая, вторая посложнее.

1) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два взаимно простых.

2) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два, одно из которых нацело делится на другое.

Comments

Re: global constant

[mathreader.livejournal.com]

Очень интересно! Я встречал 17 как глобальную константу в другом контексте. У Г.Штейнгауза в "100 задачах" есть такая.

Мы помещаем точки в интервал 0,1 одна за одной. Требуется сделать это так, чтобы первые k уложенных точек попадали бы ровно по одной в каждый подынтервал ( i/k, (i+1)/k ), i = 0..k-1.
Оказывается, такое можно сделать для набора из 17 точек, но для всех больших уже нельзя. (Если я ничего не перепутал.) Доказательство там тоже есть, но я его идею не понял - какие-то оценки, неравенства и т.п.

А нет ли здесь "гомоморфизма" из одной задачи в другую? Вы не знаете, где можно прочитать про решение 16-17 (сам я, боюсь, не придумаю).