Темы (задачи) для научных исследований по математике (стр. 4 )

Или по другому:

А. Задача о неплотной расстановке пентамино

а) На клетчатой доске 6´6 вдоль линий клеток расставляются фигурки вида буквы Т (см. рис.) так, чтобы они не накладывались друг на друга (касаться углами или сторонами фигурки могут, а также их можно поворачивать на 90°, 180° или 270°). Расстановку фигурок назовем плохой, если на доску нельзя поставить никакой новой фигурки без нарушения указанных условий. Каким наименьшим количеством фигурок можно добиться плохой их расстановки?

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

в) Исследуйте общую задачу о максимально неплотной расстановке фигурок типа «пентамино» на прямоугольных досках m × n (оцените количественные характеристики таких упаковок, возможные методы и алгоритмы упаковок и т. п.).

г) Два игрока играют на доске m × n по следующим правилам: каждый из них по очереди выставляет, если возможно на доску пентамино. Кто выигрывает при правильной игре – начинающий или его соперник? Исследуйте игру при различных занчениях m и n.

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

Ответы для первых двух пунктов: а) Тремя фигурами. б) Тремя фигурами.

18. Необычные представления натуральных чисел (а может: «Необычная система счисления – позиционная или нет?!»)

□  Докажите, что любое натуральное число представимо в виде суммы одного или нескольких слагаемых вида 2s3t, где s и t – целые неотрицательные числа, причем среди слагаемых нет таких, что одно делит другое. К примеру: 23 = 9 + 8 + 6.

□  Можно ли 2 и 3 в таком представлении заменить на какие-нибудь другие числа, если условие представления любого натурального числа заменить на условие: «начиная с некоторого места».

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

19. Необычные деления – 1

(ВсМО-144) Докажите, что для любого натурального п найдется число, составленное из цифр 1 и 2, делящееся на 2п.

20. Необычные деления – 2

(ВсМО-329) а) Пусть т и п – натуральные числа. Докажите, что если для некоторых неотрицательных целых чисел k1, k2, …, kп число делится на , то п ³ т.

21. Неравные кучки

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

а) При игре в 16 камней начинающий сделал ход 5+11. Покажите, как теперь второй игрок сможет победить.

б) При игре в 16 камней начинающий сделал ход 5+11. Приведите пример (неудачного) хода второго игрока, после которого он проиграет.

в) Кто победит при игре в 7 камней, 11 камней, 16 камней?

г) Кто победит при игре в камней?

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

е) Предложите свои обобщения.

22. Посадим всех!

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

1. Решить задачу для .

2. Решить задачу для .

3. Решить задачу для .

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

5. Ещё раз пронумеруем стулья следующим образом: . Решите пункты 1-4, если номер кандидата не должен совпадать ни с каким номером стула.

23. Интересная последовательность

Пусть — сумма цифр натурального числа . Положим , и так далее.

1. Найдите все такие , для которых найдется натуральное число , что для всех натуральных .

2. Найдите все такие , для которых найдется натуральное число , что для всех натуральных .

3. Найдите все такие , для которых найдется натуральное число , что последовательность периодическая для натуральных .

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

5. Предложите свои обобщения задачи.

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

1. Покрытия и точные покрытия (тайлинги) на плоскости

Пусть A – матрица размера m на n, каждый элемент которой – целое неотрицательное число. Назовём тайлом (tile) сплошную прямоугольную подматрицу A, другими словами прямоугольник на плоскости, на которой нарисована A. Весом тайла назовём сумму его элементов. Пусть задано некоторое целое положительное число b. Тайлингом} A называется множество непересекающихся тайлов, которые покрывают все элементы A и вес каждого из которых не превосходит b. Покрытием (cover) матрицы A называется множество тайлов (уже, возможно, пересекающихся), которые покрывают все элементы A и вес каждого из которых не превосходит b. Нас будут интересовать оптимальные тайлинг и покрытие, то есть тайлинг и покрытие, имеющие наименьший размер (наименьшее количество тайлов среди всех допустимых).

Для заданной матрицы A и числа b обозначим размер оптимального тайлинга t(A, b), оптимального покрытия – c(A, b). Очевидно, что t(A, b) ≤ c(A, b). Попробуйте выяснить что-либо об обратном соотношении t(A, b) ≤ d · c(A, b) для некоторого d. Приведите пример, когда t(A, b) ≤ f · c(A, b) для как можно большего f – это даст нижнюю оценку на d. Попробуйте найти способ по заданному оптимальному покрытию строить небольшой (отличающийся в константу раз по размеру) тайлинг – это даст верхнюю оценку на d. Какое наибольшее число тайлов может покрывать элемент A в оптимальном покрытии? Приведите нижние и верхние оценки.

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

2. Соотношения между ω и χ

Пусть I = {I1, …, In} – некоторое конечное множество отрезков на прямой. Построим граф пересечений (intersection graph) этого множества следующим образом: вершинами графа G являются элементы I, две вершины смежна тогда и только тогда, когда соответствующие им отрезки пересекаются. Кликой (clique) графа называется множество попарно смежных его вершин. Число вершин в наибольшей клике графа G обозначается ω(G). Хроматическим числом (chromatic number) графа называется наименьшее число цветов, в которые можно раскрасить вершины графа таким образом, чтобы никакие две вершины одного цвета не были смежны. Хроматическое число графа G обозначается как χ(G).