Задания
Девятого республиканского турнира юных математиков

Обращаем ваше внимание на то, что предлагаемые задачи носят исследовательский характер, поэтому наилучшие обобщения и полные решения неизвестны даже их авторам, поэтому: ·         хотя мы и ждем максимальных Ваших обобщений, но во многих задачах интерес представляют даже отдельные частные случаи; ·         возможно (это допускается и даже приветствуется) вы сможете усилить ряд утверждений, приведенных непосредственно в формулировках задач; ·         возможно (это допускается и даже приветствуется) вы сможете усилить ряд утверждений, приведенных непосредственно в формулировках задач; ·         кроме рассмотрения исходной постановки можно исследовать свои направления, причем совсем необязательно ваши обобщения должны совпадать с предложениями авторов задач; ·         в конце каждого своего исследования обязательно дайте краткое резюме – четко сформулируйте ВАШИ основные достижения (утверждения, примеры, гипотезы), с указанием страниц (и/или пунктов) в работе, где они приведены и доказаны (обоснованы); ·         кроме этого, дайте четкие ссылки на литературу, которую Вы использовали при проведении исследований.

№ 1.   ДВУМЕРНЫЕ ПРОГРЕССИИ                                                    

В таблице m´n клеток (m строк и n столбцов) стоят mn чисел. Назовем такой набор чисел двумерной арифметической прогрессией (Ап²), если числа в каждой строчке и столбце таблицы составляют обычную (одномерную) арифметическую прогрессию (Ап¹). Изучите свойства такой двумерной прогрессии, начиная со следующих вопросов.

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

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

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

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

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

№ 2.   ФИГУРЫ НА ШАХМАТНОЙ ДОСКЕ  

Основная  задача. В любом пункте этой задачи предлагается рассматривать шахматные доски различных размеров (3´3, 4´4, …, 8´8, и т.д.), в том числе прямоугольные.

а) Какое наибольшее количество шахматных королей можно расположить на шахматной доске так, чтобы в исходном положении любой король мог сделать первый ход? Короли не враждуют и могут делать ход в клетку, расположенную рядом с другим королём.

б) Какое наибольшее количество шахматных слонов можно разместить на шахматной доске так, чтобы у каждого в исходном положении была возможность сделать первый ход?

в) Решите аналогичную задачу для шахматных ладей.

г) Решите аналогичную задачу для шахматных коней.

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

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

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

ж) Сформулируйте и исследуйте другие аналогичные или более общие задачи.

№ 3.   СЛАБЫЕ ПРИЗНАКИ ПРАВИЛЬНЫХ ФИГУР

А) Предварительные задачи.

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

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

3.  Верно ли, что если все стороны пятиугольника равны между собой и четыре его диагонали равны между собой, то этот пятиугольник правильный?

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

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

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

5. Обязательно ли тетраэдр правильный, если у него:

а) Пять двугранных углов равны друг другу?

б) Восемь плоских углов равны друг другу?

6. Обязательно ли треугольная пирамиды АВСD правильная, если ее основание АВС – правильный треугольник и три плоских угла при вершине D равны друг другу?

№ 4.   ДОМИНО И ТРИМИНО                                                  

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

Будем выкладывать косточки домино в соответствии со следующими правилами. Начинать можно с любой косточки. Каждую следующую косточку необходимо выкладывать так, чтобы она продолжала уже выложенную цепочку (по принципу «торец в торец») и при этом число на прикладываемой дольке этой косточки было равно числу на соответствующей концевой дольке цепочки. Цепочки из косточек домино, полученные по этим правилам, будем называть правильными разложениями.

1)      Сколько всего косточек домино в указанном наборе?

2)      Какое наибольшее число косточек может быть выложено в соответствии с правилами (будем называть такие расположения косточек максимальными правильными разложениями)?

3)      Попробуйте определить точно или оценить количество правильных разложений (хотя бы для некоторых отдельных значений п, п = 3, 4, 5, …).

Б) Рассмотрите те же вопросы для обобщенного домино, т.е. для домино, косточки которого состоят из трех (или более) долек и имеют вид прямоугольника 1´3 (1´4 и т.п., выкладывать косточки разрешается по описанным выше правилам).

В) Рассмотрим игру «тримино» – аналог игры домино, в которой косточки состоят из трех долек, на которых отмечены цифры от 0 до п, причем в отличие от домино, косточки разрешается прикладывать своим торцом не только к концу цепочки, но и к средней дольке любой из ранее выложенных косточек. Примечание. Здесь возможно рассмотрение двух случаев как двух разных игр: прикладывание с одной стороны косточки или прикладывание с двух сторон косточки.

