Задача № 1.  К неравенству Коши-Буняковского                                               

Пусть  где  

1.                   Докажите, что существуют  такие, что С = п – 1.

2.                   Докажите, что величина C не может принимать натуральные значения, меньшие п – 1.

3.                   Попробуйте указать другие натуральные значения, которые величина С принимать не может, а также те натуральные значения, которые она может принимать.

Задача № 2. Обобщение задачи о счастливых билетах.                                    

1.                   Номера билетов в автобусе являются семизначными числами  и могут начинаться с нулей (например, 0000001). Дадим несколько возможных определений понятия «счастливый билет».

а) Номер билета будем называть счастливым, если а₆ + а₅ + а₄ = а₂ + а₁ + а₀.

б) Номер билета будем называть счастливым, если

                          а₆ + а₅ + а₄ + k₁ = а₂ + а₁ + а₀ + k₂, где k₁ и k₂ – цифры и k₁ + k₂ = а₃.

в) Номер билета будем называть счастливым, если

                                 |(а₆ + а₅ + а₄ + k₁) – (а₂ + а₁ + а₀ + k₂)| < t, где  k₁ + k₂ = а₃  и  t = 1…37.

Найти количество счастливых билетов для случаев а), б) и в).

2.                   Номер билета является n-значным числом (n – нечетное). Определив номера счастливых билетов аналогично подпунктам а), б), в) пункта 1 (в пункте в) возьмите t – любое фиксированное натуральное число), найдите количество счастливых билетов.

3.                   Придумайте другие обобщения этой задачи.

Задача № 3.  Сравнение расстояний                                                                             

1.        Четыре точки, лежащие на одной прямой, задают 6 различных отрезков. Докажите, что длина наибольшего из этих отрезков превышает длину наименьшего не менее чем в 3 раза.

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

3.        Обобщите задачи пунктов 1 и 2 на п точек (хотя бы для некоторых значений п).

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

5.        Придумайте и исследуйте другие обобщения этой задачи (например, для точек, принадлежащих другим фигурам, или для точек в пространстве).

Задача № 4.  Задача о многоугольниках, вписанных в многоугольники             

Правильный многоугольник вписан в правильный многоугольник , т.е. все вершины многоугольника лежат на сторонах многоугольника . Докажите, что

1)         если m > n = 3, то m = 4 или m = 6;

2)         если m > n > 3, то m = 2n.

Опишите множество пар чисел (m, n) при условии, что .

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

Задача № 5.  Почти монотонные последовательности                                             

Пусть  и  – две последовательности действительных чисел. Будем писать , если каждое действительное число  встречается в последовательности  не меньшее число раз, чем в последовательности . Если, кроме того, выполнено , то напишем  (в этом случае последовательность  получается из  перестановкой членов).

Докажите (или опровергните) следующие утверждения:

1.       Пусть , где  – последовательность положительных чисел. Тогда:

1. а) для любого конечного набора первых членов последовательности  найдется такой член а_т, что а_т меньше всех а_i,  (i = 1, 2, …, k);

1. б) существует номер , для которого  меньше всех предыдущих членов ;

1. в) существует бесконечно много номеров , для которых  меньше всех предыдущих членов .

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

2.   б)  Пусть, в дополнение к 2. а),  – последовательность положительных чисел такая, что

    и    .

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

3.       Пусть , где  – действительные числа, и  - некоторое число, большее 1. Тогда существует такой номер  (возможно, неединственный), , что:

-          все отношения , , , … ,  не больше ,

-          а любое из отношений , , , … , не меньше .

4.       Пусть  – последовательность действительных чисел, удовлетворяющая условию

  .

Тогда существует такое число , что

  .

5.       Попробуйте в пунктах 1, 2 и 3 сформулировать и доказать более сильные утверждения, а также получить другие, похожие результаты.

Задача № 6.  Виды многочленов                                                          

Рассмотрим квадратные трехчлены (многочлены 2-й степени) с целыми коэффициентами (обозначим множество таких многочленов через Z₂[x]). Будем считать вначале, что старшие коэффициенты всех этих многочленов равны 1 и обозначать такое множество многочленов через

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

0)       Канонический вид:  Ясно, что множество многочленов, представляемых в таком виде и есть

1)       Канонический вид со сдвигом:  Соответствующее множество многочленов обозначим через

2)       Факторизованный вид (разложение на линейные множители):  Соответствующее множество –

3)       Почти факторизованный вид:  Соответствующее множество –

1.    Попробуйте исследовать включение одних из описанных множеств многочленов в другие. Например, очевидно, что  Последнее, в частности, означает, что любой многочлен, представляемый в виде 1), 2) или 3), может быть записан в виде 0). Для некоторых извозможно выполнение равенства

2.    Та же задача, но для случая, когда старший коэффициент не обязательно равен 1, а какому-то целому числу а.

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

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

