Нечетное шестизначное число все цифры которого различны

Нечетное шестизначное число все цифры которого различны

При решении задач раздела 1.3 приходится иметь дело с размещениями из n элементов по m и теоремой умножения для чисел случаев.

Теорема 1. (умножения для чисел случаев) . Пусть какую-то часть элементов вектора x = (x₁, x₂, . , x_n) можно выбрать r способами, а остаток — s способами. Тогда весь вектор может быть выбран r•s способами.

Размещением из n элементов по m называется упорядоченное подмножество множества из n элементов, содержащее ровно m элементов. Число размещений обозначается как A n m и вычисляется по формуле

A n m =

n! (n-m)!

.

Задача 1. Из цифр 1, 2, 3, 4, 5 наугад составляется трёхзначное число (без повторяющихся цифр). Какова вероятность того, что составленное число будет чётным?

Решение. Прежде всего укажем общее число трёхзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4, 5 (без повторения):

Сколько же среди них таких, которые оканчиваются чётной цифрой? Попытаемся составить такое число. На третьем месте нужно поставить одну из цифр 2, 4; следовательно, последнюю цифру искомого трёхзначного числа можно выбрать двумя способами. После того как эта цифра будет выбрана, оставшиеся две цифры мы сможем выбрать в любом порядке из числа не использованных четырёх цифр. Это можно осуществить таким числом способов: A 4 2 = 4*3. В соответствии с теоремой умножения для чисел случаев общее число способов составления четного трёхзначного числа

Таким образом, по классической формуле вероятность интересующего нас события A будет

P(A) =

M N

=

2*4*3 5*4*3

=

2 5

.

Полученная вероятность совпадает с вероятностью того, что при произвольной перестановке цифр 1, 2, 3, 4, 5 на третьем месте окажется чётная цифра (см. типовую задачу раздела 1.2). Это нетрудно было предвидеть, но успех в решении вероятностных задач обычно приходит к тем, кто обладает для этого более солидным арсеналом средств.

Нечетное шестизначное число все цифры которого различны

При решении задач этого занятия вам пригодятся следующие признаки делимости:

Натуральное число делится на 3 тогда и только тогда, когда его сумма цифр делится на 3.
Натуральное число делится на 9 тогда и только тогда, когда его сумма цифр делится на 9.
Натуральное число делится на 2 тогда и только тогда, когда его последняя цифра чётна.
Натуральное число делится на 5 тогда и только тогда, когда его последняя цифра равна 0 или 5.
Натуральное число делится на 4 тогда и только тогда, когда число, образованное его двумя последними цифрами (в том же порядке), делится на 4.
Натуральное число делится на 8 тогда и только тогда, когда число, образованное его тремя последними цифрами (в том же порядке), делится на 8.

1. Вовочка написал в тетради число 65349*0712 в качестве примера числа, которое делится: а) на 9; б) на 3. (На месте звёздочки когда-то была написана цифра, а теперь там пятно от сладкого чая.) Помогите Вовочке восстановить пропущенную цифру. Укажите все возможные варианты!

Ответ. а) 8; б) 2, 5 или 8.

Сумма известных цифр числа равна 37.

a) Чтобы число делилось на 9, нужно, чтобы его сумма цифр делилась на 9. Это возможно, только если на месте звёздочки стоит цифра 8.

б) Чтобы число делилось на 3, нужно, чтобы его сумма цифр делилась на 3. Это возможно, только если на месте звездочки стоит одна из цифр 2, 5, 8.

2. Запишем подряд цифры от 1 до 9, получим число 123456789. Простое оно или составное? Изменится ли ответ в задаче, если каким-то образом поменять порядок цифр в этом числе?

Ответ. Составное; не изменится.

Решение. Легко проверить, что сумма цифр этого числа равна 45 и делится на 9. Значит, в силу признака делимости на 9 и само число делится на 9 и потому составное. При любой перестановке цифр числа сумма этих цифр не изменяется, поэтому число будет по-прежнему делиться на 9 (а значит, будет составным).

3. Делится ли число 32561698 на 12? Решите эту задачу: а) с помощью признака делимости на 4; б) с помощью признака делимости на 3.

Ответ. Не делится.

а) Число оканчивается на 98, а 98 не делится на 4. Поэтому по признаку делимости на 4 число на делится на 4. Но любое число, делящееся на 12, должно делиться и на 4.

б) Сумма цифр числа равна 40, а 40 не делится на 3. Поэтому по признаку делимости на 3 число на делится на 3. Но любое число, делящееся на 12, должно делиться и на 3.

4. Даша и Таня по очереди выписывают на доску цифры шестизначного числа. Сначала Даша выписывает первую цифру, затем Таня — вторую, и так далее. Таня хочет, чтобы полученное в результате число делилось на три, а Даша хочет ей помешать. Кто из них может добиться желаемого результата независимо от ходов соперника?

У Тани есть следующая выигрышная стратегия: после очередного хода Даши она должна дописать к числу такую цифру, чтобы в результате сумма цифр числа делилась на 3. Это всегда можно сделать (более того, для этого Тане достаточно использовать цифры 0, 1 и 2). Тогда после каждого хода Тани (в том числе после последнего) написанное на доске число будет делиться на 3, и Таня выиграет.

Упражнение. Попробуйте доказать, что Тане для выигрыша достаточно правильно сделать последний ход (независимо от её предыдущих ходов).

5. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр — названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

Решение. Город 9 соединён авиалиниями только с городами 3 и 6, а города 3 и 6 соединены только между собой и с городом 9. (Это можно проверить непосредственно, а можно упростить проверку, пользуясь признаком делимости на 3.) Поэтому от города 9 нельзя добраться до города 1. Стало быть, невозможно добраться и из города 1 в город 9.

6. Чтобы открыть сейф, нужно ввести код — семизначное число, состоящее из двоек и троек. Сейф откроется, если двоек в коде больше, чем троек, а сам код делится и на 3, и на 4. Какой код может открывать сейф?

