[Kombinatoryka] Numerowanie

[tomix]

Może ktoś poda jakieś wskazówki do rozwiązania tego zadania?

Mamy 2007-kąt foremny. Na każdym wierzchołku jest punkt i na każdym środku boku też jest punkt, (czyli w sumie 4014 punktów). Ponumerować te punkty liczbami naturalnymi od 1 do 4014 tak, żeby na każdym boku (tzn. wierzchołek, środek boku, drugi wierzchołek) suma liczb była wszędzie taka sama. Czy takie ponumerowanie jest możliwe dla każdego n-kąta foremnego, czy tylko dla n = 2007?

[mol_ksiazkowy]

raczej nalezaloby wiec zaczac od n=3 i zobaczyc czy idea umiesczenia liczb 1,2,3...n/2 w srodkach bokow "przejdzie", sorki za niechlujny rysunek

[Sylwek]

Udało mi się dowieść, że dla n nieparzystego powyższa idea (troszkę zmodyfikowana) rzeczywiście działa. Wystarczy umieścić liczby w podanej kolejności (najpierw na wierzchołku, potem w środku boku, potem znów na wierzchołku, ..., na końcu na środku boku):


\(\displaystyle{ 1, \ (2n-1), \ (\frac{n+1}{2}+1), \ (2n-2), \ 2, \ (2n-3), \ (\frac{n+1}{2}+2), \ (2n-4), \ 3, \ \ldots, \ \frac{n-1}{2}, \ 2n}\)

Opisowo: zaczynamy od wierzchołków, jedynkę stawiamy w dowolnym wierzchołku, dwa wierzchołki dalej dwójkę, dwa wierzchołki dalej trójkę ... , w wierzchołku sąsiadującym z jedynką stawiamy \(\displaystyle{ \frac{n+1}{2}}\), dwa wierzchołki dalej \(\displaystyle{ \frac{n+1}{2}+1}\) itd. Wpisywanie w środki boków zacznijmy od środka boku z wpisanymi w wierzchołki \(\displaystyle{ 1, \frac{n+1}{2}}\), wpiszmy tam 2n, a następny środek boku (idąc w tą samą stronę co wpisywanie w wierzchołki) 2n-1 i tak aż dojdziemy do n+1.

Nie trudno pokazać, że suma wzdłuż każdego boku jest taka sama i równa \(\displaystyle{ \frac{5n+3}{2}}\).

Przykład dla n=7 (suma po każdym boku to 19):


Dla kwadratu warunki zadania spełnia np. układ (zaczynając od wierzchołka): \(\displaystyle{ (1,7,5,2,6,3,4,8)}\). Ogólny przypadek dla n parzystego pozostawiam otwarty, z treści zadania ("czy dla każdego n-kąta czy tylko dla n=2007") można się domyśleć, że ponumerowanie jest możliwe dla każdego n-kąta ) .

[_Mithrandir]

A dlaczego numerować kolejno co dwa wierzchołki? Skąd taki pomysł? Skąd wiedziałeś, że tak należy zrobić? Bo niezbyt to rozumiem, a też mam ten problem.

[Sylwek]

Zauważyłem pewną analogię rozpatrując trójkąt, pięciokąt, siedmiokąt i zastosowałem to w przypadku ogólnym dla n nieparzystych.

[_Mithrandir]

No tak. Dzięki Rozumiem, że oglądanie przypadków szczególnych to dobry sposób na rozwiązanie przypadku ogólnego (w geometrii)?

[mikel]

Nie tylko w geometrii.

[mol_ksiazkowy]

Ogólny przypadek dla n parzystego pozostawiam otwarty, z treści zadania ("czy dla każdego n-kąta czy tylko dla n=2007") można się domyśleć, że ponumerowanie jest możliwe dla każdego n-kąta

Sylwku, a czy znasz rozwiazanie dla sześciokąta??

[DoMini1606]

Nie jestem Sylwkiem, ale: dla sześciokąta np. licząc kolejno od wierzchołka: 1,11,5,10,2,12,3,8,6,4,7,9.

Znalazłam także inne rozwiązania dla kwadratu. Licząc kolejno od wierzchołka:
1) 1,6,7,3,4,2,8,5
2) 8,4,3,5,7,2,6,1
3) 4,2,8,5,1,6,7,3
Więcej rozwiązań dla kwadratu nie znalazłam.

Doszłam także do wniosku, że suma liczb na jednym boku mieści się w przedziale \(\displaystyle{ \langle n+5, \frac{1}{k} \left( 1+2+3+...+n+ \left( n+n-1+n-2+...+n-k+1\right) \right) \rangle}\) gdzie n, to liczba punktów, a k to liczba wierzchołków.

[darek20]

tu jest to zadanie, tylko w łatwiejszej formie
http://bundeswettbewerb-mathematik.de/a ... 07_1_e.pdf