Две задачи

[alexey_rom]

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

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

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

Comments

Re: global constant

[mathreader.livejournal.com]

В предыдущем комменте имеется в виду, что описанное условие верно для всех k от 1 до n, если мы укладываем n точек.

компактная укладка чисел

[falcao.livejournal.com]

Из "Ста задач" я кое-что помнил, но про эту задачу, видимо, забыл. надо будет потом восстановить в памяти. Скорее всего, связи там нет.

А задача про взаимно простые числа была в сборнике И.Л.Бабинской. Она там шла в разделе задач для самостоятельного решения, то есть там не приведены даже указания. Поэтому я не знаю, где бы это решение могло быть записано. Я сейчас его просто расскажу.

В одну сторону пример можно построить явно. Потребуем, чтобы первое число было чётным. Тогда 9 чисел из 17 мы тем самым "обслужили". Далее, про второе число потребуем делимости на 3. Тогда этим же свойством будут обладать 8-е и 14-е. Осталось позаботиться ещё о пяти числах. Если наложить условие, что 6-е число кратно 5, то этим же свойством обладает и 16-е. Остались числа под номерами 4, 10 и 12. Если первое из них кратно 13, то оно не взаимно просто с самым последним числом списка. Аналогично, если потребовать делимость на 11 самого первого числа из семнадцати, то 12-е по счёту число с ним будет иметь нетривиальный общий делитель. Наконец, от 10-го числа потребуем делимости на 7. Общая схема будет такая:

2 3 2 13 2 5 2 3 2 7 2 11 2 3 2 5 2

Здесь показано, на что должно делиться то или иное число. Применение Китайской теоремы об остатках гарантирует существование такого примера, хотя его можно указать и явно. В качестве первого числа достаточно взять 27830.

В обратную сторону рассуждение такое. Пусть нам дано 16 последовательных целых чисел. Предположим, что каждое из них имеет общий простой делитель p ещё с каким-то числом из списка. Тогда p не превосходит 16-1, то есть принимает одно из значений 2, 3, 5, 7, 11, 13. Чётных и нечётных чисел у нас поровну. Без ограничения общности, потребуем, чтобы первое число было нечётно, меняя при необходимости у всех чисел знак. Обозначим наши числа через n+1, n+2, ..., n+16, где n чётно. Среди восьми имеющихся нечётных чисел на 3 делится максимум три, на 5 -- не более двух, на 7 -- то же самое, а на 11 и на 13 может делиться не более одного нечётного. Вместе получается ограничение 3+2+2+1+1=9, но такой план нереализуем, поскольку при попытке построить соответствующий пример оказывается, что одни и те же числа "с краёв" должны выступать сразу в нескольких "ролях".

Строго это можно обосновать так. Рассмотрим числа n+7, n+9, n+11 "в середине". Каждое из них делится на некоторое простое p такое, что на расстоянии p от него в нашем списке есть ещё хотя бы одно число. Сразу отпадают возможности p=11 и p=13. Понятно, что ни на 3, ни на 5, ни на 7 не могут делиться сразу два из чисел n+7, n+9, n+11. Поэтому ровно одно из них делится на 3, ровно одно на 5 и ровно одно на 7.

Последний факт означает, что из нашего ограничения в 9 чисел исчезает одна "единичка": на расстоянии 14 уже никакие нечётные числа в списке не будут. Поэтому, ввиду равенства 8=3+2+1+1+1, ровно три нечётных числа списка делятся на 3, ровно два -- на 5, и ровно по одному приходится на каждое из чисел 7, 11, 13.

У нас уже есть одно из мест, где находится число кратное 5. Это может быть только n+11 -- в противном случае на расстоянии 10 в список ничего не попадает. Отсюда ясно, что n+1 и n+11 кратны 5.

Заметим, что "ресурсов" у нас пока что "в обрез", и поэтому среди восьми нечётных чисел никакое из них не может делиться сразу на два простых числа из списка 3, 5, 7, 11, 13 -- в противном случае возникла бы "нехватка". Из этого следует, что n+1 не делится на 3. Значит, на 3 не может делиться n+7, а потому остаётся единственный вариант, когда на 3 делится n+9 вместе с числами n+3 и n+15. Но теперь выясняется, что в наш "диапазон" не укладываются числа, делящиеся на 13. Их должно быть два (одно чётное, и одно нечётное), и меньшее из них не превосходит n+3. Но n+1 и n+3 у нас уже "заняты", и если с этой целью взять n+2, то этим же свойством обладет и n+15, которое у нас тоже "задействовано", что снова приводит к "повтору".

Такая вот получается задача на "компактную укладку чисел"! :)

Далее, то нечётное число, которое кратно 13,

Re: компактная укладка чисел

[mathreader.livejournal.com]

Большое спасибо за столь развернутый ответ!