В силу признака делимости на 4 код может оканчиваться только цифрами 32 (другие двузначные числа, составленные из цифр 2 и 3, не делятся на 4).

Двоек в коде больше, чем троек; значит, двоек не меньше четырёх, а троек не больше трёх. Если в коде четыре двойки и три тройки, то сумма цифр кода равна 2 · 4 + 3 · 3 = 17 и не делится на 3, поэтому и сам код не делится на 3. По аналогичной причине код не может состоять из пяти двоек и двух троек (тогда сумма цифр была бы равна 2 · 5 + 3 · 2 = 16). Значит, код может состоять только из одной тройки и шести двоек (тогда сумма цифр равна 2 · 6 + 3 · 1 = 15 и код делится на 3).

Положение единственной тройки в коде мы уже определили, а остальные цифры · двойки. Значит, подходит только код 2222232.

7. Замените звездочки в записи числа 72*4* цифрами так, чтобы это число делилось на 45. Укажите все возможные варианты!

Ответ. 72540, 72045, 72945.

Число делится на 45 тогда и только тогда, когда оно делится на 5 и на 9 (докажите это с помощью основной теоремы арифметики). Чтобы число делилось на 5, последняя цифра должна быть равна 0 или 5.

Пусть последняя цифра числа равна 0, тогда сумма известных нам цифр числа равна 7 + 2 + 4 + 0 = 13. Чтобы число делилось также и на 9, нужно дополнить сумму цифр до числа, кратного 9. Это удастся сделать, только если взять в качестве третьей цифры числа цифру 5. Этот случай даёт нам число 72540.

Пусть теперь последняя цифра числа равна 5, тогда сумма известных нам цифр числа равна 7 + 2 + 4 + 5 = 18 и уже делится на 9. Чтобы число делилось также и на 9, нужно, чтобы после дописывания ещё одной цифры сумма цифр числа по-прежнему была кратна 9. Это условие будет выполнено, только если взять в качестве третьей цифры числа цифру 0 или цифру 9. Таким образом, этот случай даёт нам ещё два числа: 72045 и 72945.

8. а) Докажите, что произведение двух последовательных чётных чисел всегда делится на 8. б) Может ли произведение четырех последовательных натуральных чисел оканчиваться на 116?

Ответ. б) Не может.

а) Из двух последовательных чётных чисел одно к тому же обязательно делится на 4 (докажите это аккуратно, пользуясь признаком делимости на 4), поэтому их произведение делится на 8.

б) Среди четырёх последовательных натуральных чисел всегда будут два последовательных чётных числа, так что их произведение должно делиться на 8 по пункту а. А число 116 не делится на 8. Значит, оно не может быть образовано тремя последними цифрами числа, делящегося на 8.

9. Докажите, что из любых семи различных цифр можно составить число, которое делится на четыре.

Достаточно доказать, что среди любых 7 различных цифр найдутся две, из которых можно составить число, кратное 4. Тогда это число можно будет поставить в конец числа, а остальные цифры расставить в произвольном порядке перед ними. Полученное число будет делиться на 4 в силу признака делимости на 4.

Среди 7 различных цифр обязательно найдутся по крайней мере две чётных (иначе среди них было бы по крайней мере 6 нечётных цифр, а нечётных цифр всего 5). Числа, кратные 4, можно составить из «хороших» пар чётных цифр (0, 2), (0, 4), (0, 6), (0, 8), (2, 4), (2, 8), (4, 6), (4, 8) и (6, 8). Остаётся ещё «плохая» пара (2, 6). Если других чётных цифр в наборе нет, то в нём должны содержаться все нечётные цифры (в том числе 1). Тогда, используя имеющиеся в наборе в этом случае цифры 1 и 6, можно составить число 16, кратное 4. Если же в наборе есть другие чётные цифры, то есть по крайней мере одна из «хороших» пар чётных цифр, а этот случай рассмотрен выше.

10. Может ли произведение числа и суммы его цифр равняться 4704?

Если число делится на 3, то в силу признака делимости и его сумма цифр делится на 3. Тогда произведение числа и суммы его цифр делится на 9. Если же число не делится на 3, то и сумма его цифр не делится на 3, значит, и произведение числа и суммы его цифр не делится на 3.

Таким образом, произведение числа на сумму его цифр либо делится на 9, либо не делится на 3. А число 4704 делится на 3, но не делится на 9.

Упражнение. В условии задачи не сказано, что число должно быть целым. Проверьте, что ответ останется тем же и для дробных чисел, записанных при помощи конечных десятичных дробей.

11. Может ли натуральное число, записываемое с помощью 10 нулей, 10 единиц и 10 двоек, быть квадратом некоторого другого натурального числа?

Сумма цифр числа, составленного из таких цифр, равна 10 · 0 + 10 · 1 + 10 · 2 = 30. Значит, в силу признаков делимости это число делится на 3, но не делится на 9.

Предположим, что искомое число m является квадратом числа n , то есть m = n 2 = n · n . Если m кратно 3, то и n кратно 3, а тогда m = n · n должно быть кратно 9.

12. Натуральное число В обладает следующим свойством: для любого числа A, которое делится на В, на В также делятся и все числа, полученные из А перестановкой цифр. Докажите, что В может быть равно только 1, 3 или 9.

Решение. Пусть число В — k -значное. Тогда среди чисел от 10 k +1 до 10 k +1 +B ровно одно число делится на B. Пусть это число имеет вид 10 m_km_{k -1}. m ₁ (в этом решении такая запись означает не произведение нескольких чисел, а одно число, состоящее из цифр 1, 0, m_k, m_{k -1}, . m ₁). Раз делимость на В не зависит от порядка цифр числа, то на В делятся также числа m_km_{k -1}. m ₁10 и m_km_{k -1}. m ₁01. Значит, и разность этих двух чисел, равная 9, должна делиться на В. А это возможно только при В = 1, В = 3 или В = 9.

