alexey_rom (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
alexey_rom) wrote2009-12-01 02:41 pm
alexey_rom) wrote2009-12-01 02:41 pm
Entry tags:
Две задачи
Позаимствовано из блога Concrete Nonsense (там есть решения). Первая простая, вторая посложнее.
1) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два взаимно простых.
2) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два, одно из которых нацело делится на другое.
1) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два взаимно простых.
2) Дано 51 различное целое число от 1 до 100 включительно. Доказать, что среди них найдётся два, одно из которых нацело делится на другое.
no subject
no subject
вариации на тему
В первой, кстати, представляет интерес получение точной оценки. Была какая-то задача с похожей тематикой, где для 16 чисел строился некий пример, а для 17 уже всегда что-то находилось. Но само условие я сейчас забыл -- надо будет потом вспомнить.
Re: вариации на тему
Согласен.
Да.
global constant
Доказать, что среди 16 последовательных натуральных чисел всегда существует число, взаимно простое с остальными, а среди 17 -- уже не всегда.
Можно сформулировать иначе -- так, чтобы числа 16 и 17 явно не фигурировали, и их требовалось найти. В таком виде получается некая "глобальная константа" :)
А над усилением первой задачи надо будет немного подумать.
Re: global constant
Мы помещаем точки в интервал 0,1 одна за одной. Требуется сделать это так, чтобы первые k уложенных точек попадали бы ровно по одной в каждый подынтервал ( i/k, (i+1)/k ), i = 0..k-1.
Оказывается, такое можно сделать для набора из 17 точек, но для всех больших уже нельзя. (Если я ничего не перепутал.) Доказательство там тоже есть, но я его идею не понял - какие-то оценки, неравенства и т.п.
А нет ли здесь "гомоморфизма" из одной задачи в другую? Вы не знаете, где можно прочитать про решение 16-17 (сам я, боюсь, не придумаю).
Re: global constant
компактная укладка чисел
А задача про взаимно простые числа была в сборнике И.Л.Бабинской. Она там шла в разделе задач для самостоятельного решения, то есть там не приведены даже указания. Поэтому я не знаю, где бы это решение могло быть записано. Я сейчас его просто расскажу.
В одну сторону пример можно построить явно. Потребуем, чтобы первое число было чётным. Тогда 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: компактная укладка чисел
no subject