Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Числа от 1 до 1000

Числа от 1 до 1000
Я
   НафНаф
 
18.01.13 - 16:57
Из набора чисел 1, 2, 3, ..., 1000 выбрали ровно 501 число. Может ли оказаться так, что среди выбранных нет пары, в которой одно делится на другое?
 
 
   acsent
 
1 - 18.01.13 - 16:57
те все числа попарно взаимно просты?
   Ник второй
 
2 - 18.01.13 - 16:58
501 число не делится. Задача решена.
   mikecool
 
3 - 18.01.13 - 16:58
(2) 1 и 501
   Азат
 
4 - 18.01.13 - 16:59
нет. нельзя... 500 можно, а 501 уже нет
   НафНаф
 
5 - 18.01.13 - 17:00
(1) нет
(2) не решена
(4) не уверен, что 500 можно
   Ayvengo
 
6 - 18.01.13 - 17:01
(0) А 99 / 3 можно?
   НафНаф
 
7 - 18.01.13 - 17:01
(6) 99 на 3 делится
   Fragster
 
8 - 18.01.13 - 17:02
(3) не выбирать 1 не предлагать?
   НафНаф
 
9 - 18.01.13 - 17:02
(4) а не, уверен, что 500 можно
   acsent
 
10 - 18.01.13 - 17:04
Простых чисел от 2 до 1000 = 337
 
 Рекламное место пустует
   Ник второй
 
11 - 18.01.13 - 17:04
(3) В тексте задачи написано что выбрали число 501.. Так как второго числа не выбрали, то и делить не на что.
   НафНаф
 
12 - 18.01.13 - 17:04
(10) и что? они не обязательно должны быть простыми, даже не обязательно попарно взаимно простыми
   НафНаф
 
13 - 18.01.13 - 17:05
(11) в тексте написано, что выбрали не одно число, а пятьсот одно
   Ник второй
 
14 - 18.01.13 - 17:06
(13) Выбрали ровно пятьсот первое число. Пятьсот первое число, это 501.
   NS
 
15 - 18.01.13 - 17:08
(13) Если в списке есть X, то не должно быть 2*X
Разобъем все числа на пары X и 2*X, из каждой пары мы можем взять только одно число. Так что не больше 500 пар.
   NS
 
16 - 18.01.13 - 17:08
В (15) 1<=X<=500
   НафНаф
 
17 - 18.01.13 - 17:10
(15) хм, а число 2 должно попасть в пару (1,2) или в пару (2,4)?
и в какую пару должно попасть число 999?
   NS
 
18 - 18.01.13 - 17:11
Глупость я написал, сейчас еще подумаю.
   acsent
 
19 - 18.01.13 - 17:12
Берем все простые числа из диапазона.
Вопрос можно ли убрать одно простое и добавить 2 непростых чтоб выполнялось условие?
Что-то мне кажется что нет
   Азат
 
20 - 18.01.13 - 17:12
(5) 500 - 999 -> ни одно не делится на другое
   НафНаф
 
21 - 18.01.13 - 17:16
(20) да понял я в (9)
   НафНаф
 
22 - 18.01.13 - 17:17
(19) можно, так как простых там сильно меньше половины
   acsent
 
23 - 18.01.13 - 17:20
(22) например?
   НафНаф
 
24 - 18.01.13 - 17:21
(23) а не, вру конечно, нельзя
но никто не сказал, что выберут именно все простые
   acsent
 
25 - 18.01.13 - 17:22
(24) ну так тем более
   НафНаф
 
26 - 18.01.13 - 17:24
(25) что тем более?
среди чисел от 1 до 10 всего 4 простых и пятого не добавить
но запросто можно взять другие 5 чисел, а вот 6 нельзя
   Lama12
 
27 - 18.01.13 - 17:33
(0) Не может.
500 - это ровно половина.
Т.е. 1 не может , потому что каждое 1-е число будет делиться на 1.
2 не может потому что каждое 2-е будет делиться на 2.
3 не может потому что каждое 3-е будет делиться на 3.
4 не может потому что каждое 4-е будет делиться на 4.
и т.д. до 500.
остаются только начиная с 501-го, а значит выбрать можно только 499. Что противоречит условию задания.
   acsent
 
28 - 18.01.13 - 17:35
если в выбранных числах есть число <=500, то как минимум не должно быть одного числа > 500
   НафНаф
 
29 - 18.01.13 - 20:16
(28) ну неправда, может быть любое простое в интервале от 501 до 1000
   НафНаф
 
30 - 18.01.13 - 20:17
(27) можно 500 выбрать, гарантированно
"3 не может потому что каждое 3-е будет делиться на 3 " и что?
   Necytij
 
31 - 18.01.13 - 21:27
(30) и тогда оно войдет в пару... каждому 3ему числу в твоем списке более 500... или в каждое из 1000 /3 = 333 чисел. А тогда у тебя уже останется только 667 чисел для выбора.