• ЗАДАЧИ
• 6 класс
• Письменная работа
• Задачи для знакомства
• Ацнок с зиланА
• Чётность
• Делимость
• В триодиннадцатом королевстве
• Алгоритмы
• Математические игры
• Движение и работа
• Геометрия
• Комбинаторика
• Комбинаторика — 2
• Задачи на повторение
• Математическая абака
• География и путешествия
• Признаки делимости
• Последовательности
• От противного
• Графы
• Шахматы
• Раскраски
• Последняя цифра
• Оценка плюс пример
• Лингвистика
• История математики
• ЗАДАЧИ ДОП. НАБОРОВ
• Доп. набор 1
• Доп. набор 2

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Нечетное шестизначное число все цифры которого различны

На этом занятии все числа — целые; слово «делится» означает «делится нацело». 1. а) Придумайте три различных числа, сумма которых делится на каждое из них. б) Придумайте три числа, сумма которых делится на число, на которое не делится ни одно из них.

Ответ. а) Например, 1 + 2 + 3 = 6, и 6 делится на 1, 2 и 3.
б) Годятся любые три натуральных числа.

Решение. б) Сумма любых трёх натуральных чисел будет делиться сама на себя. Но эта сумма больше каждого из слагаемых, поэтому ни одно из них не делится на эту сумму.

2. Верно ли, что если число одновременно делится на 4 и на 6, то оно делится и на 24?

Решение. Например, число 12 делится и на 4, и на 6, но не делится на 24. Однако если число делится и на 4, и на 6, то оно делится и на 12 = НОК(4, 6).

3. Робинзон Крузо каждый второй день пополняет запасы питьевой воды из источника, каждый третий день собирает фрукты и каждый пятый день ходит на охоту. Сегодня у Робинзона тяжёлый день: он должен делать все эти три дела. Когда у Робинзона будет следующий тяжёлый день?

Ответ. Через 30 дней.

Решение. Поскольку Робинзон Крузо каждый второй день пополняет запасы питьевой воды из источника, каждый третий день собирает фрукты и каждый пятый день ходит на охоту, промежуток между двумя тяжёлыми днями должен состоять из числа дней, кратного 2, 3 и 5. Нас интересует следующий тяжёлый день, поэтому нужно выбрать наименьшее из таких чисел. Это число 30 = 2·3·5 = НОК(2, 3, 5) (убедитесь в этом самостоятельно).

4. Не вычисляя произведения 2013 · 15 · 77, определите, делится ли оно на 2, 3, 9, 35, 55, 80, 6039.
Ответ. На 2 и 80 не делится, на остальные — делится.

Поскольку 2013, 15 и 77 — нечётные числа, их произведение тоже нечётно (вспомните предыдущее занятие!), то есть не делится на 2. Поскольку 80 делится на 2, все числа, делящиеся на 80, должны быть чётными. Значит, число 2013 · 15 · 77 не делится также и на 80.

Число 15 делится на 3, поэтому и всё произведение делится на 3. На 9 ни один из сомножителей не делится, зато два из них (15 и 2013) делятся на 3, поэтому всё произведение делится на 9 (ведь 9 = 3·3). Аналогично, поскольку 15 делится на 5, а 77 делится на 7, произведение делится на 35 = 5·7; поскольку 15 делится на 5, а 77 делится на 11, произведение делится на 55 = 5·11; поскольку 2013 делится на 2013, а 3 делится на 3, произведение делится на 6039 = 2013·3.

Натуральное число, большее единицы, называется простым, если делится нацело только на единицу и на само себя. Например, числа 2, 3, 5, 7, 11 — простые. 5. В магическом квадрате суммы чисел в каждой строке, в каждом столбце и на обеих диагоналях равны. Можно ли составить магический квадрат 5×5 из первых 25 простых чисел?

Подсказка. Вспомните тему предыдущего занятия!

Сначала заметим, что среди всех простых чисел только одно чётное — это число 2. Действительно, любое другое чётное натуральное число делится, кроме единицы и самого себя, ещё и на 2, и потому не является простым.

Теперь предположим, что магический квадрат удалось составить из первых 25 простых чисел. Среди них есть двойка, а остальные 24 числа — нечётные. В той строке, где окажется двойка, сумма всех чисел будет чётной, ведь там одно чётное число и четыре нечётных. Во всех остальных строках все числа будут нечётными, а сумма пяти нечётных слагаемых также нечётна. Поэтому сумма чисел во всех строках не может оказаться одинаковой. Полученное противоречие доказывает, что магический квадрат невозможно составить из первх 25 простых чисел.

6. Делится ли число (111 999 − 1) на 2? А на 10?
Подсказка. Какая последняя цифра у этого числа?
Ответ. Да, делится и на 2, и на 10.

Сначала заметим, что последняя цифра произведения нескольких чисел равна последней цифре произведения их последних цифр (это следует, например, из правила умножения в столбик). Теперь найдём последнюю цифру числа 111 999 . Так как это произведение 999 сомножителей, каждый из которых равен 111 (и имеет последнюю цифру 1), его последняя цифра равна последней цифре произведения 999 единиц, то есть тоже 1. А если от этого числа отнять единицу, то у разности последняя цифра будет 0. Значит, это число делится на 10 (а заодно и на 2).

Замечание. Ответ на первый вопрос задачи можно было получить проще. Число 111 нечётное, поэтому при возведении в степень (то есть при умножении само на себя несколько раз) тоже будет давать нечётное число. Число 1 также нечётно. А разность двух нечётных чисел чётна, то есть делится на 2.

7. Найдите последнюю цифру числа: а) 3 100 ; б) 2011 2012 + 2012 2013 .

