Разместване на точки - различни разстояния
Нека да разгледаме 4 точки разположени върху окръжност на равни разстояния:
Може ли точките да се разместят така, че всеки две да бъдат на различни разстояния от това, на което са били в началото?
В СтруниМа можем да направим поставки за върховете от следния бутон:
За да номерираме върховете и поставките натискаме бутона "Номерация на точките":
Забелязваме, че както и да разместваме точките върху 4-те поставки всяка от точките ще има поне една съседна точка, която е била нейна съседна и в началното разположение.Това е така тъй като не могат да се намерят 2 "не-съседни" за дадена точка. На примера можем да забележим, че 1-2 и 3-4 са съседни както в началното разположение (гледайки номерацията на поставките) така и в новото:
Може ли 5 точки разположени по окръжност да се разместят така, че всеки две да са на различно разстояние от това, на което са били в началното разположение?
Оказва се, че е възможно. Нека да наредим първо нечетните, след това четните точки по големина. За да проверим можем да натиснем бутона за проверка:
Нека точките са 6. Могат ли да се разместят така, че всеки две да са на различно разстояние от това, на което са били в началото?
Събиране по окръжност a+b на две цели числа с даден брой точки N (в случая са 6) ще наричаме:
- ако a+b дава остатък 1,2,3,4,...,N-1, то резултатът от събирането е самия остатък. Например, при 6 точки 5+8=1 тъй като 13 дава остатък 1 при деление на 6;
- ако a+b дава остатък 0, то резултатът от събирането е N. Например, при 6 точки 4+14=6, тъй като 18 дава остатък 0 при деление на 6;
Виждаме, че за да намерим новото място на някоя точка с номер a, която се измества на b места по часовниковата стрелка е точно резултатът от събирането по окръжност с N точки (изследвайте сами).
Например ако точка 5 се премести с 20 места, то това е равносилно да направи 3 пълни обиколки и да се измести с 2 места (20:6=3 Ост 2). Тъй като 5+2=7, което е повече от 6, за да намерим новото място на точката трябва да извадим броят на местата в една обиколка (6) т.е. новото място на точката е 5+2->7-6=1 място.От друга страна ако извършим събирането 5+20=25 и намерим остатъка, при деление на 6 - 25:6=4 Ост 1 също получаваме, че 1 е новото място на точка 5.
Можем да забележим, че всеки две точки, които се изместят с равен брой места по часовниковата стрелка, ще останат на същото разстояние, на което са били и в началото:
Следователно всяка от точките трябва да се измести с различен брой места по часовниковата стрелка. Ако изместим някоя точка с 6 места, то тя се връща на първоначалното си положение. Това означава, че можем да считаме, че броят на местата, на които може да се измести една точка е 1,2,3,4,5 или 6.
Тогава задачата се превърща в това, можем ли да съберем числата от 1 до 6 с числата от 1 до 6 (всяко с различно), така че след събирането по окръжност да се получат отново числата от 1 до 6. Тъй като 21+21=42 и 21 дават различни остатъци при деление на 6 (0 и 3 съответно), то исканото не е възможно (събирането по окръжност запазва остатъка при деление на броя на точките).
Вярно ли е, че произволен четен брой точки 2n не могат да се разместят така, че всеки две точки да са на различно разстояние от това, на което са били в началото? (Полска национална олимпиада, 1989 година)
Тук можем да разсъждаваме, като примера с 6 точки. Всяка от точките трябва да се измести с различен брой места по часовниковата стрелка - 1, 2, ..., 2n-1, 2n. Тогава 1+2+3+...+2n+1+2+...+(2n-1)+2n=n.(2n+1)+n.(2n+1)=2.n.(2n+1) и 1+2+3+...+2n=n(2.n+1)=2.n.n+n трябва да дават равен остатък при деление на 2n(тъй като събирането по окръжност запазва остатъка при деление на броя на точките - 2n). Но това не е така - първия израз се дели точно на 2n, а втория дава остатък n при деление на 2.n, което означава, че не е възможно да разместим точките по исканото условие.
Може ли 9 точки наредени на равни разстояния по окръжност, да се разместят така, че всеки две да са на различно разстояние от това на което са били в началото?
Има три условия, които заедно образуват необходимо и достатъчно условие точките да могат да се разместят. Нека точка 1 се е изместила с a_1 по часовниковата стрелка, точка 2 с а_2 места и т.н. точка n се е изместила с a_n места по часовниковата стрелка.
1) Всеки две измествания a_i и a_j трябва да са различни т.е. образуват, в някакъв ред, числата от 1 до n. Както вече видяхме ако две точки се изместят на равен брой места по часовниковата стрелка остават на същото разстояние:
2) Новите места на всеки две точки i и j, които се получават като i + a_i и j + a_j трябва да са различни помежду си. Т.е. числата a_i + i образуват, в някакъв ред числата от 1 до n.
3) Никоя точка не трябва да изпревари друга точка с първоначалното им разстояние. Никоя разлика (a_i + i)- (a_j + j) не трябва да е равна на j-i. Тогава a_i + 2.i е различно от a_j + 2.j за всички i и j (при събиране по окръжност).
Можем да разгледаме сумите от квадратите на тези 3 множества от числа (които са пермутации на числата от 1 до n):
Изваждайки втората сума от третата получаваме сума, която се дели на n:
Добре известно е, че:
което винаги се дели на n, когато n е нечетно.
Тогава можем да кажем, че:
Изваждайки първата сума от втората получаваме, че сумата на квадратите на числата от 1 до n се дели на n (условие 1):
Горното е вярно тогава и само тогава, когато n не се дели на 3 (в противен случай само n се дели на 3 и оставащото се дели на n/3, но не и на n).
Тогава, ако броят на точките се дели на 3, то точките не могат да се разместят така, че всеки две да бъдат на различно разстояние от това, на което са били в началото.
Когато n е нечетно и не се дели на 3 можем да изместим точка 1 с 1 място, точка 2 с 2 места, точка 3 с 3 места и т.н. точка n с n места. Очевидно условие 1) е изпълнено. Условие 2) също е изпълнено, тъй като всеки две числа i + i = 2.i и j + j = 2.j са различни (n е нечетно). Условие 3) е изпълнено тъй като за всеки две i и j имаме, че i+2.i=3.i и j+2.j=3.j са различни (тъй като n не се дели на 3).
В обобщение можем да кажем - точките могат да се разместят така, че никои две не остават на същото разстояние, ако n e нечетно число, което не се дели на 3.
Copyright: Mladen Valkov