Имеется 11 различных натуральных чисел, не больших 20. Докажите, что из них можно выбрать два числа, одно из которых делится на другое.
Ответ: Возьмем все четные числа среди 11 выбранных и разделим каждое на максимальную степень двойки, чтобы в частном получилось нечетное число. Имеем теперь 11 нечетных чисел меньше 20. Среди них есть равные (всего нечетных чисел 10). Отсюда следует утверждение задачи.
Комментарии
Странный ответ!
Имеем разные числа, а доказываем приведя к одинаковым?
Пахнет бредом.
Попытаюсь объяснить попроще? но более громоздко. Всего максимально без пар может быть в ряду 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 - не делится ни на что, т.к нет повтора
А можно привести какое нить докозательство по проще ?
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) и внутри также произойдет преобразование путем выбрасывания "лишних" чмсел. А теперь пошел спам: какие теоремы нужны для поступления в бауманку? и пойдет флуд: я мудреця мудреця мудрец(_П_)
Нет, все нормально. Сначала делается допущение, что такой набор возможен. Затем берут числа этого набора и делят их на два несколько раз, пока можно делить нацело. Допустим, из 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. Утверждение в задаче доказано.
У меня есть другое решение, по-моему гораздо проще.
Возьмем все простые числа от 1 до 20. : 1, 3, 5 , 7 , 11, 13, 17, 19. Их всего 8. Далее если мы возьмем еще одно любое число не большее 20 - то оно гарантировано будет делится на одно из вышеприведенных простых. Где я ошибся? И если нет - то зачем нам 11 чисел, если хватит и девяти.
двойку забыл, тогда хватит и 10
А если взять девять, даже десять - с 11 по 20? Не делится. Так что, десять мало.
Из 11 чисел может быть ни одного простого.
1 не катит потому что на него все делятся
Вы ошиблись взяв 1 и вообще, кто вам сказал брать только простые числа?
"Возьмем все простые числа от 1 до 20. : 1, 3, 5 , 7 , 11, 13, 17, 19. Их всего 8. Далее если мы возьмем еще одно любое число не большее 20 - то оно гарантировано будет делится на одно из вышеприведенных простых."
не все сказано, потому как набор любой. просто если берутся другие наборы, то в них либо обязательно есть простые числа через хотя бы 1 делится на другое, либо не содержит их вообще, но делится на другое составное (8 и 16 ради примера).
во-первых 1 не простое число, (теорема чисел), во вторых конечно такие легкин задачи не будут всетрачаться на олимпиаде но если встретиться вроде этого то за такое доказательство дасться 3 балла максимум из 7 если не считать апеляцию
Более того, если взять 12 чисел из 20, то можно найти 2 таких пары(как минимум)
Вот наши клетки, которые исчерпывают собой все числа от 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, количество пар делимое-делитель увеличивается.
Можно и иначе (и наверное, более правильно/логично).
Расположим числа в клетках так, чтобы любое число, стоящее левее, делилось на любое число, стоящее правее (начиная с наибольшего делителя каждого из чисел). Множество целых чисел от 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 клетку, из них обязательно образуется пара делитель-делимое.
Я думаю у меня самое простое доказательство.)
Любое число от 1 до 10 умнож. на 2 будет наход, в числ. промежутке. от 11 до 20. Значит ,если брать 11 чисел то как мин. 1 число будет от 1 до 10. И все!
Я тоже так вначале подумал, но это не так.
x- число от 1 до 10.
2x-число от 1 до 20.
Вот и все доказательство.))
Очень глубокое доказательство. По вашему все числа от 1 до 20 делятся на 2?
Сори за 3 комента. Я думал инет лагает)
Вот простое доказательство:
Числа от 11 до 20 не являются делителями.
Числа от 1 до 10 являются делителями.
Из 11 чисел как минимум одно будет делителем. Следовательно из 11 чисел мы можем выбрать два числа одно из которых будет делиться на другое, чтд.
Среди чисел от 11 до 20 есть простые числа 11, 13, 17 и 19. Они кратны только единице и себе. Так что не каждое целое число от 11 до 20 делится на любое целое число от 1 до 10, а только некоторые. Суть в том, что некоторые целые числа от 1 до 10 делятся на другие числа этого же интервала.
На мой взгляд, самое красивое и лаконичное решение привёл автор. Ни убавить ни прибавить.
хватает 10 чисел
даже 9
Прочитал все комменты, ни одного доказательства не понял. Решил написать своё, подробное, с разжёвыванием. Пойдём от обратного. Попытаемся собрать одиннадцать чисел от 1 до 20, чтобы не было пары "делимое делитель". 1 является делителем любого числа, поэтому рассмотрим числа от 2 до 20. Ниже представлены возможные числа, в скобках - числа которые исключаются, если уже использовано число вне скобок. Так, например, если мы использовали число 4, то уже не можем использовать числа 8, 12, 16 и 20. Итак, таблица:
2 (4, 6, 8, 10, 12, 14, 16, 18, 20)
3 (6, 9, 12, 15, 18)
4 (8, 12, 16, 20)
5 (10, 15, 20)
6 (12, 18)
7 (14)
8 (16)
9 (18)
10 (20)
11
12
13
14
15
16
17
18
19
20
Для начала используем числа больше 10, которые в данном случае не могут быть делителями, так как при n>10 20:n<2. Итак, у нас есть десять чисел от 11 до 20, не нарушающие усдовия задачи. Теперь нам нужно ещё одно число. Но, исходя из таблицы, при использовании любого числа меньше 11, нам придётся исключить минимум одно из уже записанных нами чисел. При таком размене в нашем списке будет оставаться либо десять чисел, либо меньше. Вывод: собрать одиннадцать чисел, не нарушая условия, нельзя. Отсюда следует, что при использовании одиннадцати чисел найдётся по крайней мере одна пара "делимое-делитель". Что и требовалось доказать.
Мне особенно понравилось решение от:
"Оставлен Алексей Вс, 01/23/2011 - 07:36"
Правда, что уже на 9 числах всё срабатывает.
Но можно просто чуть модифицировать авторское. Заметить, что на 1 все делятся, поэтому её можно выбросить. Осталось 19 чисел. Тогда можно смело брать не 11, а 10 чисел. Или двадцатку не включать в условие. Так ещё никто не делал.
Хотя нет, решение Алексея не правильное. Ведь можно взять составные числа - 4, 6, 8, ... - и как они соотносятся между собой? Неизвестно.