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 на Международната Олимпиада по Математика.