StruniMa

Разместване на точки - съседни разлики

Може ли точките номерирани от 1 до \(n^2\) да се разместят върху квадратна мрежа, така че всеки две съседни по мрежата се различават не повече от \(n\).

Лесно се намира пример, като разположим точките последователно по диагонали (или по редове):

В СтруниМа можем да проверим това с бутона :

Може ли точките номерирани от 1 до 25 да се разместят така върху квадратна мрежа 5х5, че разликата на всеки две съседни е не повече от 3?

Не. Нека разстояние между две поставени точки е броят на минималния брой стъпки по мрежата, които са нужни да стигнем от едната до другата точка. Например, тук разстоянието между A и B е 5, между A и C е 4 и между B и C е 2:

Тъй като абсолютната разлика на две съседни числа е не повече от 3, то \(|A-B|\leq 5.3=15\) и \(|A-C|\leq 4.3=12\) т.е. разликата на две точки на разстояние \(k\) не може да е повече от \(3k\):

Къде могат да бъдат точките 1 и 25? Тъй като 25-1=24, то те трябва да са на разстояние поне 8 стъпки. Това е възможно само ако двете точки са в противоположни ъгли на мрежата.

Нека да разгледаме двата пътя с дължина 8. Има точно един възможен начин да разположим точки по 2-та пътя, така че разликата на всеки две съседни точки не надвишава 3. Това са числата 1,4,7,10,13,16,19,22,25, но не можем да ги използваме по повече от веднъж.

Може ли точките номерирани от 1 до 25 да се разместят така върху квадратна мрежа 5х5, че разликата на всеки две съседни е не повече от 4?

Отново не е възможно. Нека да започнем да поставяме последователно точките 1,2,3 и т.н., така че разликите между съседните точки остават не повече от 4.

Да забележим, че ако достигнем до момент, при който сме поставили числата от 1 до \(m\), така че да имат повече от 4 съседни до тях, то ще има разлика, която е поне 5. Това е така, тъй като на някое от оранжевите числа ще трябва да поставим число, което е поне \(m+5\) - изваждайки от него, което и да е от 1 до \(m\) ще получим разлика, която е поне 5.

Продължаваме да поставяме точките докато не достигнем до точка \(k\) и във всеки ред и във всеки стълб на мрежата не се появи поне една поставена точка:

Има три възможности за разположението на точката \(k\) (на примера това е точка 12)- при премахването и, се освобождава се точно един стълб, точно един ред или едновременно реда и стълба, в която е точката. На примера сме в първи случай.

След премахването и имаме поне една поставена точка и поне една свободна позиция на всеки от редовете. Така можем да намерим 5 различни съседни празни поставки до точките от 1 до \(k-1\):

Аналогично можем да разсъждаваме и ако след премахването на точката \(k\) остава празен ред и във всички стълбове имаме поне една поставена точка.

Остана третият случай, при който след премахването на точката \(k\) се освобождава един ред и един стълб. Тогава, ако оставим точката \(k\), то отново сме в положение при, което във всеки стълб (ред) има поне по една поставена точка и поне една празна поставка - т.е. имаме поне 5 празни поставки до вече поставените точки от 1 до \(k\).

Това означава, че както и да поставяме точките ще има разлика, която е поне 5. Можем да разсъждаваме по същия начин за произволна дъска \(n\) x \(n\) и се оказва, че както и да разместваме числата по мрежата, то ще се появи разлика, която е поне n. Това е известна задача, появила се в Shortlist на Международната Олимпиада по Математика.