StruniMa

Разместване на точки - суми в подчасти

Дадена е квадратна мрежа от поставки \(m \times n\). Ако за дадени \(m\) и \(n\) можем да поставим числата от \(1\) до \(mn\), така че сумите по редове да са равни помежду си и по стълбове да са равни помежду си, то ще наричаме полученото магически правоъгълник.

За кои естествени числа \(n\) съществува магически правоъгълник \(2 \times n\)?

При \(2 \times 2\) сумите по редове и стълбове са равни на \(\frac{1+2+3+4}{2} = \frac{10}{2} = 5\). Но така например \(1\) ще трябва да се комбинира с \(4\) и по ред и стълб, но не можем да повтаряме числа. Тук нямаме решение.

При \(2 \times 3\) сумата на числата е \(1+2+3+4+5+6=21\). За всеки магически правоъгълник, трябва общата сума на числата да се дели както на броя редове, така и на броя стълбове. Тук \(21\) не се дели на \(2\) (броят редове), следователно няма магически правоъгълник \(2 \times 3\).

Горното можем да обобщим за произволно нечетно \(n\) - тогава сумата на числата е \(1+2+...+2n=(2n+1)n\), което не може да се раздели целочислено на \(2\), т.е. не могат да се изравнят двата реда.

Ще покажем, че за мрежа \(2 \times 2k\), когато \(n=2k\) е четно можем да попълним числата така, че сумите по редове да са равни и сумите по стълбове са равни. Ако \(k\) е четно, то можем да разделим малките (от 1 до 2k) и големите (2k+1 до 4k) на двойки, като е показано:

т.е. имаме по k двойки със сума 2k+1 и k двойки със сума 6k+1 и в двата реда.

Когато n е четно и k е нечетно, то можем да разделим малките (от 1 до 2k) и големите (2k+1 до 4k) на двойки, но разликата горния иолния ред е 4k.

Размяната на втория и последната колона увеличава долния ред с 2k и намалява горния с 2k:

Да се докаже, че ако m и n са от различна четност, то не съществува магически правоъгълник \(m \times n\).

Сумата от числата върху мрежата е \(1+2+3+...+m.n=\frac{(m.n+1).m.n}{2}\). Нека без ограничение на общността \(n\) е четното число от двете. Нека \(2^k\) е най-голямата степен на \(2\), което дели \(n\). Тъй като \(m.n+1\) и \(m\) са нечетни, то най-голямата степен на \(2\), която дели горната сума идва от \(\frac{n}{2}\) и тя е \(2^{k-1}\). Тогава няма как \(n\) да дели горната сума т.е. не може числата да се разположат в \(n\) колони с равна сума.