500 можно. Потому что в 501 - 1000 (500 чисел), и они друг на друга не делятся. Одна спускаясь ниже получаем пары сразу 500 = 1000 / 2, 499 = 998 /2 и т.д.
Если выбрано 501 число - тогда не может выполниться условие, что там не будет такой пары, где одно число кратно другому.
   НафНаф
 
32 - 19.01.13 - 00:08
(31) не, непонятно про доказательство
   Asirius
 
33 - 19.01.13 - 00:33
Нетривиальный набор из 500 чисел:
334,335,...,667 - итого подряд 334 числа
669,671,...,999 - итого 166 нечетных чисел
 
 
   NS
 
34 - 19.01.13 - 01:51
Хм. А вот и доказательство.
Пусть у нас есть набор из 501 чисел.
Допустим в этом наборе есть два, но тогда в нем не может быть 501 числа, так как нечетных чисел больших двух всего 499. То есть числа два в наборе нет.

То есть у нас есть набор из 501 числа, в котором нет двух, и любое число из набора не делится на другое.
Тогда если мы любое число из набора меньшее либо равное 500 умножим на два, то набор не перестанет удовлетворять условию (0)

Берем по очереди все числа из набора меньшее либо равное 500 и умножаем на два до тех пор пока оно не войдет в интерал 502..1000 (а любое число меньшее либо равное пятисот умножением на два можно привести к этому интервалу)

В итоге мы получили 501 разное число в интервале 501..1000
Чего не может быть, в этом интервале всего 500 чисел.
   Asirius
 
35 - 19.01.13 - 02:37
(34) > Тогда если мы любое число из набора меньшее либо равное 500 умножим на два, то набор не перестанет удовлетворять условию (0)
вот это утверждение неверное, хотя на доказательство с некоторой поправкой это не повлияет.

Например у тебя в наборе есть числа 4 и 6. Умножив 6 на 2, получишь 12, что делится на 4, т.е нарушится условие из (0)
   NS
 
36 - 19.01.13 - 02:44
(35) Я каждый раз умножаю минимальное число из набора.
   НафНаф
 
37 - 19.01.13 - 18:42
(34) 6 сначала делилось на 2, а потом "после закидывания за 500" 768 не делится на 512
   NS
 
38 - 19.01.13 - 18:43
(37) правильный набор чисел не испортится.
   NS
 
39 - 19.01.13 - 18:52
Аргументация простая. если б больше а и не делится на б,
Тогда б не делится на 2а, и 2а не делится на б
   НафНаф
 
40 - 19.01.13 - 18:59
(39) после перекидываний за 500 большее может стать меньшим
   НафНаф
 
41 - 19.01.13 - 19:03
решение в (34) зачет
   sda553
 
42 - 19.01.13 - 20:39
А теперь усложняем задачу:
Какое максимальное количество чисел можно выбрать в этом интервале, чтобы все они были взаимно простыми
   НафНаф
 
43 - 19.01.13 - 21:25
(42) попарно или вообще? )))
   sda553
 
44 - 19.01.13 - 22:26
(43) Попарно конечно, не совсем понимаю как они могут вообще быть взаимно просты.
Все те же условия что и в 0
   НафНаф
 
45 - 19.01.13 - 22:29
(44) сколько ты найдешь чисел, попарно взаимнопротых7
   sda553
 
46 - 19.01.13 - 22:35
На каком множестве? Во множестве натуральных чисел я смогу найти бесконечное количество взаимно простых
   RomanYS
 
47 - 22.01.13 - 00:54
(42) Оно не может быть больше количества простых чисел, число смотри в (10)
При этом выбирать не обязательно сами простые числа, а, например, их степени.
   sda553
 
48 - 23.01.13 - 09:12
(47) Да неужели?
Возьмем взаимно простые числа в интервале 1...33
2*5,2*7,2*11,3*5,3*7,3*11,все простые числа от 13 меньше 33
Их явно больше, чем количество простых в том же промежутке
2,3,5,7,11,все простые от 13, меньше 33
   Михаил Козлов
 
49 - 23.01.13 - 11:57
Похоже решение может быть таким.
Во множестве всех натуральных чисел от 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.
 
 Рекламное место пустует
   SUA
 
50 - 23.01.13 - 12:40
(48)2*5 и 2*7 не взаимно простые ибо 2.
Ваш К.О.
   samozvanec
 
51 - 23.01.13 - 12:42
(0) если единицу выбрали, то все поделится, если нет - то не все. может оказаться, что единицу не выбрали.
   sda553
 
52 - 23.01.13 - 13:34
(50) Тогда меня (1) несколько смутил. Имелось в виду не взаимно простые, а то что в (0) во усем множестве нет ни одной пары в которой одно бы число делилось на другое
   RomanYS
 
53 - 23.01.13 - 14:51
(52) в (47) ответ на (42), а там задача отличная от (0), и (1) к ней не относится


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует