Теорема 1 - Сгибнев А. И. Исследовательские задачи для начинающих

Теорема 1.

  1. Единица – первое проигрышное число.


2. Пусть Х – проигрышное число, тогда:

А. Числа, большие Х и меньшие 2Х+1 – выигрышные;

Б. 2Х +1 – проигрышное число.
Доказательство.

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

2.А. Пусть Х – проигрышное число, N – число, причем

X < N < 2X+1

Очевидно,

N-X ≤ N/2

Поэтому можно отнять N-X камней и получить проигрышное число Х.

Б. Докажем, что 2Х+1 – проигрышное число.

Докажем от противного: Пусть 2Х+1 – выигрышное число. Тогда ходящий игрок (назовем его Первым) может за один ход оставить в кучке проигрышное число камней. По условию задачи он не может брать больше половины, т.е. больше Х камней. Значит, после хода Первого игрока останется Y камней, где

X+1 ≤ Y ≤ 2Х

По доказанному, все такие числа – выигрышные. Противоречие.

Теорема доказана.
Теорема 2.
А. Все числа вида Хn = 2n-1, где n – любое натуральное число, – проигрышные.

Б. Хn=2n-1 – единственные проигрышные числа.
Доказательство.
А. Доказательство проводится методом математической индукции.

X1 = 2-1 = 1 – проигрышное число. Пусть Хn – проигрышное число.

По теореме 1, если Х –проигрышное число, то и 2Х+1 –проигрышное число.

следовательно Хn+1 = 2Хn+1 = 2(2n-1)+1= 2*2n-1= 2n+1-1 - проигрышное число.

Б. Пусть Y не число вида 2n-1. Тогда для некоторого числа n выполнено:

2n - 1 < Y < 2n+1 - 1

Очевидно, Y - 2n ≤ Y/2, значит, из Y можно получить проигрышное число камней 2n - 1. Т.е. Y – выигрышное число.

Теорема доказана.

Первые проигрышные числа:

№ проигр. числа

Число

Формула

1

1

21-1=1

2

3

22-1=3

3

7

23-1=7


Комментарий. Работа выполнена в Красноярской летней школе в 2000 году. Данные о возрасте участников не сохранились.


^ Задача о мудрецах у людоедов

Выполнил:

Абасов Артём

Летняя школа «Интеллектуал»

Руководитель Сгибнев А.И.


Занумеруем мудрецов так: 0, 1, 2, …, n (всего n+1). Нулевой видит всех, n-й не видит никого. Зашифруем белые колпаки 0, а черные колпаки 1. Тогда последовательность мудрецов шифруется последовательностью 0 и 1.

Рассмотрим частные случаи:

1) Легко гарантированно спасти каждого второго мудреца. Разобьём мудрецов на пары, и в каждой паре первый мудрец говорит цвет колпака второго.

2) Рассмотрим случай, когда мы хотим спасти двух мудрецов из трех. Пусть 0-ой мудрец скажет ”0”, если видит перед собой комбинации 00 или 11. В противном случае пусть скажет “1”. Тогда по его ответу 1-й мудрец поймёт, совпадает ли его цвет с цветом 2-го.

Заметим, что мы разбили 4 возможные последовательности – 00, 01, 10 и 11 – на 2 списка по 2 последовательности:


00

11


01

10




При этом списки обладают такими свойствами:

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

Свойство Б. Любые две последовательности из разных списков отличаются друг от друга не менее, чем в одном разряде (т.е. все числа разные).


Теперь рассмотрим общие случаи.

Утверждение. Гарантированно можно спасти n из n+1 мудрецов.

Ясно, что нулевого мудреца гарантированно спасти нельзя – ведь цвет его колпака никто не видит. Докажем, что если можем разбить все 2n последовательностей для n мудрецов (кроме нулевого) на 2 списка по 2n-1 последовательностей со свойствами A и Б, то таким образом можно спасти n мудрецов.

Доказательство.

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

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

Доказательство.

Докажем это утверждение по индукции.

^ База:

См. выше.

Переход:

Предположение индукции:

Можно разбить все 2k последовательностей длины k на 2 списка по 2k-1 последовательностей со свойствами A и Б.

?) Тогда аналогичное разбиение возможно для 2k+1 последовательностей длины k+1.



000

011

101

110

001

010

100

111




0000

0011

0101

0110

_____

1001

1010

1100

1111


0001

0010

0100

0111

_____

1000

1011

1101

1110



В самом деле, возьмём первый список длины n и припишем спереди к каждому числу 0. Затем возьмём второй список и припишем спереди к каждому числу 1. Все получившиеся числа объявим первым списком длины k+1. Затем приписывая, наоборот, к первому списку 1, а ко второму 0, построим второй список длины k+1. Докажем, что полученные списки обладают свойствами А и Б. Во-первых, все полученные последовательности различны, так как у них либо разные «хвосты», либо, если «хвосты» одинаковы, то разные первые цифры (по построению). Во-вторых: две последовательности из одной половины списка отличаются в двух цифрах «хвоста», а две последовательности из разных половин одного списка отличаются первой цифрой (по построению) и хотя бы одной цифрой «хвоста» (по свойству Б).