Задача № 7. Суммы цифр натуральных чисел                                                                

Будем рассматривать числа в 10-й системе счисления. Для каждого натурального числа п определим значение s(п) – сумму цифр всех натуральных чисел от 1 до п включительно.

1.       Найдите такое п, что s(п) = 901.

2.       Докажите, что для всех натуральных т верно равенство s(10^т– 1) = 45·т·10^т-1.

3.        Докажите, что для двузначного числа  имеет место формула:

4.       Найдите аналогичную формулу для трехзначных чисел.

5.       Вычислите σ(2005).

6.       Выведите общую или рекуррентную формулу для σ(),

7.       Предложите свои обобщения этой задачи и исследуйте их.

Задача № 8. Связисты                                                                                  

Два связиста играют в такую игру. Имеется n телефонных узлов. Связисты по очереди делают свои ходы. За один ход каждый из них может соединить кабелем k пар любых узлов. Узлы, которые соединены кабелем, повторно не соединяются. Выигрывает тот связист, после хода которого с любого узла можно будет дозвониться до любого другого (быть может, через несколько промежуточных узлов). Выясните, кто выигрывает при правильной игре – начинающий или его партнер? Рассмотрите другие варианты игры, например:

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

2.        Пусть вначале все узлы попарно соединены кабелем, а связисты убирают по очереди по k соединений. Игрок, нарушивший связь, проигрывает (выигрывает). Кто из игроков выигрывает в этих играх при правильной стратегии?

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

В любом пункте интересно получить определенные результаты хотя бы для отдельных (даже небольших) значений п и k.

Задача № 9. Слоны на шахматной доске                                         

С белого углового поля шахматной доски размера n×m клеток (n > 1; m > 1) начинает двигаться шахматный слон. Дойдя до края доски, слон поворачивает под прямым углом. Попав в угол, он останавливается.

1.       При каких значениях n и m, слон обойдет все белые поля доски?

2.       Сколько всего полей он обойдет на доске n×m (при различных значениях n и m)?

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

Задача № 10.     Обобщение игры в «пятнадцать»                                          

1.    В плоской квадратной коробке 4´4 в некотором порядке размещены 15 одинаковых фишек квадратной формы, одно место (будем называть его клеткой) остается свободным. Фишки пронумерованы числами от 1 до 15 (например, так, как на рис.1а). Не вынимая фишек из коробки, а лишь последовательно передвигая их друг за другом на свободную клетку (движение одной фишки с одной клетки на другую считается одним ходом), нужно разместить их в порядке возрастания номеров так, как на рис. 1б.

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

а) Из каких исходных позиций можно за конечное число ходов перейти в позицию, указанную на рис. 1б? Укажите все позиции, из которых это можно сделать, и все позиции, из которых такой переход невозможен.

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

2.    В плоской квадратной коробке 5´5 с одной вырезанной клеткой в некотором порядке размещены 23 одинаковые фишки, пронумерованные числами от 1 до 23. Необходимо разместить их в порядке возрастания номеров. Исследуйте вопросы, аналогичные вопросам пунктов 1.а) и 1.б) для следующих случаев.

2.1. Вырезана клетка с3 (нумерация клеток, как в п. 1), свободной в конечной позиции должна остаться клетка е1.

2.2. Вырезана клетка е1 (нумерация клеток, как в п. 1), свободной в конечной позиции должна остаться клетка с3.

3.    В плоской квадратной коробке 6´6 с четырьмя вырезанными клетками в некотором порядке размещена 31 фишка. Фишки пронумерованы числами от 1 до 31. Необходимо разместить их в порядке возрастания номеров. Исследуйте вопросы, аналогичные вопросам пунктов 1.а) и 1.б) для следующих случаев.

3.1. Вырезаны клетки с3, с4, d3, d4, свободной в конечной позиции должна остаться клетка f1.

3.2. Вырезаны клетки с3, с4, d4, f1, свободной в конечной позиции должна остаться клетка d3.

4.    Придумайте другие обобщения этой игры и исследуйте их. Например, для случаев коробок размеров n´n, n ³ 7, или с другими вариантами вырезанных клеток.

Задача № 11. Свойства последовательностей из остатков                            

Пусть задан набор  из нулей и единиц  Построим поднаборов  по правилу:                                           (1)

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

1.        Для действительного числа a  и натурального п определим последовательность целых чисел по правилу

                                                                      (2)

где  обозначает остаток от деления a на b. Показать, что для каждого набора существует  такое, что

то есть набор (1) представляет собой двоичную запись числа .

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

3.        Найдите количество циклических наборов  при п = 3 и

4.        Показать, что количество циклических наборов  при п = 4 и  равно 16. Предложите алгоритм (его описание и обоснование), при помощи которого можно было бы решить задачу при .

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

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

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