StruniMa

Суми в подчасти

Темата е изготвена със съдействието на:

Суми в подчасти - как да изследваме във СтруниМа

За да изследвате задачите в темата може да влезете в темата за Графи и вериги. Оттук избираме квадратна мрежа.

От горният бутон включваме номерацията на точките, а от двата плъзгача можем да правим квадратни мрежи с различни размери.

За да можем да поставяме точките по началните им места, избираме следния бутон - при изключването на чавката до него, точкте се изместват встрани.

За да можем да преместваме точките от падащото меню вдясно избираме Разместване.

Вдясно от падащото меню можем да изберем Магически правоъгълници (или друга тема по избор).

След нареждане на точките можем да проверим дали сумите по редове и стълбове са равни.

Суми в подчасти - магически квадрати

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

Задача 1. Да се покаже, че за всяко нечетно \(n\) има магически квадрат \(n \times n\).

а) Да се намери магически квадрат \(3 \times 3\) .

Ако разбием квадрата на редове или на стълбове получаваме, че сумата във всеки от тях трябва да е \(45:3=15\). Нека да съберем средния ред, средния стълб и двата главни диагонала. Тъй като сумата на числата по всяко от четирите линии е 15, то сумата им е 60.

Тъй като всяко от 9-те числа участва по веднъж в сумата от 4-те линии с изключение на средното \(e\) (което участва 4 пъти т.е. допълнително 3 пъти), то имаме, че \(1+2+3+4+5+6+7+8+9+3е=60\). Оттук следва, че средното число \(e=5\).

На втора стъпка можем да видим, къде се намира числото 9. Ако то е в някой от ъглите, то трябва да направим сума 6 по три различни начина, но единствените възможности са \(1+5=2+4=6\). Оттук следва, че 9 е по средата на някоя от страните и останалите числа се допълват лесно като спазваме, че сумата по ред,стълб и диагонал е 15.

Суми в подчасти - магически правоъгълници

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

Задача 1.За кои естествени числа \(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:

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

Сумата от числата върху мрежата е \( \displaystyle 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\) колони с равна сума.

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

а) Ако едно от \(m\) и \(n\) се дели на 4.

Нека да подредим числата по големина по дължина на страната, която се дели на 4 - без ограничение на общността да считаме, че това е дължината на правоъгълната мрежа \(m\) (на примера това е страната имаща 8 поставки). След това нека да обърнем всеки втори стълб:

Можем да забележим, че в получената таблица сумите във всички стълбове са равни (това е така, тъй отляво надясно половината от редовете намаляват с 1, а другата половина се увеличава с 1 т.е. не се променя сумата във всеки следващ).

Ако обърнем средните стълбове, които са половината от всички, ще балансираме сумите по редове, а сумите по стълбове не се променят. Това е така, тъй като сумата на средните \( \displaystyle \frac{m}{2}\) четени отгоре надолу се увеличава с \( \displaystyle \frac{m^2}{2}\), а на другите намалява с \( \displaystyle \frac{m^2}{2}\). Това от своя страна е така, тъй като на горната стъпка разликата от сумите между всеки два реда е \( m^2 \), а сумата от средните \( \displaystyle \frac{m}{2}\) се увеличава с точно толкова, колкото сумата на другата половина, от съображение за симетрия.

б) Ако \(m\) и \(n\) дават остатък 2 при деление на 4.

Нека да подредим числата по големина по редове (започвайки отдолу нагоре) и да отделим средните 2 реда. Нека да обърнем всеки втори стълб без да променяме числата в средните 2 реда. Така изравняваме сумите по редове (без средните 2 реда). Още повече сумата им е точно толкова, колкото трябва да е накрая т.е. \( \displaystyle \frac{(m.n+1).m.n}{2} : n = \frac{(m.n+1).m}{2}\).

Тъй като \(n-2\) се дели на 4, то можем да обърнем средните \( \displaystyle \frac{n-2}{2}\) реда, с което изравняваме сумите по стълбове (отново игнорирайки средните 2 реда).

Средната таблица \(m \times 2\) можем да попълним, както в Задача 1., с което сумите по редове стават равни и сумите по стълбове също ставт равни.

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

Задача 4.1 Да се намери магически правоъгълник \(3 \times 5\).

Нека да разположим числата 2,5,8,11,14 във втория ред, а в средния стъпб да бъдат 1,8,15. След това първия ред го допълним с числата, които дават остатък 1 при деление на 3.