Г) Попробуйте рассмотреть игру «тримино» с косточками вида:

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

Исследуйте вопросы аналогичные вопросам 1) – 3) в указанных играх и других по вашему усмотрению (при этом дайте точное определение вводимых вами условий или правил игры).

№ 5.   ШУЛЕРЫ-2   (Перестановки карт)                                 

Исходная постановка.

Имеется колода из п карт, сложенных по порядку: 1, 2, 3, …, п. Разрешается взять подряд несколько карт и, не меняя порядка, переставить их в любое место колоды (можно в начало или в конец). Пусть М(п) – наименьшее число таких операций, необходимое для того, чтобы сложить карты в обратном порядке. Докажите, что

а) М(9) £ 5;

б) М(52) £ 27;

в) М(52) ³ 17;

г) М(52) ³ 27.

Найдите или оцените сверху и снизу  М(п) для любого п ³ 3.

Общая постановка.

Пусть в отличие от исходной постановки разрешается переставлять не произвольное число карт, а фиксированное число k карт (заранее определенное).

1.       Пусть М(п, k) – наименьшее число таких операций, необходимое для того, чтобы сложить карты в обратном порядке.

2.       Найдите или оцените значения М(п, k) для различных значений п и k (например, для k =1 и т.п.).

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

Определение. Будем называть расстановки, которые можно получить друг из друга описываемыми операциями, эквивалентными; иначе – неэквивалентными. Множество всех попарно эквивалентных перестановок назовем классом эквивалентных перестановок.

4.       Существуют ли значения п и k, при которых гарантировано найдутся неэквивалентные перестановки карт? Если да, то попробуйте указать (дать какое-нибудь формальное описание) множество перестановок, эквивалентных исходной? Сколько всего классов эквивалентных перестановок (т.е. таких множеств перестановок, что все перестановки, принадлежащие одному множеству эквивалентны между собой, а перестановки, принадлежащие разным множествам – неэквивалентны)?

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

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

№ 6.   ТОЧКИ БРОКАРА В МНОГОУГОЛЬНИКАХ

Пусть - внутренняя точка выпуклого многоугольника  (). Точка  называется точкой Брокара, если  (в этом случае угол  называется углом Брокара).

I.             1. Докажите, что в любом треугольнике существует точка Брокара, причем

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

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

II.     1. Исследуйте вопрос о существовании точек Брокара в многоугольниках (п-угольниках, хотя бы для некоторых значений п, п = 4, 5, 6, …).

2. Найдите какие-нибудь свойства точек Брокара и углов Брокара в многоугольниках.

№ 7.   ГРАФЫ   И   ЦЕПИ                                                          

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

Цепью в графе называется такая последовательность его вершин v_i и ребер e_j

                                   L = (v₁, e₁, v₂, e₂, v₃, ... , v_k),

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

Задача. Задан граф. 1) Определить наименьшее число цепей, на которое можно разбить ребра графа. (Каждое ребро графа должно входить ровно в одну цепь.) 2. Построить это разбиение.

Решить поставленную задачу для частных разбиений, например:

а) все цепи содержат одинаковое количество ребер (возможно небольшое), или все цепи содержат число ребер, не большее некоторого заранее заданного числа;

б) цепи являются простыми, т. е. содержат каждую свою вершину ровно один раз;

в) цепи являются замкнутыми, т. е. циклами;

г) циклы являются простыми;

д) каждая вершина графа содержится не более (не менее), чем  в заданном числе цепей;

е) возможны другие виды цепей, предложенных и рассмотренных Вами.

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

№ 8.  МНОГОЗНАЧНЫЕ ПЕРИОДИЧЕСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ФУНКЦИИ

Пусть R – множество всех действительных чисел. Обозначим через [R²] семейство всех наборов из двух действительных чисел, не зависящих от порядка следования входящих в них чисел. Например, следующие наборы [1, 2] и [2, 1] означают один и тот же элемент в [R²]; наборы [1, 2], [1, 1], [2, 2], [1, –4] – разные элементы в [R²]. Аналогично можно определить семейство [R^п] всех наборов, состоящих из п действительных чисел.

Определение 1. Последовательность (А_п) назовем двузначной последовательностью или 2‑последовательностью, если каждый член последовательности является элементом из [R²], т.е. (А_п) = {А₁, А₂, А₃, … | А_т Î [R²], т = 1, 2, …}.

Аналогично можно определить п-значную последовательность (п-последовательность). В частности, при п = 1 получим обычную числовую последовательность.

Определение 2. Последовательность (а_п) (обычная) называется сечением 2‑последовательности, если для любого п Î N выполнено включение а_п Î А_п, т.е. а_п является одним из двух чисел в наборе А_п.

