Внеурочная деятельность 6В,6Г

3. Разгадай ребусы:

1).

2).

Ответы:

Занятие №2

Алгоритм Евклида

В 6-ом классе математику начинают изучать с темы «Делимость чисел». При ее изучении вы познакомились с новыми свойствами чисел. Знание признаков делимости, наибольшего общего делителя полезно при сокращении дробей. Существует несколько способов нахождения наибольшего общего делителя.

Начнем с примера:

Даны два числа 24 и 30. Выпишем все делители этих чисел.

Делители 24 – 1, 2, 3, 4, 6, 8, 12, 24.

Делители 30 – 1, 2, 3, 5, 6, 10, 15, 30.

Общие делители – 1, 2, 3, 6.

Наибольший общий делитель – 6. НОД(12,30)=6.

Как отыскивать НОД? Один способ приведен выше – выписать все делители каждого числа, выбрать общие, наибольший из них и есть НОД. Способ вполне понятный, только громоздкий.

Есть другой способ (он нам известен).

Чтобы найти НОД нескольких натуральных чисел, надо:

1) Разложить их на простые множители;

2) Из множителей, входящих в разложение одного из этих чисел, вычеркнуть те, которые не входят в разложение других чисел;

3) Найти произведение оставшихся множителей.

30 2 24 2

15 3 12 2 НОД(24,30)=2^.3=6

5 5 6 2

1 3 3

1

Способ этот очень прост, понятен и удобен, но у него есть существенный недостаток: если данные числа очень велики, да еще и не очень легко раскладываются, то задача отыскания НОД становится довольно трудной. К тому же может оказаться, что, основательно потрудившись, мы убеждаемся, что НОД чисел равен 1 и вроде бы вся работа проделана зря.

Есть еще один замечательный способ отыскания НОД без какой бы ни было предварительной обработки чисел. Такой способ придумали древнегреческие ученые более двух тысяч лет тому назад. Он носит название «алгоритм Евклида».

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

23: 4=5(ост.3)

Число 23 здесь делимое, 4- делитель, 5 – неполное частное и 3 – остаток. В числе 23 содержится 5 раз по 4 да еще 3. Имеем: 23=4^.5+3.

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

Теперь можно познакомиться с алгоритмом Евклида.

Пусть требуется найти НОД(102; 84). Найдем для этих чисел неполное частное и остаток, т.е. разделим одно на другое:

102=84^.1+18, 18<84.

Теперь проделаем такую же операцию для чисел 84 и 18:

84=18^.4+12, 12<18.

Следующий шаг – для 18 и 12:

18=12 ^.1+6, 6<12.

Теперь – для 12 и 6:

12= 6^.2+0.

Процесс закончился.

Может ли этот процесс оказаться бесконечным? Нет, потому что остатки убывают. Теперь присмотримся к записанным равенствам. Из первого ясно, что всякий делитель чисел 102 и 84, в том числе и наибольший, должен быть также и общим делителем, в том числе и наибольшим, чисел 84 и 18. Из второй строчки видно, что НОД(84,18)=НОД(18,12). Третья строчка показывает, что НОД(18,12)=НОД(12,6). Но из последней строчки видно, что число 6 (последний не равный нулю остаток в нашей цепочке равенств) делит нацело число 12 и является НОД чисел 6 и 12, а, следовательно, и 12 и 18, и18 и 84, и 84 и 102. Таким образом, НОД(102,84)=6; мы даже не пытались разложить на множители числа 102 и 84!

Вот эта последовательность операций и называется алгоритмом Евклида. Удобство алгоритма Евклида становится особенно заметным, если применить хорошо продуманную форму записи, например такую:

В этой табличке сначала записывают исходные числа, делят большее на меньшее в уме, записывая остатки справа, а частные – внизу, пока процесс не закончится. Последний делитель и есть НОД.

Занятие №3

Принцип Дирихле

Принцип Дирихле широко известен в такой, несколько несерьезной формулировке:

если в 50 клетках сидит 51 кролик, то по крайней мере в одной клетке сидит не менее двух кроликов.

Доказательство этого принципа очевидно. Действительно, пусть это утверждение неверно, тогда в каждой клетке сидит не более одного кролика, и, следовательно, в 50 клетках — не более 50 кроликов, а их должно быть 51. Получили противоречие.

Решение задачи с помощью принципа Дирихле сводится к выбору «кроликов» и «клеток». Иногда не совсем очевидно, кто в данной задаче является «кроликом», и что служит «клеткой».

Задачи:

1. Доказать, что из числа любых 13 учащихся найдутся по меньшей

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

Обсуждение решения.

- Как вы понимаете выражение «по меньшей мере»?

- Действительно, так как количество месяцев в году 12, то из 13

учеников найдется по крайней мере 2 ученика с одинаковыми

месяцами рождения.

2. Имеется 25 конфет 3 сортов. Верно ли, что не менее 9 из них будут какого-то одного сорта?

Решение

Пусть «клетками» у нас будут сорта конфет, а «кроликами» - сами конфеты. По принципу Дирихле найдется «клетка», в которой не менее 25 / 3 «кроликов». Так как 8 < 25 / 3 < 9, то найдется 9 конфет одного сорта.

Утверждение можно доказать, проводя сразу рассуждения от противного. Пусть конфет каждого сорта не более 9, то есть не превышает восьми. Тогда всего конфет не больше 3 × 8 = 24, а по условию их 25. Противоречие.

3. В классе 30 человек. Паша сделал 13 ошибок, а остальные меньше. Доказать, что какие-то три ученика сделали одинаковое количество ошибок.

Решение

По условию задачи, наибольшее число ошибок, сделанных в работе 13. Значит, ученики могли сделать 0, 1, 2, ..., 13 ошибок. Эти варианты будут «клетками», а ученики станут «кроликами». Тогда по (обобщенному) принципу Дирихле (14 клеток и 30 зайцев) найдутся три ученика, попавших в одну «клетку», то есть сделавших одинаковое число ошибок.

4. В квадратном ковре со стороной 1 м моль проела 51 дырку (дырка — точка). Докажите, что некоторой квадратной заплаткой со стороной 20 см можно закрыть не менее трёх дырок.

Решение

Весь ковер можно накрыть такими заплатками.

(1м2 = 10000см2,10000см2 : (20*20) = 25) 25-ю заплатами. «Клетка» - заплатка, «кролики» - дырки. Если одна заплатка закрывает две дырки, то всего закроется 50 дырок, но по условию 51 одна дырка, значит, какая-то из заплаток закроет три дырки.

По принципу Дирихле какая-то из этих заплат накроет не менее трех дырок.

5. Можно ли разложить 44 шарика на 9 кучек так, чтобы количество шариков в разных кучках было различным?

Решение

Предположим, нам это удалось. Упорядочим кучки по возрастанию количества шариков. Тогда в первой кучке должно быть не меньше одного шарика, во второй — не меньше двух, в третьей — не меньше трех и т. д. Всего шариков должно быть не меньше, чем 1 + 2 + 3 + ... + 9 = 45. А у нас только 44. Противоречие.