Главная

11 чисел

Имеется 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать два числа, одно из которых делится на другое. 

Ответ: Возьмем все четные числа среди 11 выбранных и разделим каждое на максимальную степень двойки, чтобы в частном получилось нечетное число. Имеем теперь 11 нечетных чисел меньше 20. Среди них есть равные (всего нечетных чисел 10). Отсюда следует утверждение задачи.

Ваша оценка: Пусто Средняя: 4.2 (43 голосов)

#1Опубликовано LordOfChaos в Ср, 11/23/2011 - 18:44.

Вот наши клетки, которые исчерпывают собой все числа от 1 до 20. (само число и его делители, меньшие самого числа)
1. 20 10 5 4 2 1
2. 19 1
3. 18 9 6 3 2 1
4. 17 1
5. 16 8 4 2 1
6. 15 5 3 1
7. 14 7 2 1
8. 13 1
9. 12 6 4 3 2 1
10. 11 1
Таким образом, имеем возможность выбрать только 10 чисел, таких, чтобы одно не делилось на другое 20(10),19,18(9),17,16(8),15,14(7),13,12, а 11-е число обязательно будет делителем одного из уже выбранных. При выборе числа, меньшего 7, количество пар делимое-делитель увеличивается.

#2Опубликовано LordOfChaos в Ср, 11/23/2011 - 19:01.

Можно и иначе (и наверное, более правильно/логично).
Расположим числа в клетках так, чтобы любое число, стоящее левее, делилось на любое число, стоящее правее (начиная с наибольшего делителя каждого из чисел). Множество целых чисел от 1 до 20 входит сюда полностью.
1. 20 10 5 1
2. 19 1
3. 18 9 3 1
4. 17 1
5. 16 8 4 2 1
6. 15 5 1
7. 14 7 1
8. 13 1
9. 12 6 3 1
10. 11 1
Теперь каких бы 2 кроликов(числа) мы ни посадили в 1 клетку, из них обязательно образуется пара делитель-делимое.

#3Опубликовано Гость в Пт, 05/20/2011 - 14:09.

Более того, если взять 12 чисел из 20, то можно найти 2 таких пары(как минимум)

#4Опубликовано Гость в Чт, 04/28/2011 - 17:40.

"Возьмем все простые числа от 1 до 20. : 1, 3, 5 , 7 , 11, 13, 17, 19. Их всего 8. Далее если мы возьмем еще одно любое число не большее 20 - то оно гарантировано будет делится на одно из вышеприведенных простых."
не все сказано, потому как набор любой. просто если берутся другие наборы, то в них либо обязательно есть простые числа через хотя бы 1 делится на другое, либо не содержит их вообще, но делится на другое составное (8 и 16 ради примера).

#5Опубликовано Алексей в Вс, 01/23/2011 - 13:36.

У меня есть другое решение, по-моему гораздо проще.
Возьмем все простые числа от 1 до 20. : 1, 3, 5 , 7 , 11, 13, 17, 19. Их всего 8. Далее если мы возьмем еще одно любое число не большее 20 - то оно гарантировано будет делится на одно из вышеприведенных простых. Где я ошибся? И если нет - то зачем нам 11 чисел, если хватит и девяти.

#6Опубликовано Василий в Втр, 04/05/2011 - 18:19.

Из 11 чисел может быть ни одного простого.

#7Опубликовано Гость в Вс, 02/13/2011 - 23:58.

А если взять девять, даже десять - с 11 по 20? Не делится. Так что, десять мало.

#8Опубликовано Гость в Чт, 01/27/2011 - 15:46.

двойку забыл, тогда хватит и 10

#9Опубликовано Mikel в Чт, 07/22/2010 - 06:49.

Странный ответ!
Имеем разные числа, а доказываем приведя к одинаковым?
Пахнет бредом.

#10Опубликовано Den в Втр, 09/07/2010 - 15:16.

Нет, все нормально. Сначала делается допущение, что такой набор возможен. Затем берут числа этого набора и делят их на два несколько раз, пока можно делить нацело. Допустим, из 12 получается 3, из 16 - единицу, а из 18 - 9.

Теперь мы имеем новый набор из 11 натуральных чисел, не превышающих 20, и все они - нечетные. Очевидно, что среди них будет хотя бы два одинаковых, пусть они равны S. В исходном наборе на том же месте стоят числа типа S*(2^k), где k - некая целая степень.

Таким образом, доказано, что среди любых 11 чисел (не превышающих 20) найдется два числа вида S*(2^k), где k - натуральное, S - натуральное нечетное, одинаковое для обоих чисел.
Пусть a=S*(2^k1), b=S*(2^k2), b>a. Тогда b/a=2^(k2-k1) - целое число. Иначе говоря, b - делится на a. Утверждение в задаче доказано.

#11Опубликовано Ordemarebys в Пт, 08/06/2010 - 01:13.

Попытаюсь объяснить попроще? но более громоздко. Всего максимально без пар может быть в ряду 8 чисел длящихся только на 1 (с учетом того, что в ряду числа не смогут повторится, единица не входит в эти числа)эти числа не будут иметь делителя (если в ряду нет единицы) все остальные числа в ряду от 1 до 20 делятся либо на 2 и/или на 3, поэтому оставшиеся 3 числа в ряду всегда буду делится между собой.
20 - 1,2,4,10
19 - 1
18 - 1,2,3,6,9
17 - 1
16 - 1,2,4,8
15 - 1,5,3
14 - 1,7,4,3
13 - 1
12 - 1,2,3,4,6
11 - 1
10 - 1,2,5
9 - 1,3
8 - 1,2,4
7 - 1
6 - 1,3,2
5 - 1
4 - 1,2
3 - 1
2 - 1
1 - не делится ни на что, т.к нет повтора

#12Опубликовано мудрец с горы заблуждения в Чт, 04/28/2011 - 23:41.

Ordemarebys число 20 делится еще на 5) а если подумать немного... 1 отпадает сразу(на него делится каждое целое)=>остается 19. 2 тоже отбрасываем(если будет 2 то числа 4,6,8,10,12,14,16,18,20-9 чисел не могут быть и у нас остается 19-9=10 чисел среди котрых есть 3 и 9=>2 не подходит).остается 18 возможных чисел(мы выкинулы 1 и 2). берем 3. у нас остается 17 чисел(без 9). Но мы должны выкинуть число 4 , 5 , 10(так как на них делится 20) и внутри также произойдет преобразование путем выбрасывания "лишних" чмсел. А теперь пошел спам: какие теоремы нужны для поступления в бауманку? и пойдет флуд: я мудреця мудреця мудрец(_П_)

#13Опубликовано VASKO-de-GAMA в Пнд, 01/17/2011 - 20:06.

А можно привести какое нить докозательство по проще ?