^ Случай с тремя цветами колпаков.

Зашифруем три цвета как 0,1 и 2. В этом случае у мудрецов будет 3 списка, в каждом по 3n последовательностей. (0-ой мудрец своим ответом будет задавать один из трех списков.) В каждом из этих списков должны выполняться свойства A и Б. Способ построения таких списков аналогичен случаю двух цветов.

Вот списки длины 2 и 3:

00

11

22

01

12

20

21

02

10



000

011

022

101

112

120

221

202

210

100

111

122

201

212

220

021

002

010

200

211

222

001

012

020

121

102

110



^ Комментарий руководителя.

Работа выполнена в 2011 году.

Нетрудно заметить, что (в случае двух цветов) сумма всех единиц в каждом списке имеет одну и ту же чётность. Отсюда следует следующая переформулировка решения: каждый мудрец подсчитывает чётность числа видимых ему чёрных колпаков. Это решение более наглядно, легко понимается и доказывается. У него только один недостаток – до него непросто догадаться самому, если нет соответствующего опыта. Подобный опыт как раз и приобретается в ходе изобретения «длинного» решения со списками, приведённого выше.


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


Выполнил Власенко Дмитрий,

школа-интернат «Интеллектуал», 9 класс

Руководитель: Шноль Дмитрий Эммануилович


Цели этой проектной работы:

Чтобы задать последовательность этого вида, кроме рекуррентной формулы надо задать два её начальных члена a0 и a1 (обычно последовательности определяются для натуральных номеров, но в этом случае удобно её начинать с нулевого члена).

Пока я в основном изучил последовательности, у которых начальные члены a0 = 0 и a1 = 1. Для них:




Пусть последовательность задана формулой . Тогда все члены последовательности , заданной формулой , равны (То есть , а ).

  1. l = –1;

  2. –2 < k < 2.



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

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

Комментарий. Работа выполнена в 2005 году.


ИСТОРИИ


^ Шноль Д.Э.

Задача про «пифагоров кирпич»

В томе «Математика» энциклопедии издательства «Аванта+» я прочел, что до сих пор неизвестно, существует ли «пифагоров кирпич»: прямоугольный параллелепипед с целыми ребрами, диагональю и диагоналями граней. Пример параллелепипеда, у которого нецелые только две диагонали боковых граней, легко найти (ребра 3; 4; 12): 13² = 3² + 4² +12², при этом 3² + 4² = 5². Мне показалось, что было бы интересно поработать с такими параллелепипедами, а также попытаться найти те параллелепипеды, у которых диагональ только одной грани нецелая (мы их назвали «слабыми по одной грани»). В таком виде и была вывешена тема для исследовательской работы в начале года. Сам я в ней не разбирался, так что мог работать наравне с учеником, который ее выберет. К моему удивлению, ее выбрал пятиклассник Алеша Рухович и сумел за год существенно продвинуться. Во-первых, используя формулы для пифагоровых троек, Алеша вывел общую формулу для «пифагорова кирпича, слабого по двум граням». О пифагоровых тройках он сам прочитал в одной из популярных книг, а потом применил их на деле. Сделать это не сложно, но очень важна самостоятельность. Во-вторых, он написал программу, которая нашла несколько примеров «пифагорова кирпича, слабого по одной грани». Мы вместе всматривались в эти примеры, но особых закономерностей не обнаружили. Тогда Алеша снова использовал формулы для пифагоровых троек, получил некоторое уравнение 4-й степени в целых числах, решение которого и дают ответ. Как решить такое уравнение, мы не знали, и, казалось, это был тупик. Тогда Алеша сам предложил попробовать поработать с делимостью. Известно, что во взаимно простых пифагоровых тройках одно число четное, а два других - нечетные. Алеша исследовал, какими могут быть взаимно простые целые числа, задающие ребра «пифагорова кирпича», с точки зрения делимости на степени двойки. Результат оказался довольно интересным: одно число должно быть нечетным, второе - делиться на 4, но не делиться на 8, третье - делиться на 8. На этом закончился первый год исследований, при этом бывали длительные периоды (до месяца), когда исследование «буксовало». Во время работы над темой инициатива того или иного хода решения почти всегда исходила от ученика, я, как правило, выступал только как квалифицированный слушатель. Времени и сил, чтобы самому подробно разбираться в задаче, у меня не было, и это было только к лучшему: Алеша смог получить полное удовольствие от собственных открытий. Работа Алеши была принята к докладу на Колмогоровских чтениях, и он был отмечен как самый молодой участник.


^ Сгибнев А.И.

Две исследовательские работы

