Разбиение чисел
Категория реферата: Рефераты по математике
Теги реферата: продукт реферат, конспект
Добавил(а) на сайт: Pechenikov.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Пусть в разбиении некоторая нечётная часть r встречается k раз. Запишем k в виде суммы различных степеней двойки
k = 2a1 + 2a2 + ..., a1 > a2 > ...
и заменим (..., r, r, ..., r, ...) (k раз) на (..., 2a1r, 2a2r, ...). То, что получится, будет разбиением с различными частями.
Например, разбиение (5, 5, 5, 1, 1, 1, 1, 1, 1) соответствует разбиению (10, 5, 4, 2), поскольку число пятёрок равно 3 = 21 + 20, а число единиц равно 6 = 22 + 21.
Упражнения
3. Докажите, что в результате второго преобразования получается разбиение с различными частями.
4. Докажите, что если сначала выполнить преобразование Глэйшера, а затем обратное, то получится исходное разбиение.
Существует другое, не менее интересное и совершенно неожиданное доказательство теоремы Эйлера, принадлежащее американскому математику XIX века Дж. Сильвестру. Вот конструкция Сильвестра: пусть имеется разбиение числа n на нечётные части: (2k1+1, 2k2+1, ..., (2kq+1), где k1 ≥ k2 ≥ ... ≥ kq. На листе клетчатой бумаги в некотором её узле поставим точку x1. Справа от x1, поставим в узлах k1 точек и столько же точек поставим в узлах, расположенных под точкой x1. Затем проделаем то же самое с числом k2, взяв в качестве исходной точку x2, расположенную в следующем за точкой x1 по диагонали направо вниз узле, и т.д., пока не дойдём до числа kq.
Например, разбиению на нечётные части (9, 9, 5, 1, 1) числа 25 будет отвечать картинка, изображённая на рис. 1.
|
Рис. 1. |
|
Рис. 2. |
Она состоит из симметричных относительно диагонали уголков, так что в самом верхнем уголке 2k1+1 точек, в следующем 2k2+1 точек и т.д., а всего точек будет n. Теперь проведём на той же картинке линии так, как показано на рис. 2, подсчитаем количество точек на каждой из этих линий и образуем из полученных таким образом чисел разбиение. Оказывается, все части этого разбиения различны.
Упражнение 5. Докажите это утверждение.
В нашем примере получится разбиение (9, 6, 5, 4, 1). Подумайте, как построить по разбиению на различные части разбиение на нечётные, т.е. восстановить по такому разбиению исходную симметричную картинку.
Отступление: решение задачи М1065
В этом разделе используется более сложная техника, чем в остальной части статьи. При желании вы можете пробежать его, не вникая в детали, и продолжить чтение со следующего раздела. Итак, займёмся решением задачи М1065 из «Задачника «Кванта» (1987, № 9). Напомним её формулировку.
Будем рассматривать векторы (x, y) с целыми неотрицательными координатами, причём хотя бы одна из координат отлична от 0. Назовём такой вектор образующим, если |x–y| = 1.
а) Докажите, что рассматриваемый вектор (x, y) можно представить в виде суммы различных образующих (или он сам — образующий) тогда и только тогда, когда величина k(x, y) = x + y – (x–y)2 неотрицательна.
б) Докажите, что число N(x, y) различных (с точностью до порядка) представлений вектора (x, y) в виде суммы различных образующих зависит только от числа k = k(x, y). Найдите N(13, 18).
Решение задачи начнём с того, что найдём общий вид целочисленных решений неравенства k(x, y) ≥ 0. Числа x+y и x–y имеют одинаковую чётность, поэтому k(x, y) является чётным при любых целых x, y. Следовательно, для любого целого m≥0 достаточно найти целочисленные решения уравнения x + y – (x–y)2 = 2m. Положим x–y = q. Тогда x+y = 2m+q2. Из этих двух равенств немедленно получаем:
|