Квадрат из натуральных чисел

Давайте начнём новый, 2022й год с интересной задачи.

Рассмотрим квадратную таблицу. Попробуем её заполнить натуральными числами так, чтобы суммы чисел во всех строках и всех столбцах были одинаковыми.

Это немного напоминает магические квадраты, но с облегчёнными условиями: числа внутри могут повторяться, а равенство сумм требуется только по строкам и столбцам, не по диагоналям.

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

Но давайте теперь подсчитаем, сколько существует квадратов, сумма всех элементов которых равна наперёд заданному числу N.

Например, для N = 12 таких квадратов тоже 12. Смотрите:

один квадрат из одной ячейки, в которой запишем число 12.

  [12]

пять квадратов из четырёх ячеек, вот такие:

  [1 5] [5 1] [2 4] [4 2] [3 3]

  [5 1] [1 5] [4 2] [2 4] [3 3]

и шесть квадратов из девяти ячеек:

  [1 1 2] [1 1 2] [1 2 1] [1 2 1] [2 1 1] [2 1 1]

  [1 2 1] [2 1 1] [1 1 2] [2 1 1] [1 1 2] [1 2 1]

  [2 1 1] [1 2 1] [2 1 1] [1 1 2] [1 2 1] [1 1 2]

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

А теперь предлагаем вам, уважаемые читатели, выяснить, сколько существует квадратов с указанным свойством, сумма всех чисел в ячейках которых равна 28? Вы, вероятно, догадываетесь, какой будет ответ ;) - тем интереснее будет перечислить их все.

Медиана больше среднего

Важными статистическими свойствами выборки (набора чисел) являются среднее значение и медиана. Они не тождественны. 

Среднее значение - это обычное среднее арифметическое, сумма всех чисел в наборе, разделённая на их количество. 

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

Например, в выборке 1,2,3,5,20 среднее значение равно (1+2+3+5+20)/5 = 5.2, а медиана равна 3.

Теперь рассмотрим, к чему было такое вступление :)

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

Для семёрки таких способов будет 15, вот они:

7 = 1+6 = 2+5 = 3+4 = 1+1+5 = 1+2+4 = 1+3+3 = 2+2+3 = 1+1+1+4 = 1+1+2+3 = 1+2+2+2 = 1+1+1+1+3 = 1+1+1+2+2 = 1+1+1+1+1+2 = 1+1+1+1+1+1+1

Подсчитаем для каждого набора чисел в разбиениях среднее и медиану

(7): среднее 7, медиана 7

(1, 6): среднее 3.5 медиана 3.5

(2, 5): среднее 3.5 медиана 3.5

(3, 4): среднее 3.5 медиана 3.5

(1, 1, 5): среднее 7/3 медиана 1

(1, 2, 4): среднее 7/3, медиана 2

(1, 3, 3): среднее 7/3, медиана 3

(2, 2, 3): среднее 7/3, медиана 2

(1, 1, 1, 4): среднее 1.75, медиана 1

(1, 1, 2, 3): среднее 1.75, медиана 1.5

(1, 2, 2, 2): среднее 1.75, медиана 2

(1, 1, 1, 1, 3): среднее 1.4, медиана 1

(1, 1, 1, 2, 2): среднее 1.4, медиана 1

(1, 1, 1, 1, 1, 2): среднее 7/6, медиана 1

(1, 1, 1, 1, 1, 1, 1): среднее 1, медиана 1

Итак, мы видим, что среди 15 разбиений числа 7 на натуральные слагаемые, всего у двух наборов слагаемых медиана оказалась больше среднего значения. Это наборы (1, 3, 3) и (1, 2, 2, 2).

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

Пентапенни

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

А пентапенни - это конфигурации из пяти одинаковых монет, касающихся друг друга некоторым образом. Пентапенни считаются разными, если их ельзя перевести одна в другую добавлением или разрывом точек касания двух монет.