Определение 3. Набор сечений {(а_п), (b_п)},  называется веером 2-последовательности (А_п), если [а_п, b_п] = А_п для любого п Î N. Веер называется периодическим (постоянным), если (а_п) и (b_п) – периодические (постоянные) последовательности и т.д.

Определение 4. Последовательность (а_п) (а также 2-последовательсноть (А_п)) называется периодической, если существует такое натуральное число T, что при любом п Î N выполняется равенство а_п = а_п+Т (А_п = А_п+Т). При этом число T называется периодом последовательности. Наименьший из возможных периодов последовательности называется основным периодом.

Определение 5. Пусть (А_п) = {(а_п), (b_п)} – некоторая 2-последовательность. С ней можно связать характеристическую 2‑последовательность (Н_n), которая определяется следующим образом:  Н_n = [max {(а_п), (b_п)}, min {(а_п), (b_п)}]  для любого п Î N.

Аналогичные определения можно дать для п-последовательности.

Предлагается задача: изучить свойства периодических 2-последовательностей (n‑последовательностей).

Можно предложить для исследования следующий перечень вопросов:

1) если {(а_п), (b_п)} – периодический (постоянный) веер, то будет ли (А_п) периодической (постоянной) 2-последовательностью?

Исследуя вопрос 1), можно рассмотреть различные ситуации. Например, последовательности веера имеют различные основные периоды.  Если при этом 2-последовательность является периодической, то какова зависимость основного периода (А_п) от основных периодов веера?

2) если (А_п) периодическая последовательность, то будут ли обязательно ли последовательности веера будут периодическими? Если предположить, что утверждение 2) выполняется, то исследовать зависимость периодов веера от периода (А_п).

3) если  характеристическая последовательность (Н_n) периодическая (имеет основной период), то будет периодической (иметь основной период) (А_п)? Если предположить, что утверждение 3) выполняется, то исследовать зависимость периодов (А_п) от периодов (Н_n).

4) если  последовательность (А_п) – периодическая (имеет основной период), то будет периодической (иметь основной период) (Н_n)? Если предположить, что утверждение 4) выполняется, то исследовать зависимость периодов (Н_n) от периодов (А_п).

Предложите соответствующие определения и попробуйте исследовать периодические n‑функции.

№ 9.   МАТЕМАТИКИ  ИГРАЮТ                                             

Исходная задача.

1) Каждому из трех математиков писали на лбу натуральное число, причем одно из этих чисел являлось суммой двух других, и сообщили им об этом. Математик не видит, что написано у него на лбу, но видит, что написано у других. Первый сказал, что не может догадаться, какое число написано у него на лбу. После этого то же самое сказал второй математики, а затем и третий. Тогда первый сказал: «Я знаю, что у меня на лбу написано число 50». Какие числа написаны у двух остальных? (См. журнал «Математика в школе», № 3, 2007 г.)

Сопутствующие задачи. Предлагается рассмотреть ряд вопросов, возникающих вместе с этой задачей. Для начала введем несколько обозначений и понятий. Первого, второго и третьего математиков будем называть А, В и С соответственно, а соответствующие три числа, написанных у них на лбах будем представлять упорядоченной тройкой (a, b, c). Тройку назовем допустимой, если все ее элементы – натуральные числа, и недопустимой в противном случае. Ходом назовем ответ любого из математиков; кругом назовем последовательность трех ходов, соответствующей ответам А, В и С (кругов может быть несколько: первый, второй, третий и т.д.). Тройку назовем разрешимой, если за конечное количество ходов кто-то из математиков сможет догадаться, какое число написано у него на лбу (т.е. ему будет известна вся тройка), в противном случае тройку будем называть неразрешимой. Аналогично определим тройки, разрешимые и(или) неразрешимые за k ходов. Тройку назовем метаразрешимой, если не только какой-то из математиков, но и мы (назовем нас наблюдателями) сможем определить тройку, даже не имея полной информации (например, пункте 1) мы заранее знаем только одно число – 50).

2) Укажите все тройки, разрешимые за один ход (т.е. первым же ответом А).

3) Укажите все тройки, разрешимые за два хода (т.е. первым ответом В).

4) Укажите все тройки, разрешимые за три хода (т.е. первым ответом С).

1.2) Мог ли на четвертом ходу математик А сказать, что у него на лбу написано число 20? Мог ли он сказать (на четвертом ходу), что у него на лбу число 49? Могли бы мы (т.е. наблюдатели) назвать при  этом оставшиеся числа, тройки?

1.3) Может ли математик А узнать свое число, если оно трехзначное? А если четырехзначное?