а) Начнём последовательно выписывать последние цифры степеней тройки. Для нахождения последней цифры очередной степени тройки достаточно брать последнюю цифру предыдущей степени, умножать её на 3 и брать последнюю цифру результата. Получим следующую цепочку: 3, 9, 7, 1, 3, 9, 7, 1. (проверьте!). Видно, что на каждом четвёртом месте в этой последовательности стоит единица. Поскольку 100 делится на 4, на сотом месте тоже будет стоять единица. То есть последняя цифра числа 3 100 равна 1.

Последняя цифра числа 2011 2012 равна 1 (вспомните, например, решение задачи 6). Найдём последнюю цифру числа 2012 2013 . Как мы уже отмечали при решении задачи 6, последняя цифра произведения нескольких чисел равна последней цифре произведения их последних цифр. Поэтому последняя цифра этого числа совпадает с последней цифрой числа 2 2013 . А она равна 2 (получите это самостоятельно по аналогии с пунктом а). Теперь ясно, что последняя цифра числа 2011 2012 + 2012 2013 равна сумме последних цифр каждого из слагаемых, то есть 1 + 2 = 3.

8. Допишите к числу 523. три цифры так, чтобы полученное шестизначное число делилось на 7, 8 и 9. Сколько всего таких чисел существует?

Ответ. Таких чисел два: 523152 и 523656.

Решение. Чтобы число одновременно делилось на 7, 8 и 9, необходимо, чтобы оно делилось на НОК(7, 8, 9) = 504 (вспомните задачу 3). Теперь выясним, какие из шестизначных чисел вида 523. делятся на 504. Сначала поделим 523000 на 504 с остатком: 523000 = 504 · 1037 + 352. Чтобы получить ближайшее к 523000 число, делящееся на 504, нужно взять число 504 · 1038 = 523152. Это одно из интересующих нас чисел. Следующее за ним число, делящееся на 504, равно 523152 + 504 = 523656. Следующее число, кратное 504, уже будет больше 524000. Таким образом, мы нашли все интересующие нас числа.

9. В магазине было 6 ящиков яблок, массы которых равны соответственно 15, 16, 18, 19, 20 и 31 кг. Две фирмы приобрели 5 ящиков, причем одна из них взяла в два раза больше яблок (по массе), чем другая. Какой ящик остался в магазине?

Ответ. Ящик массой 20 кг.

Решение. Поскольку одна фирма купила вдвое больше яблок, чем другая, общая масса купленных яблок должна делиться на 3 (тогда две трети купит первая компания и ещё треть — вторая). Общая масса всех яблок в магазине равна 15 + 16 + 18 + 19 + 20 + 31 = 119 кг. Осталось определить, какое из чисел 15, 16, 18, 19, 20 и 31 нужно отнять от 119, чтобы получилось число, кратное трём. Нетрудно убедиться, что это может быть только число 20.

10. Вершины тысячеугольника занумерованы по порядку от 1 до 1000. Сан Саныч отмечает каждую пятнадцатую вершину, начиная с первой (то есть вершины с номерами 1, 16, 31, 46 и т.д.). Так он делает до тех пор, пока не дойдёт до уже отмеченной вершины. Сколько вершин тысячеугольника останутся неотмеченными?

Решение. Будем выписывать номера отмеченных вершин. Первые несколько из них делятся на 15 с остатком 1: это 1, 16, 31, . 991. Дальше будет 6 и другие номера, делящиеся на 15 с остатком 6: 21, 36, . 996. Дальше будет 11 и другие номера, делящиеся на 15 с остатком 11: 26, 41, . 986. А потом — снова 1, и больше никакие вершины отмечены не будут. Если аккуратно посчитать (проделайте это!), отмеченных вершин получится 200 штук, а неотмеченных — 800.

11. Если в выражение n 2 + n + 41 подставлять n = 1, 2, 3, 4, 5, получатся простые числа 43, 47, 53, 61, 71. Верно ли, что при подстановке в это выражение любого натурального числа n получится простое число?

Решение. Если подставить в это выражение n = 41, получим сумму 41 2 + 41 + 41. Каждое слагаемое в этой сумме делится на 41, поэтому и вся сумма делится на 41. Кроме того, эта сумма, очевидно, не равна 41. А значит, она не является простым числом.

• ЗАДАЧИ
• 6 класс
• Письменная работа
• Задачи для знакомства
• Ацнок с зиланА
• Чётность
• Делимость
• В триодиннадцатом королевстве
• Алгоритмы
• Математические игры
• Движение и работа
• Геометрия
• Комбинаторика
• Комбинаторика — 2
• Задачи на повторение
• Математическая абака
• География и путешествия
• Признаки делимости
• Последовательности
• От противного
• Графы
• Шахматы
• Раскраски
• Последняя цифра
• Оценка плюс пример
• Лингвистика
• История математики
• ЗАДАЧИ ДОП. НАБОРОВ
• Доп. набор 1
• Доп. набор 2

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

ВЫСТРАИВАНИЕ ЭВРИСТИК В ОЛИМПИАДНОМ ЗАДАНИИ ДЛЯ РАЗВИТИЯ КРИТИЧЕСКОГО МЫШЛЕНИЯ Текст научной статьи по специальности «Математика»

Похожие темы научных работ по математике , автор научной работы — Совертков Петр Игнатьевич

Занятие 8. Формулы, формулы, формулы. . .
МЕТОДИКА РАБОТЫ С КЛАСТЕРОМ ПО МАТЕМАТИКЕ
Методика конструирования содержания учебных задач с помощью дидактической инженерии
Методика конструирования учебных задач с помощью дидактической инженерии
Содержательно-методические основы работы по обучению решению олимпиадных задач
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «ВЫСТРАИВАНИЕ ЭВРИСТИК В ОЛИМПИАДНОМ ЗАДАНИИ ДЛЯ РАЗВИТИЯ КРИТИЧЕСКОГО МЫШЛЕНИЯ»

2013 СЕВЕРНЫЙ РЕГИОН: НАУКА, ОБРАЗОВАНИЕ, КУЛЬТУРА № 2

ПРОБЛЕМЫ ОБРАЗОВАНИЯ П.И. Совертков

ВЫСТРАИВАНИЕ ЭВРИСТИК В ОЛИМПИАДНОМ ЗАДАНИИ ДЛЯ РАЗВИТИЯ КРИТИЧЕСКОГО МЫШЛЕНИЯ

1. Роль эвристик в выстраивании маршрута при анализе задачи

Решение любой олимпиадной задачи предполагает проведение расширенного анализа заключения задачи и его связи с условием задачи. Требуется выстроить цепочку от заключения 2 задачи к условию и задачи (рис. 1), провести разбиение данной задачи на ряд вспомогательных подзадач и осуществить последующий синтез решений вспомогательных подзадач с целью перехода от условия задачи к тому, что требуется найти или

доказать. 0__^ 0____^ 0

Олимпиадные задачи являются нестандартными ^ $ Р X

задачами, поэтому в большинстве случаев вначале р 1

осуществляется перебор известных фактов и методов с

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

Для заключения 2 находим предпосылки Р1, Р2, . Рр . Рк, из которых следует заключение 2 (рис. 2). Для условия и находим следствия 52, . . 5П. Если нашлись следствие и предпосылка Р), такие, что из следует Р., или если эти утверждения совпа-

ли, т.е. = Р., то от условия и к заключению 2 по-

строена цепь с помощью эвристик. Методика генерирования идей для выстраивания различных следствий представлена в пособии «Моделирование в интегра-тивном проекте по математике и информатике» [1].

Сокращение числа переборов различных вариантов можно провести методом деления пополам области альтернатив [2] или методом жадного подхода [3].

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

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

Обучение выстраиванию эвристик можно проводить при поиске решения одной задачи различными методами [4]. В этом случае приоритет отдается наиболее простому и рациональному решению. Большинство методических пособий по решению олимпиад-

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

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

Отбор учащихся в школе для участия в городской или районной олимпиаде по математике часто происходит по уровню усвоения школьного курса математики, т.е. с ориентацией на освоение материала в соответствующем классе.

Отбор заданий для городской олимпиады не всегда ориентируется на материал, изучаемый в соответствующем классе. Учащиеся различных классов могут решать некоторые задачи городской олимпиады, т.к. достаточно базовых знаний для решения таких задач. Нужно применить нестандартный подход либо к переосмыслению условия задачи, либо к частичному изменению известного ранее метода, либо к поиску закономерности для нескольких частных случаев и доказательству утверждения о том, что закономерность выполняется для любого значения переменной из области определения.

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

2. Поиск рационального алгоритма решения задачи

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

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

Число называется полным квадратом, если квадратный корень из этого числа является целым числом. Например, число 207936 является полным квадратом, т.к. при извлечении квадратного корня из этого числа получаем целое число 456.

Задача 1. Найти шестизначные числа с возрастающими цифрами слева направо и являющиеся полными квадратами.

Отметим сразу, что формулировка задачи предполагает оперирование числом как одним объектом при извлечении квадратного корня и оперирование его цифрами.

Если человек рассматривает число 369, то он воспринимает его сразу двумя способами — как одно число и с пониманием значения цифр.

Компьютерное оперирование числом еще не означает, что ему дана команда на перечисление цифр в этом числе. Если для компьютера задано число, а значит, выделена одна ячейка для записи этого числа, то нужно выделить ячейки для записи его цифр и, конечно, указать алгоритм получения этих цифр из данного числа.

Если компьютеру сообщена некоторая упорядоченная последовательность цифр или он сам ее образует, располагая в определенные ячейки, то нужно сообщить метод формирования самого числа из цифр с помощью десятичной системы счисления.

В дальнейшем шестизначное число обозначим следующим образом

а5а4а3а2аа = а5 -105 + а4 ■ 104 + а3 • 103 + а2 -102 + а ’10 + а ■

Разработка алгоритма для компьютерной программы может реализовываться в двух направлениях.

Первое направление — перебор цифр шестизначного числа. Сравнение цифр в порядке возрастания в этом случае окажется естественным, но потом придется определять значение числа для каждой выборки цифр, извлекать квадратный корень и определять, является ли полученное число целым числом.

Второе направление — перебор всех шестизначных чисел. Извлечение квадратного корня окажется естественной операцией, но потом придется выделять цифры каждого числа и проводить их сравнение.

Рассмотрим первый вариант выстраивания этапов решения задачи.

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

2. Осуществим проверку расположения цифр в порядке возрастания. Переменные в циклах независимые, поэтому проверка на возрастание цифр слева направо необходима. Проверка условия а < а < а < а < а < а предполагает проверку пяти условий:

3. Найдем численное значение комбинации цифр, т.е. вычислим десятичное представление числа для данных цифр.

4. Извлечем квадратный корень из полученного числа.

5. Осуществим проверку, является ли квадратный корень из числа целым числом.

6. Если квадратный корень является целым числом, то напечатаем шестизначное число и квадратный корень из этого числа.

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

Проверка двух условий — возрастания цифр и целочисленнго значения квадратного корня — требует обращения к условному оператору. Можно осуществить одновременную проверку этих условий для каждого шестизначного числа, тогда последовательность этапов нужно изменить. А можно выполнить проверку этих условий раздельно, причем в

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

Для этого варианта можно рассмотреть три варианта реализации алгоритма в компьютерной программе.

Приведем программу, написанную на языке VisualBasic, для случая, когда одновременно осуществляется проверка всех условий на упорядочивание цифр и проверка целочисленного значения квадратного корня для каждой выборки из шести цифр. Private Sub Command1_Click() Start = Timer

For a5 = 1 To 9: For a4 = 0 To 9: For a3 = 0 To 9 For a2 = 0 To 9: For a1 = 0 To 9: For a0 = 0 To 9

a = a5 * 10 Л 5 + a4 * 10 л 4 + a3 * 10 л 3 + a2 * 10 л 2 + a1 * 10 + a0: b = Sqr(a) If b = Int(b) And a5 < a4 And a4 < a3 And a3 < a2 And a2 < a1 And a1 < a0 Then Print a, b Next a0, a1, a2, a3, a4, a5

Finish = Timer: t11 = Finish — Start: Print » t11=»; t11 EndSub

Для компьютера с тактовой частотой 789 МГц программа работала 3,031 сек. Читатель может видоизменить программу так, чтобы вначале осуществлялась проверка целочисленного значения квадратного корня. Если квадратный корень не является целым числом, то отпадает необходимость проверки пяти условий на возрастание цифр и время выполнения такой программы должно сократиться.

Аналогично можно видоизменить первоначальную программу, переставив порядок проверки этих условий.

Перейдем к поиску рационального алгоритма. Работу этой программы можно значительно улучшить, сократив диапазон изменения переменных. В предложенной программе рассматривается 9 • 105 = 900000 наборов шестизначных чисел. Даже если компьютер может быстро решить поставленную задачу, то попытаемся сократить число переборов.

При уточнении диапазона изменения каждого разряда возникает идея найти минимальное число, цифры которого возрастают слева направо. Таким числом является 123456.

Затем найдем максимальное число, цифры которого возрастают слева направо, т.е. число 456789.

Если не учитывать в рассматриваемых шестизначных наборах цифр упорядочивание цифр слева направо, то в диапазоне от 123456 до 456789 получаем, что цифра в каждом диапазоне может принимать четыре значения: а5 от 1 до 4, а4 от 2 до 5, а3 от 3 до 6, а2 от 4 до 7, ах от 5 до 8, а0 от 6 до 9. Количество шестизначных чисел в этом случае равно 4 • 4 • 4 • 4 • 4 • 4 = 46 = 4096.

PrivateSubCommand1_Click() Start = Timer

For a5 = 1 To 4: For a4 = 2 To 5: For a3 = 3 To 6 For a2 = 4 To 7: For a1 = 5 To 8: For a0 = 6 To 9

a = a5 * 10 л 5 + a4 * 10 л 4 + a3 * 10 л 3 + a2 * 10 л 2 + a1 * 10 + a0: b = Sqr(a)

Next a0, a1, a2, a3, a4, a5

Finish = Timer: t2 = Finish — Start: Print » t2=»; t2

Время выполнения программы для этого алгоритма равно 0,016 сек. При рассмотрении все чисел от 123456 до 456789 постепенно возникает понимание того, что мы усложняем решение задачи, вводя 6 циклов. Изменение чисел от 123456 до 456789 проще задать одним циклом с шагом 1. В этом случае всего 456789-123456+1 =333334 чисел. И мы возвращаемся к мысли о том, что в этом случае первично задание самого числа, а потом будем определять цифры этого числа и проводить сравнение цифр.

Определить значения цифр числа в компьютерной программе можно различными способами [5].

В следующей программе реализуется алгоритм, основанный на переборе всех шестизначных чисел из указанного диапазона. Private Sub Command1_Click() Start = Timer

For a= 123456 To 456789

a5 = a \ 100000: a4 = (a \ 10000) Mod 10: a3 = (a \ 1000) Mod 10

a2 = (a \ 100) Mod 10: a1 = (a \ 10) Mod 10: a0 = a Mod 10: b = Sqr(a)

Finish = Timer: t3 = Finish — Start: Print» t3=»; t3 EndSub

Время работы этой программы равно 0,703 сек. Время увеличилось, и этому есть простое объяснение. Для каждого числа применяется шесть операторов, чтобы определить его цифры в разрядах. Конечно, программу можно изменить так, чтобы время работы уменьшилось. Цифры разрядов можно определять не для всех чисел из указанного оператора, а только для чисел, являющихся точным квадратом. Учащимся предлагается написать соответствующую программу.

Можно ли еще сократить время работы программы?

Шестизначных чисел, являющихся точным квадратом и имеющих цифры, расположенные в порядке возрастания, не так уж и много. Не нужно рассматривать все шестизначные числа, будем искать числа, квадраты которых являются шестизначными числами и их цифры расположены в возрастающем порядке. Таких чисел значительно меньше, чем шестизначных чисел. Как перечислить числа, квадрат которых является шестизначным числом? Определить наименьшее целое число, квадрат которого равен или превосходит число 123456.

Находим минимальное число, равное ^.j123456 J = 352, где полуквадратные скобки

снизу означают округление числа с избытком.

Находим максимальное число, равное 456789 J = 675, где полуквадратные скобки сверху означают округление числа с недостатком.

Определение минимального и максимального значений диапазона можно выполнить в компьютерной программе с помощью простых операторов.

Организуя цикл от 352 до 675 с шагом 1 по переменной b, получим 324 случая для перебора.

Private Sub Command1_Click() Start = Timer

For b = 352 To 675: a = b Л 2: a5 = a \ 100000: a4 = (a \ 10000) Mod 10 a3 = (a \ 1000) Mod 10: a2 = (a \ 100) Mod 10

a1 = (a \ 10) Mod 10:a0 = a Mod 10

Finish = Timer: t4 = Finish — Start: Print » t4=»; t4

Время работы этой программы столь мало, что компьютер показал его равным нулю.

Сопоставляя полученные объемы выборок 900000, 333334, 324, мы видим, что рациональный выбор алгоритма позволяет значительно сократить прогон цикла, причем отпала необходимость в проверке квадратного корня на условие целочисленного значения.

3. Выстраивание эвристик на основе анализа задачи от заключения к условию

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Рассмотрим формирование эвристик на примере решения задач олимпиады Сургутского государственного университета по математике, проведенной в 2013 г.

Для некоторых задач вначале приведем структуру связей от заключения к условию задачи, реализующую схему рисунка 2.

Задача 2. Доказать, что число 11100 -1 делится на 100.

Заключение Z задачи: 11100 -1 делится на 100.

Р\ — число 11100 имеет следующий вид: 11100 =. 01

Р2 — показать, что число 11100 -1 делится на 100 или на 10 и потом еще раз на 10.

Условие U: дано число 11100 -1.

S\ — определить закономерность для двух последних цифр степеней 111,112,113. 11100.

S2 — разложить число 11100 -1 на множители.

Рассмотрим попытки реализации следствий и соединения их с предпосылками.

Первый способ решения задачи.

11100-1 = (1 + 10) • (1 + 10) • (1 + 10) •. • (1 + 10)-1

Перемножая единицы из всех скобок, получим 1.

Далее в одной скобке возьмем число 10, а в остальных скобках по единице. Перемножая эти числа, получим 10. Но таких сочетаний можно составить столько, сколько скобок, а значит, при сложении получим 1000.

Затем выберем два раза по 10 из двух скобок и умножим на единицы из остальных скобок. Таких сочетаний можно составить целое число, а значит, полученная сумма будет кратна 100. Остальные произведения, а тем более и их суммы, содержат более высокие степени числа 10. В итоге полученное число будет делиться на 100.

Второй способ решения.

Используя формулу an — bn = (a — b) (an-1 + an-2b + a»-3b2 +. + abn-2 + bn), получим 11100 -1 = (11-1) (1199 + 1198 +. + 11 + 1) = 10 (1199 +1198 +. + 11 + 1).

Докажем, что 1 199 +1 198 +. + 1 1 + 1 делится на 10.

Числа 11, 112, 113 окачиваются на единицы.

Произведение любых двух натуральных чисел, окачивающихся на единицу, является числом, оканчивающимся на единицу.

Действительно, (10а +1) (10Ь + 1) = 100аЬ + 10а +10Ь +1. Следовательно, любая степень 11″ = (10 +1)» при натуральном п окачивается на единицу.

В сумме 1 199 + 1198 +. + 1 1 + 1 сто чисел, окачивающихся на 1, поэтому сумма этих единиц равна 100 и вся сумма кратна 10.

Используя формулу бинома Ньютона

(а + Ь)п = ап + С^^ + С2an~2b2 +. + Cкan-kbk +. + Сn-1abn-1 + Ьп , п е N

(10 + 1)100 = 10100 + С;оо -1099 -1 + С20 1 09812 +. + ^ 10100-к1к +. + С9080102 -Г + С» 10-199 +1100.

Все коэффициенты Ск — целые числа, причем С^ = 100, поэтому 11100 =. 01.

Число 11100 -1 имеет две последние цифры 00, поэтому оно делится на 100.

Для доказательства утверждения достаточно показать, что число 11100 =. 01.

111 = 11, 112 = 121, 113 = 1331, 114 = 14641, 115 = 161051. Можно записать 115 = а — 50 +1, где а — натуральное число.

1110 = (115 )2 = (а — 50 +1)2 = 2500а2 + 100а +1 = 100Ь +1, где Ь — натуральное число.

Число 1110 имеет вид 1110 =. 01 (кстати, это утверждение некоторые участники

олимпиады проверили непосредственным умножением).

11100 =(1110 )10 = (100Ь +1)10 = (100Ь +1) — (100Ь +1) -. — (100Ь +1)

(100Ь +1) — (100с +1) = 10000Ьс + 100Ь + 100с + 1 = (100Ьс + Ь + с)100 +1 = 100^ +1.

Следовательно, 11100 =. 01. Число 11100 -1 делится на 100.

Замечание. Не всегда зависимость, установленная для некоторых натуральных чисел, выполняется для всех натуральных чисел. Например, формула /(п) = п2 — п + 41 при п = 1, 2, 3, 4, 5, . 40 определяет простые числа, но при п = 41 получаем составное число. Поэтому замеченную закономерность нужно обосновывать для всего заявленного диапазона.

Выбор наиболее рационального способа решения данной задачи зависит от уровня подготовленности слушателя.

Если учащийся изучает математику по углубленной программе, то для него наиболее рациональным является четвертый способ с использованием формулы бинома Ньютона. Следует заметить, что само условие задачи не содержит название формулы, а поэтому в этом способе нужно догадаться о возможности применения этой формулы. В применяемой формуле важно не вычисление коэффициентов через число сочетаний, а оценка делителей этих коэффициентов.

Значительная часть учащихся, являющихся претендентами на получение золотой медали после окончания школы, а также желающих получить высокий балл по математике на ЕГЭ и продолжить обучение по естественно-математическому направлению, должна знать формулу

ап — Ьп = (а — Ь) (ап-1 + ап-2Ь + ап-3Ь2 +. + аЬп-2 + Ьп )

Эта формула, так же, как и теорема о рациональных корнях многочлена с целыми коэффициентами, не изучается в школьном курсе математики, но ее знание позволяет быстрее решать некоторые задачи части С единого государственного экзамена по теме делимости чисел.

Это равенство просто обосновывается вычислением суммы членов геометрической прогрессии а»-1 + а»-2Ъ + а»-3Ъ2 +. + аЪ»—2 + Ъ».

Этим же способом доказывается более общее равенство для любых натуральных чисел п и к:

ак» —Ък» = (а» —Ъ») (а + а(к—2)»Ъ» + а(к—3)Ъ2″ +. + а»Ъ(к—2)» + Ъ(к—»»)

Число способов решений можно увеличить, если рассмотреть разложения 11100-1 = (112 — 1) (1198 + 1196 +. + 1 12 +1) = 100 (1198 +1 196 +. + 1 12 +1)

Незначительное расширение объема знаний приводит к самому рациональному способу решения.

Для учащихся, не знакомых с выше приведенными формулами, наиболее естественно выстраивание эвристик в соответствии с первым и четвертым способом.

Задача 3. Валенок на правой ноге изнашивается через 1000 км, а на левой ноге через 1100 км. Какой максимальный путь можно пройти в валенках, если их менять местами?

Попытаемся определить путь, который можно пройти в двух валенках.

Если пройти 1000 км, то валенок на левой ноге не износится. Если пройти 1100 км, то валенок на левой ноге износится полностью. На правой ноге валенок износится через 1000 км, и нужно добавлять еще один валенок, который износится частично. Попытаемся увеличить путь, одевая новые валенки, чтобы износилось целое число пар валенок.

Рассмотрим путь, кратный 1000 и 1100. Например, 22000 км.

Чтобы пройти путь 22000 км, потребуется на правую ногу 22 валенка и на левую ногу 20 валенок. Итого 42 валенка, или 21 пара валенок. Разделив весь путь на число пар валенок, определим максимальный путь, который можно пройти в валенках, чтобы они полностью износились.

Анализ задачи от заключения к условию сразу привел к решению задачи.

Условие задачи содержит всего два числа, поэтому попытка нахождения предпосылок для заключения упростила указанную ранее схему на рис. 2.

Второй способ. Обозначим изнашиваемость каждого валенка через 1. Валенок на правой ноге за 1 км изнашивается на 1 часть. Валенок на левой ноге изнашивается на

1 часть. Два валенка за 1 км изнашиваются на величину 1 + 1 _11 +10 _ 21 . 1100 1000 1100 11000 11000

Разделив 2 валенка на общую часть изношенности валенок на одном км, получим километраж

2: —21— = 22000 и 1047,6.

Второй способ показывает, что сформулированную задачу можно решать как типовую текстовую задачу. Из-за необычности формулировки задачи только 10% участников олимпиады смогли ее решить.

Для следующих задач приведем только решения, предоставляя читателям самостоятельно выстроить эвристики в соответствии со схемой рис. 2.

Задача 4. Найдутся ли натуральные числа х, у, г такие, что 28х + 30у + 31г = 365.

Первый способ. Числа 28, 30 и 31 — это количество дней в некоторых месяцах года, число 365 — число дней в году.

Задачу можно переформулировать следующим образом. Можно ли указать несколько месяцев из 28 дней, несколько месяцев из 30 дней и несколько месяцев из 31 дня, чтобы получить 365 дней в году.

Конечно, можно. Надо перечислить все месяца года и получим х = 1, у = 4, г = 7. Второй способ решения. Числа 28, 30 и 31 отличаются незначительно, поэтому представим

28х + 30 у + 31г = 28х + (28 + 2)у + (28+3) г = 3 65, 28( х + у + г) + 2 у + 3г = 365.

Разделим 365 на 28 и найдем остаток. 365 1

-= 13— или 365 = 28 -13 +1. Если х + у + г = 13, то 2у + 3г = 1. Уравнение

2у + 3г = 1 не имеет решений в натуральных числах. Увеличим остаток за счет уменьшения частного.

365 = 12^ или 365 = 28 -12 + 29. Если х+у + г = 12, то 2у + 3г = 29. 28 28

Уравнение 2у + 3г = 29 имеет решение в натуральных числах у = 4, г = 7 и

Используя равенство х + у + г = 12, получаем два решения х = 1, у = 4, г = 7

или х = 2, у = 1, г = 9.

Третий способ. Число 28х + 30у — четное, 365 — нечетное число, поэтому 31г —

317 31 93 155 217 179 341

365-31ъ 339 272 210 148 86 24

Число 30у имеет последнюю цифру 0.

Выписывая числа, кратные 8, получаем: 8, 16, 24, 32, 40, 48, . Далее последние цифры повторяются. Число 28х может кончаться на одну из следующих цифр: 8, 6, 4, 2, 0. На основе последней цифры исключаем из таблицы числа 339, 24. Для уравнений 28х + 30у = 148, 28х + 30у = 86 находим решения в натуральных числах. Например, х = 1, у = 4, г = 7 или х = 2, у = 1, г = 9 .

Задача 5. Показать, что при любом натуральном п дробь _несократима.

Число 2″ +1 — нечетное, поэтому числа 2″ + 1 и 2 — несократимы.

Числа 2″ +1 и 2″ являются соседними натуральными числами, поэтому также несократимы.

Если предположить, что дробь 2″ +1 сократима, то и дробь 2″ +1 также будет

» 2″ сократима, что противоречит доказанному выше утверждению.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Числа 2″ + 1 и 2(» +1), т.е. 2″ + 1 и 2″ + 2 являются соседними натуральными числами, поэтому несократимы.

Если предположить, что дробь 2″ +1 сократима, то и дробь 2″ +1 также будет

сократима, что противоречит доказанному выше утверждению.

Таким образом, данная дробь несократима и задача решена.

Анализ черновиков работ участников олимпиады показывает, что учащиеся в основном разбирали условие задачи и пытались проложить маршрут от условия задачи к заключению. Одновременный анализ заключения задачи и условия задачи, причем с приоритетом анализа заключения задачи, является сложным мыслительным актом. Сложность этого акта состоит в том, что, удерживая в памяти переход от условия и к следствию Si (рис. 2) и переход от посылки Р) к заключению задачи 2, нужно установить зависимость между и р

1. Совертков П.И. Моделирование в интегративном проекте по математике и информатике. Элективный курс: Методическое пособие. — М.: БИНОМ. Лаборатория знаний, 2012. — 262 с. — С. 104.

2. Совертков П.И. Некоторые направления развития поисковой деятельности учащихся по математике и информатике: Учебное пособие. — Сургут: РИО СурГПУ, 2007. -С. 137.

4. Совертков П.И. Сургутские олимпиады по математике. — Сургут: Изд-во Центра развития образования, 2008. — С. 103.

5. Совертков П.И. Моделирование. С. 117-123.