Магические квадраты с произведением

 О магических квадратах известно, наверное, всё. А возможны ли магические квадраты, в которых равны не суммы значений в строках, столбцах и на диагоналях, а их произведения? Оказывается – возможны. В дальнейшем буду называть такие квадраты «магическими квадратами с произведением» (сокращённо – МКП).

Интересно, что, как и «обычных» магических квадратов, возможно бесчисленное множество вариантов МКП. В общем случае для трёх чисел a, b и n МКП размером 3 × 3 имеют вид:

При этом a ≠ b, a ≠ 1, b ≠ 1, a ≠ b², b ≠ a²,

Интересно, что любой МКП размером 3 × 3 может быть основой для формирования бóльших МКП. Одно из возможных решений заключается в том, чтобы поместить такой  квадрат в центр квадрата 5 × 5 и потом подобрать такие остальные числа, чтобы они соответствовали свойствам МКП. Это означает, что МКП являются также так называемыми «рамочными магическими квадратами» – магическими квадратами, которые сохраняют свое магическое свойство, если в них отбросить окаймляющие «полосы» в две клетки.

После комментариев  @miksoft я удалю сей свой пост

Из истории двоичной системы счисления. Мнение Эдуарда Люкá
Во многих источниках можно найти информацию о том, что современная двоичная система была впервые описана великим немецким ученым Готфридом Вильгельмом Лейбницем в 1703 году в работе «Explication de l’Arithmétique Binaire…» [1]. Однако это не совсем так. Двоичную систему описывали и до Лейбница. В качестве примера можно привести работы англичанина Томаса Харриота [2] и испанца Хуана Карамюэля [3]. Но в глазах этих и других учёных XVII–XIX вв., писавших о двоичной системе счисления, эта система явно не представляла практического значения (например, для производства вычислений). И только в конце XIX века французский математик Эдуард Люкá первым оценил её возможности, написав в своей книге «Занимательная математика» [4]: «…эта система [двоичная] лучше всякой другой годилась бы для устройства арифметической машины…».

Литература

1. Leibnitz, Godefroy-Guillaume. Explication de l’Arithmétique Binaire… // Mémoires de mathématique et de physique de l’Académie royale des sciences, Académie royale des sciences, 1703.

2. Златопольский Д.М., Шилов В.В. Из истории двоичной системы счисления. Томас Харриот // Информатика в школе, 2020, № 6.

3. Златопольский Д.М., Шилов В.В. Из истории двоичной системы счисления. Хуан Карамюэль // Информатика в школе, 2020, № 8.

4. Édouard Lucas. Récréations mathématiques. Paris. 1882.

Ещё раз о количестве способов набрать сдачу в n рублей из заданного набора монет/купюр

 Вот известная задача: «Имеется неограниченное количество монет достоинством 1, 2, 5 и 10 рублей. Определить, сколькими способами можно ими выдать сдачу в n рублей».

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

Возможно, эта идея будет полезна в других задачах.

Итак.

При n = 7 все варианты следующие:

1 + 1 + 1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 2

1 + 1 + 1 + 2 + 2

1 + 2 + 2 + 2

1 + 1 + 5

2 + 5

 Среди них можно выделить те, в которых минимальным слагаемым является 1. Их – 5. В оставшемся шестом варианте минимальным слагаемым является 2. Вариантов, в которых минимальным слагаемым является 5 и 10, в данном случае нет.

При n = 10 все варианты следующие (без знака +):

1111111111, 111111112, 11111122, 1111222, 112222, 111115, 11125, 1225, 22222, 55, 10,

то есть

количество вариантов с минимальным слагаемым 1 равно 8;

количество вариантов с минимальным слагаемым 2 равно 1;

количество вариантов с минимальным слагаемым 5 равно 1;

количество вариантов с минимальным слагаемым 10 равно 1.

 Подумав (😊), можем сказать, что при n = 11:

· количество вариантов с минимальным слагаемым 1 будет таким же, как общее число всех вариантов для n = 10 (так как разность 11 – 10 не превышает 1);

· количество вариантов с минимальным слагаемым 2 будет равно сумме количеств с минимальными слагаемыми 2, 5 и 10 для n = 9 (так как разность 11 – 9 не превышает 2);

· количество вариантов с минимальным слагаемым 5 будет равно сумме количеств с минимальными слагаемыми 5 и 10 для n = 6  (так как разность 11 – 6 не превышает 5);

· количество вариантов с минимальным слагаемым 10 будет равно такому же количеству для n = 1 (так как разность 11 – 1 не превышает 10).

 Приведённые рекуррентные зависимости применимы для всех значений n, но с некоторыми исключениями – при n = 1 количество вариантов с минимальным слагаемым 1, при n = 2 количество вариантов с минимальным слагаемым 2, при n = 5 количество вариантов с минимальным слагаемым 5 и при n = 10 количество вариантов с минимальным слагаемым 10 будет равно 1 (в перечисленных случаях соответствующие слагаемые появляются впервые).

Допустим, что максимальное значение n равно 99.

В программе, реализующей описанную идею для такого случая, можно использовать двумерный массив из 109 строк и пяти столбцов (10 начальных строк массива являются условными для рекуррентного расчёта значений при n = 1..99).

Вся программа на так называемом «школьном алгоритмическом языке» (система программирования КуМир):

алг
нач цел таб м[-9:99, 1:5], цел n, j
  | Нули, в том числе в фиктивных строках   

нц для n от -9 до 99
    нц для j от 1 до 5
      м[n, j] := 0
    кц
  кц

  | Расчёты
  нц для n от 1 до 99
    если n = 1
      то
        м[n, 1] := 1
      иначе | Рекуррентная зависимость
        м[n, 1] := м[n - 1, 5]
    все
    если n = 2
      то
        м[n, 2] := 1       иначе
        м[n, 2] := м[n - 2, 2] + м[n - 2, 3] + м[n - 2, 4]
    все
    если n = 5
      то
        м[n, 3] := 1
      иначе
        м[n, 3] := м[n - 5, 3] + м[n - 5, 4]
    все
    если n = 10
      то
        м[n, 4] := 1
      иначе
        м[n, 4] := м[n - 10, 4]
    все
    | Последний столбец
    м[n, 5] := м[n, 1] + м[n, 2] + м[n, 3] + м[n, 4]    
  кц
  | Вывод всех значений
  нц для n от 1 до 99
    вывод нс, n, " | ", м[n, 5]
  кц
кон

 Конечно, вместо массива из 109 строк можно использовать 10-строковый массив и после расчёта значений для очередной строки переписать массив, отбросив «хвостовую» строку.

 Спасибо.