Всего существует 13 различных пентапенни, пишет Alexandre Muñiz вгруппе Puzzle Fun

Количество разбиений

Берём число 28. Его можно представить в виде суммы нескольких слагаемых довольно большим количеством способов. Например:
28 = 14+14 = 20+5+3 = 10+9+5+1+1+1+1+1=...

А вот интересно, сколько среди этих разбиений будет таких, в которых сумма наибольшего и наименьшего слагаемого будет больше количества слагаемых? Разбиение из единственного числа тоже считается. Порядок слагаемых не играет роли.

Например, для числа 5 таких разбиений будет 4:
5, 4+1, 3+2, 3+1+1

Сумма восьми квадратов

Существует ровно 2016 способов представить число 5 в виде суммы восьми квадратов целых чисел. Почему так много? Давате подсчитаем.

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

5 = 4+1+0+0+0+0+0+0
5=1+1+1+1+1+0+0+0

Теперь учтём перестановку слагаемых. В первом способе место для четвёрки можно выбрать 8-ю способами, и место для единицы - 7-ю способами. Итогог он нам даёт 56 расстановок слагаемых.

Со втором способе места для единиц можно выбрать $C_8^5$ (или, что то же самое, места для нулей можно выбрать $C_8^3$) способами, что составит ещё 56 способов.

Теперь учтём, что 4 может быть квадратом как числа 2, так и числа -2. Аналогично и с единицей: 1=1²=(-1)².

Учёт знака числа, возможимого в квадрат, увеличит число способов для первого представления в 4 раза, а для второго - в 32 раза. Таким образом, итоговый результат равен:
56*4+56*32 = 56*36 = 2016 способов

Количество разных ходов в шахматах

Из начальной позиции в шахматах у белых есть 20 вариантов хода. Столько же возможных ответов есть и у чёрных. Выходит, после первого хода может сложиться 400 разных позиций.

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

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

По аналогии с задачей о выражении числа пи, можно в решениях также учитывать различные условия:
- располагать фигуры по всей доске
- только на своей половине
- тоьлко в крайних двух горизоналях

Вычисление количества сочетаний

Число 10 на математических часах представляется как
$10=C_5^2$

Эта запись означает количество сочетаний из 5 элементов по 2. Иными словами, сколькими способами можно выбрать из пяти различных предметов неупорядоченную пару

Искомое число можно подсчитать непосредственно. Из (1,2,3,4,5) можно выбрать такие пары (не забываем, что порядок в них неважен):

(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)
Всего их 10.

Как же вычислять $C_n^m$ не прибегая к непосредственному перечислению? Первый предмет можно выбрать n способами. Второй предмет можно выбрать (n-1) способами. Для третьего будет (n-2) способов, и т.д. до (n-m+1) способов выбрать m-й предмет.

Значит, количество способов выбрать m предметов из n при условии, что порядок важен, равно произведению $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)$.

Сами же эти m предметов можно переставить между собой m! способами. Значит, каждая непорядоченная группа из m предметов при нашем подсчёте оказалась подсчитанной m! раз.

Поэтому $C_n^m$ оказывается равно дроби: $\frac{n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)}{m!}$

Эту формулу можно упростить, заметив, что $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1) = \frac{n!}{(n-m)!}$

Таким образом, $C_n^m = \frac{n!}{m!(n-m)!}$

Объяснение математических часов: 1 - факториал нуля

На своих математическия часах для обозначения числа 1 я использовал формулу:

$1 = 0!$

1. Факториал нуля.
Символ факториала (n!) обозначает произведение числе от 1 до n. Поэтому часто на математических часах через факториал тройки обозначают шестёрку: $3!=1\cdot 2\cdot 3 = 6$.

Но обозначение факториала можно расширить и на 0, если учесть, что $n!=1\cdot 2\cdot 3 \dots (n-1)\cdot n$ - это количество способов разместить в ряд n разных предметов. Так как 0 предметов можно разместить ровно один способом, то $0! = 1$