Я расскажу о двух работах (или одной, как считать), показательных во многих отношениях. Всё началось с того, что шестиклассник Володя Иванов взял задачу об аликвотах – обыкновенных дробях с числителем 1. Древние египтяне использовали почему-то только такие дроби. Другие дроби представляли в виде сумм аликвот. Сохранился папирус Ахмеса, в котором дроби вида 2/(2n+1) представлялась в виде суммы двух, трёх или четырёх аликвот. Володя задался вопросом: любую ли дробь такого вида («папирусную») можно представить в виде суммы двух аликвот? Оказалось, что любую, да ещё несколькими способами. Всегда присутствует, во-первых, тривиальное разложение(которое мы договорились даже не учитывать), во-вторых, ещё такое: = + (можно проверить тождество непосредственно). Володя искал разложения численно на компьютере, и открыл, что для многих n есть и другие разложения. Этим закончилось первое полугодие, но тут наш коллега Андрей Олегович Белинский подкинул идею посмотреть частоты распределения количеств разложений. Володя обсчитал все дроби с n от 1 до 500. Оказалось, что вполне можно говорить о статистической закономерности: 1, 4, 7, 13 вариантов встречались стабильно больше остальных. Примерно в этот момент я понял, что нашу задачу можно сформулировать так: дано натуральное число h; сколько есть пар натуральных чисел a и b, для которых h является средним гармоническим? Новая формулировка задачи привела, во-первых, к тому, что мы стали исследовать и чётные знаменатели (для них закономерности оказались такие же). Во-вторых, была поставлена серия аналогичных задач: Дано натуральное число r. Сколько существует пар натуральных чисел a, b, для которых r является 1) средним арифметическим? 2) средним геометрическим? 3) средним квадратичным? За эти задачи взялся Миша Пядёркин (6 класс). Но вернёмся к Володе. За следующие полгода (третьи!) мы поняли, что количество вариантов разложения папирусной дроби в сумму двух аликвот однозначно определяется видом разложения её знаменателя на простые множители. Наконец, в четвёртом полугодии я смог по Володиным таблицам и классификациям угадать общую формулу для количества вариантов. Мне хотелось, чтобы Володя на майской школьной конференции доложил этот результат, но сам он никак до формулы не догадывался, а лишать его открытия было нечестно… Он придумал формулу осенью, а чуть раньше, в августе, корейский учитель Kim Young Won, которому я рассказал нашу гипотезу как пример того, на что способна неполная индукция в школьной математике, дал строгий и простой вывод формулы.

Тем временем Миша легко решил задачу о среднем арифметическом. Решение задачи о среднем геометрическом я знал, поэтому подсказал нужную комбинаторную идею. После этого мы на вторые полгода завязли в задаче о среднем арифметическом трёх чисел. Сложность была в том, что при подсчёте троек чисел мы вводили «ограничения» (как называл их Миша), то есть отождествляли все варианты, получаемые друг из друга перестановкой (например, 1+2+3 и 3+2+1 считали за 1 вариант). Поэтому надо было отдельно считать случаи, в которых все три числа различны, в которых два числа совпадают и в которых все три совпадают. Миша проделал всю работу сам с большим энтузиазмом (я только вылавливал ошибки и давал советы). Получились разные ответы для чётных и нечётных r.

В задаче о среднем квадратичном даже двух чисел просветов не было видно. Миша сделал для неё компьютерную таблицу разложений (как Володя когда-то), и на этом мы расстались на лето. В начале осени я посмотрел на таблицу и стал догадываться, что к чему. К сожалению, дальнейшее происходило при весьма слабом участии Миши. Постепенно я опять угадал общую формулу – она оказалась очень похожа по структуре на Володину, но сложнее (так что без подготовки открыть её было бы очень трудно). Потом я научился доказывать, что количество вариантов не меньше, чем утверждает формула. Для этого хватало чисто алгебраической техники: равенство

(a2 + b2)(c2 + d2) = (ac bd)2 + (ad bc)2

порождает два числовых разложения. Однако эта техника принципиально не могла доказать отсутствия других вариантов разложений! Требовался выход задачи в какую-то другую область математики… Задача пролежала три года, но вспомнилась, когда проф. Г.Б. Шабат, консультировавший другого моего ученика, рассказал ему о гауссовых числах – это комплексные числа с целыми действительной и мнимой частями. Эти числа однозначно раскладываются на простые гауссовы числа, исследовав которые, не так уж трудно оказалось доказать угаданные мною формулы. Заодно задача свелась к классической задаче Ферма-Эйлера о сумме квадратов.

Удивительно, что дети могут плодотворно заниматься одной темой по два года и больше! Очевидно, это возможно не с любой задачей, а с задачей, допускающей постепенные продвижения, «вживание» (которого почти никогда не бывает на уроках). А в результате этого «вживания» со временем решаются задачи, к которым вначале совсем не видно подхода. Правда, иногда уже другими детьми…

Стоит отметить и большую роль обсуждения задач с коллегами по ходу решения.


0002860350645698.html
0002981495365872.html
0003192736934987.html
0003325446105048.html
0003381905217704.html