Можем да забележим, че сумата на числата в първия ред е с 5 по-малка от тази в средния ред, а тази в третия ред е с 5 по-голяма от тази в средния ред. Тогава ако разменим числата 4 и 9, сумите ще се изравнят.

Задача 4.2 Да се намери магически правоъгълник \(3 \times 7\).

Отново поставяме числата по същия начин, както в задача 4.1 (във всеки ред числата дават равен остатък при деление на 3).

Първият ред има със 7 (страната на мрежата) по-малка сума от необходимата, а последния - със 7 по-голяма. Разменяме числата в първия и шестия стълб, при което се изравняват сумите в редовете.

Задача 4.3 Да се покаже, че ако \(n=2k+1\) е взаимно просто с 3, то има магически правоъгълник \(3 \times (2k+1)\).

Нека да разположим числата по същия начин, като предходните 2 задачи.

Нека да разгледаме с колко се увеличава сумата в първия ред, ако разменим първото и третото число в някой от стълбовете. Ако двете са в централния или наляво от него стълб разликата е от вида \((6k+2)-9r\), където \(r\) е някое от числата \(0,1,2,...,k\). Ако двете числа са в някой от стълбовете вдясно от централния, то разликата е от вида \((3k-4)-9l\), където \(l\) е някое от числата \(0,1,2,...,l-1\).

Тъй като \(2k+1\) не се дели на 3, то \(k \equiv 0,2 \pmod 3\). Оттук \((3k-4)\) и \((6k+2)\) дават остатъци 2 и 5 при деление на 9 (в някакъв ред). С остатъците 2 и 5 могат да се получат всички (без 0) останали с използването на не повече от 4 от тях: \(2+2+5 \equiv 0 \pmod 9\), \(5+5 \equiv 1 \pmod 9\), \(2+5+5 \equiv 3 \pmod 9\), \(2+2 \equiv 4 \pmod 9\), \(5 \equiv 5 \pmod 9\), \(2+2+2 \equiv 5+5+5 \equiv 6 \pmod 9\), \(2+5 \equiv 7 \pmod 9\), \(2+2+2+2 \equiv 2+5+5+5 \equiv 8 \pmod 9\). Ако \(k \geq 8\), то \(4(3k-4) \geq (0+1+2+3).9 + (2k+1)\) и \(4(6k+2) - ((k-3)+(k-2)+(k-1)+k).9 \leq 0\) т.е. ще има комбинация от някои от тези разлики, които ще увеличат сумата в първия ред с точно \( (2k+1) \). Ако \(k < 8\), можем да направим примерите (вече \(3 \times 5\) и \(3 \times 7\) са разгледани). Примери за \(3 \times 11\) и \(3 \times 13\) са

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

Тъй като \(17 \equiv 8 \pmod 9\), то ще са нужни 4 двойки да бъдат разменени. Разликите са \(20-0.9,20-1.9,...,20-7.9\) и \(20-0.9,20-1.9,...,20-7.9\). \(17\) може да се получи като \((20-0.9)+(20-1.9)+(20-2.9)+(20-4.9)=80-7.9=17\).

Задача 4.4 Да се намери магически правоъгълник \(3 \times 9\).

Тук ще забележим, че методът приложен в горните 2 задачи няма да проработи (тъй като трябва да увеличим сумата в първия ред с 9). Нека да наредим 3 магически квадрата \(3 \times 3\) един до друг, като в първия участват числата от 1 до 9, във втория от 10 до 18 и в третия от 19 до 27. Така сумите по редове са равни.

Всеки от квадратите го разбиваме на три блока 1х3, както е показано. Разместваме блоковете така, че във всеки квадрат 3х3 да има един блок от всеки цвят, при което се получава магически правоъгълник, тъй като сумата във всяка колона става 15 + 9 + 18 = 42.

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

Разделяме числата от \(1\) до \(9n\) на три групи - от \(1\) до \(3n\), от \(3n+1\) до \(6n\) и от \(6n+1\) до \(9n\). Разделяме правоъгълника на 3 правоъгълника \(3 \times n\), в които попълваме съответно трите групи от числа така, че да се получат 3 магически правоъгълника (попълваме левия и към него добавяме \(3n\) и \(6n\) към всяко от числата в него, за да получим средния и десния правоъгълник). Така изравняваме сумите по редове.

Разместваме ги както в Задача 4.4 (разместваме ги така, че във всеки правоъгълник да попадне по един блок от всеки цвят), с което изравняваме сумите по стълбове.