5) Последние вопросы напрямую связаны с таким: всегда ли разрешимая тройка является метаразрешимой? Если нет, то попробуйте указать условия, при которых разрешимая тройка является метаразрешимой.

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

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

7) А если математики могут по своему усмотрению менять порядок ответов (например, А,В,С,В,А,…, или по другому). Могут они при этом упростить или ускорить игру?

8) Можно ли придумать аналогичную игру для четырех и более математиков?

№ 10.   ТРОТУАРНАЯ ПЛИТКА                                               

Исходная задача. Из плошек разного вида будем складывать квадраты и прямоугольники.
1. Попробуйте из плошек вида (т.е. из прямоугольников 1×2) сложить квадраты размером 4×4, 6×6, 8×8, или прямоугольники 4×5, 4×6, а×b так, чтобы никакие две плошки не образовывали квадрат 2×2? (Здесь а и b – натуральные числа.). Если какие-то фигурки складываются таким образом, то покажите, если – нет, то попробуйте это доказать.
2. Тот же вопрос для плошек вида . Здесь а и b – действительные числа (необязательно натуральные).
3. Единичный квадрат разрезали на две части: квадратик ½×½ и уголок ( и ). Васе дали по a² обоих фигурок. Для каких значений а Вася сможет сложить квадрат a×a так, чтобы никакие две плошки не образовывали единичный квадрат? Аналогичный вопрос для прямоугольника а×b.
4. Аналогичные вопросы для квадратика и уголка других размеров.

Обобщающие задачи
5. Единичный квадрат разрезали на две части S и T. Васе дали по a² плошек вида S и T соответственно, где a – положительное число, квадрат которого натурален. Для каких a Вася может сложить из своих плошек квадрат a×a так, чтобы никакие две фигурки не образовывали единичный квадрат? Разберите следующие случаи (выбор способа и общности разрезания – остается за Вами):
      квадрат разрезали по прямой линии;
      квадрат разрезали по k-звенной ломаной, k > 1;
      квадрат разрезали по кривой, не являющейся ломаной.
6. Вопросы пунктов 3-5 с измененным требованием: ни для какого действительного с, 1 £ c < a (c < b), никакой набор плошек внутри сложенного квадрата или прямоугольника не должны образовывать квадрат с×с. Верно ли, что тогда никакие две плошки не будут образовывать единичный квадрат (т.е. что требование является усиленным)?

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

Замечание. Все фигурки в условиях задач можно как угодно поворачивать.

№ 11. ОПЕРАЦИИ НАД ПАРАМИ МНОЖЕСТВ                   

1)    В упорядоченной паре множеств (А,В) разрешается заменить любое (одно) из множеств А или В множеством А*В, где * – одна из операций: È (объединение множеств), Ç (пересечение), \ (разность в любом порядке, т.е. А\В или В\А), Δ (симметрическая разность). Полученная пара опять преобразуется по указанному правилу и т.д. Можно ли за конечное число шагов поменять А и В местами, т.е. при помощи конечного числа указанных преобразований из пары (А,В) получить пару (В,А)? (На каждом шаге разрешается применять разные операции из числа указанных). Примечачие.  А Δ В = (АÈВ)\(АÇВ).

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

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

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

3) Изучите эти (а может и другие) вопросы для множества упорядоченных пар, построенного с помощью описанных преобразований, исходя не из двух начальных множеств, а, например, из трех (т.е. А, В, С) и более.

№ 12. МНОЖЕСТВА ИЗ КОРНЕЙ И КОЭФФИЦИЕНТОВ

1.       Множество S, , удовлетворяет условию: если числа a и b принадлежат этому множеству S, то многочлен  либо не имеет действительных корней, либо его корни обязательно целые и тоже принадлежат этому множеству S.

а) Приведите пример такого множества S. Может ли такое множество состоять из одного, двух, трех элементов.

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

в) Может ли такое множество S содержать бесконечное множество элементов.

2.       Множество Т, , удовлетворяет условию: если числа a и b принадлежат множеству Т, то многочлен  либо не имеет целых корней, либо его корни целые  и тоже принадлежат этому множеству. Элемент множества Т назовем лишним, если после его удаления из множества Т оно все равно удовлетворяет данному условию. Множество из n элементов, не содержащее лишних, назовем минимальным множеством.

А) Определите значения n, для которых существуют минимальные множества.

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

3.       Множество V, , удовлетворяет условию: если числа a и b принадлежат этому множеству, и если многочлен  имеет действительные корни, то они принадлежат этому множеству. Исследуйте вопросы аналогичные вопросам пунктов 1 и 2 для множества V.

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