Задача на магический квадрат с умножением 3x3

Question

Из собеседования на джуниора, нужно было быстро решить. Я не решил, гугл не помог. Гуглится якобы решенный квадрат, но при проверке произведения там разные.

Возьмем числа от трех до одиннадцати и квадрат 3 на 3 клетки. Есть ли возможность расположить числа в клетки квадрата таким образом, что произведение чисел в строках дает тот же результат, что и произведение чисел в столбцах с теми же номерами? Если можно — расставьте, если нельзя — объясните почему.

Answer 1

При расстановке вручную очевидно, что 7 и 11 должны быть на диагоналях, как простые числа, для которых нет кратных. Подумав, туда же — на диагональ — ставится и 9, потому что иначе троек получается несбалансированное количество. Остается постараться поделить оставшиеся 6 чисел на пары. Не слишком просто, но вполне реально — таких пар с одинаковыми произведениями не так уж много...

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

Ну, а если есть компьютер и 5 минут времени...

int main(int argc, char * argv[])
{
    int x[] = {3,4,5,6,7,8,9,10,11};

    do {
        if (x[0]*x[1]*x[2] != x[0]*x[3]*x[6]) continue;
        if (x[1]*x[4]*x[7] != x[3]*x[4]*x[5]) continue;
        if (x[2]*x[5]*x[8] != x[6]*x[7]*x[8]) continue;

        for(int i = 0; i < 9; ++i)
        {
            cout << setw(3) << x[i];
            if (i%3 == 2) cout << "\n";
        }
        cout << "\n\n";

        break;

    } while(next_permutation(x,x+9));

}

https://ideone.com/SB9mzb

Answer 2

разложим все числа на простые множители

3, 4, 5, 6, 7, 8, 9, 10, 11

получим

2^7, 3^4, 5^2, 7, 11

понятно, что 7 и 11 не могут быть в одном ряду или строке по основной теореме арифметики, значит они должны относится к разным строкам и находиться в центре строки/столбца

тройки у нас в в виде 9ки, 3, 6, значит 9ка тоже должна принадлежать строке и столбцу

9ку нельзя ставить в один ряд/столбце с 7 и 11 потому что иначе не хватит троек

итого получаем 7,11,9 находятся на диагонали

[ 7  *  8 ]
[ * 11  * ]
[ *  *  9 ]

вариант не единственный, возможны отражения, повороты и перемещение 7, 11, 9 по диагонали

если записать в общем виде:

[ 7  a  b ]
[ c 11  e ]
[ d  f  g ]

получаем отношение

a/c = d/b = e/f

исходя из этого соотношения подбираются оставшиеся числа

P.S.

итак главное - это 7, 11 и соотношение a/c = d/b = e/f из которого следует, что 3е число в диагонали это 9ка

из соотношения также следует, что отношение кол-ва 2ек (простых множителей) должно быть одинаковым, а поскольку двоек всего 7 штук, и они разбиты на группы 1 (6, 10), 2 (4), 3 (8), то возможны варианты:

3 - 1 = 2 - 0 = 2 - 0 (деление - это вычитание степеней)

и ВСЕ!!!

аналогично можно сделать с пятерками 1 (5, 10):

1 - 1 = 0 - 0 = 0 - 0

и тройками 1 (3, 6) (9ка стоит в диагонали)

1 - 1 = 0 - 0 = 0 - 0

таким образом ОДНОЗНАЧНО мы получаем отношение a/c = d/b = e/f = 2

исходя их этого дальше очень легко собрать всевозможные комбинации, удовлетворяющие условию!!!

Например

[ 7   4  6 ]
[ 8  11  5 ]
[ 3  10  9 ]

P.P.S.

по хорошему задача

[ X  a  b ]
[ c  Y  e ]
[ d  f  Z ]

решается исключительно через основную теорему арифметики и соотношение:

a/c = d/b = e/f

поскольку у нас есть числа, которые содержат простые множители

2^7, 3^4, 5^2, 7, 11

из соотношения сразу 7,9,11 уходят в диагональные элементы, поскольку с ними соотношения не будут соблюдаться, а при анализе остальных чисел получаем, что соотношение равно строго 2, откуда следует

7, 9, 11 должны находиться на диагонали матрицы
5 и 10 должны находиться в одной строке-столбце
3 и 6 должны также находиться в одной строке-столбце

БЛОГ НА HUSL

Задача на магический квадрат с умножением 3x3

Ответы (2 шт):