В блоге я как-то писал и о том, как можно определить факториал дробного числа.

С факторалом также связаны такие понятия, как факторион, субфакториал и праймориал.

Минимальная суперперестановка

В строке 123412314231243121342132413214321 встречаются все возможные 24 перестановки строки "1234". Эта строка имеет минимально возможную длину.

Аналогичной минимальной строки для всех перестановок пяти цифр "12345" ещё не найдено.

Такие строки называются суперперестановками.

Мат в 549 ходов

Сразу скажу - сначала я посмотрел на дату поста. Но новость об этом появилась ещё 28 марта, так что, скорее всего, это не розыгрыш.

В Москве, в Университете им.Ломоносова составляется полный каталог всех семифигурных окончаний шахматной партии. И в ходе перебора наткнулись вот на такую позицию:



Белые в ней могут привести партию к победе, но чёрные способны оттягивать своё поражение в течение 549 ходов! Интересно, что выигрышная стратегия белых включает превращение пешки в коня, а не в ферзя.

Спасибо большое Илье Весеннему за развитие темы и за ссылку на полное решение.

Субфакториал

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

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

Для трёх предметов будет 2 способа: (2, 3, 1) и (3, 1, 2)

Для четырёх предметов уже выходит целых 9 способов: (2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3), (3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 3, 1, 2), (4, 3, 2, 1).

Обозначается субфакториал восклицательным знаком перед числом.
!4 = 9.

Вычисляется он по формуле:
 

Факториал нуля

Как легко догалались читатели, в софизме-сенсации восклицательный знак является не знаком препинания, а символом факториала.

Для натурального числа n его факториал - это произведение всех натуральных чисел от 1 до n. Например, 5! = 1*2*3*4*5 = 120.

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

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

Всего вариантов расстановки будет 5*4*3*2*1 = 5!

А сколькими способами можно расставить в ряд 0 предметов? Ровно одним - когда мы получаем пустой ряд. Вот поэтому принято, что 0! = 1.

Без одинаковых углов

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

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

Например, самым большим квадратом, который можно раскрасить в два цвета требуемым образом, будет квадрат 4 на 4:



Для трёх цветов наибольшим квадратом будет 10x10 (автор Tom Sirgedas).

Но уже для пяти цветов появляется открытая проблема. Известно решение для квадрата 25 на 25. Известно, что нет решения для квадрата 28 на 28. А вот для промежуточных значений - ведётся поиск. Если раскраска пятью красками квадрата со стороной 27 существует, один из цветов должен располагаться так:

Может быть, у вас получится найти расположение остальных?

Кроме всеобщего признания, участие в конкурсе приносит и эстетическое наслаждение. Взгляните только, какой изумительный ковёр получила Наталия для 11 цветов и N = 121

Страница конкурса
Обсуждение конкурса на русскоязычном математическом форуме

Маршруты шахматного коня

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

Эту задачу успешно решают для всё больших и больших значений n и m мои коллеги Наталия Макарова (также исследовательница магических квадратов) и Алексей Чернов. Результаты представлены в базе данных. Вот, например, один из двух вариантов замкнутого пути по обычной шахматной доске 8 на 8:

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

Домино из шахматной доски

Если из шахматной доски вырезать 2 угловых поля, лежащих на одной диагонали, то её станет невозможно полностью разрезать на "доминошки" 1x2.

Казалось бы, почему невозможно? Ведь остаётся 62 клетки, число чётное, и вполне может быть покрытое 31-й плиткой домино. Однако стоит вспомнить о раскраске. Среди оставшихся полей 30 белых и 32 чёрных. Доминошка же, как её ни располагай, будет всегда вмещать одно чёрное и одно белое поле. Таким образом, после того как вырежем из доски 30 плиток, останутся 2 несвязанные чёрные клетки.

8 ферзей

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