Числа от 1 до 1000 #648037

Из набора чисел 1, 2, 3, ..., 1000 выбрали ровно 501 число. Может ли оказаться так, что среди выбранных нет пары, в которой одно делится на другое?

те все числа попарно взаимно просты?

501 число не делится. Задача решена.

1 и 501

нет. нельзя... 500 можно, а 501 уже нет

нет не решена не уверен, что 500 можно

А 99 / 3 можно?

99 на 3 делится

не выбирать 1 не предлагать?

а не, уверен, что 500 можно

Простых чисел от 2 до 1000 = 337

В тексте задачи написано что выбрали число 501.. Так как второго числа не выбрали, то и делить не на что.

и что? они не обязательно должны быть простыми, даже не обязательно попарно взаимно простыми

в тексте написано, что выбрали не одно число, а пятьсот одно

Выбрали ровно пятьсот первое число. Пятьсот первое число, это 501.

Если в списке есть X, то не должно быть 2*X Разобъем все числа на пары X и 2*X, из каждой пары мы можем взять только одно число. Так что не больше 500 пар.

В 1<=X<=500

хм, а число 2 должно попасть в пару (1,2) или в пару (2,4)? и в какую пару должно попасть число 999?

Глупость я написал, сейчас еще подумаю.

Берем все простые числа из диапазона. Вопрос можно ли убрать одно простое и добавить 2 непростых чтоб выполнялось условие? Что-то мне кажется что нет

500 - 999 -> ни одно не делится на другое

да понял я в

можно, так как простых там сильно меньше половины

например?

а не, вру конечно, нельзя но никто не сказал, что выберут именно все простые

ну так тем более

что тем более? среди чисел от 1 до 10 всего 4 простых и пятого не добавить но запросто можно взять другие 5 чисел, а вот 6 нельзя

Не может. 500 - это ровно половина. Т.е. 1 не может , потому что каждое 1-е число будет делиться на 1. 2 не может потому что каждое 2-е будет делиться на 2. 3 не может потому что каждое 3-е будет делиться на 3. 4 не может потому что каждое 4-е будет делиться на 4. и т.д. до 500. остаются только начиная с 501-го, а значит выбрать можно только 499. Что противоречит условию задания.

если в выбранных числах есть число <=500, то как минимум не должно быть одного числа > 500

ну неправда, может быть любое простое в интервале от 501 до 1000

можно 500 выбрать, гарантированно "3 не может потому что каждое 3-е будет делиться на 3 " и что?

и тогда оно войдет в пару... каждому 3ему числу в твоем списке более 500... или в каждое из 1000 /3 = 333 чисел. А тогда у тебя уже останется только 667 чисел для выбора. 500 можно. Потому что в 501 - 1000 (500 чисел), и они друг на друга не делятся. Одна спускаясь ниже получаем пары сразу 500 = 1000 / 2, 499 = 998 /2 и т.д. Если выбрано 501 число - тогда не может выполниться условие, что там не будет такой пары, где одно число кратно другому.

не, непонятно про доказательство

Нетривиальный набор из 500 чисел: 334,335,...,667 - итого подряд 334 числа 669,671,...,999 - итого 166 нечетных чисел

Хм. А вот и доказательство. Пусть у нас есть набор из 501 чисел. Допустим в этом наборе есть два, но тогда в нем не может быть 501 числа, так как нечетных чисел больших двух всего 499. То есть числа два в наборе нет. То есть у нас есть набор из 501 числа, в котором нет двух, и любое число из набора не делится на другое. Тогда если мы любое число из набора меньшее либо равное 500 умножим на два, то набор не перестанет удовлетворять условию Берем по очереди все числа из набора меньшее либо равное 500 и умножаем на два до тех пор пока оно не войдет в интерал 502..1000 (а любое число меньшее либо равное пятисот умножением на два можно привести к этому интервалу) В итоге мы получили 501 разное число в интервале 501..1000 Чего не может быть, в этом интервале всего 500 чисел.

> Тогда если мы любое число из набора меньшее либо равное 500 умножим на два, то набор не перестанет удовлетворять условию вот это утверждение неверное, хотя на доказательство с некоторой поправкой это не повлияет. Например у тебя в наборе есть числа 4 и 6. Умножив 6 на 2, получишь 12, что делится на 4, т.е нарушится условие из

Я каждый раз умножаю минимальное число из набора.

6 сначала делилось на 2, а потом "после закидывания за 500" 768 не делится на 512

правильный набор чисел не испортится.

Аргументация простая. если б больше а и не делится на б, Тогда б не делится на 2а, и 2а не делится на б

после перекидываний за 500 большее может стать меньшим

решение в зачет

А теперь усложняем задачу: Какое максимальное количество чисел можно выбрать в этом интервале, чтобы все они были взаимно простыми

попарно или вообще? )))

Попарно конечно, не совсем понимаю как они могут вообще быть взаимно просты. Все те же условия что и в 0

сколько ты найдешь чисел, попарно взаимнопротых7

На каком множестве? Во множестве натуральных чисел я смогу найти бесконечное количество взаимно простых

Оно не может быть больше количества простых чисел, число смотри в При этом выбирать не обязательно сами простые числа, а, например, их степени.

Да неужели? Возьмем взаимно простые числа в интервале 1...33 2*5,2*7,2*11,3*5,3*7,3*11,все простые числа от 13 меньше 33 Их явно больше, чем количество простых в том же промежутке 2,3,5,7,11,все простые от 13, меньше 33

Похоже решение может быть таким. Во множестве всех натуральных чисел от 1 до M - Z(M) введем отношение частичного порядка: a<b если a делит b. Тогда задача состоит в том, чтобы найти максимальное число несравнимых элементов Ш(Z(M)) (ширина Z(M)) в этом частично-упорядоченном множестве. Есть теорема (не помню чья, простая), что ширина равна минимальному числу цепей Ц(Z(M)), покрывающих это множество. В нашем случае цепь - последовательность чисел, так что предыдущее делит следующее. Покажем, что Ц(Z(M))<=500. Для этого построим множество цепей, покрывающих Z(1000) в количестве 500 так: - концы этих цепей - числа от 501 до 1000 - закрыли числа от 501 до 1000. - для всех четных чисел из этих концов добавим их половинки - закрыли числа от 251 до 500. - и т.д. Например, для числа 624 цепь будет такой: 624<312<156<78<39.

2*5 и 2*7 не взаимно простые ибо 2. Ваш К.О.

если единицу выбрали, то все поделится, если нет - то не все. может оказаться, что единицу не выбрали.

Тогда меня несколько смутил. Имелось в виду не взаимно простые, а то что в во усем множестве нет ни одной пары в которой одно бы число делилось на другое

в ответ на , а там задача отличная от , и к ней не относится