Punkty kratowe - środek ciężkości

[PokEmil]

Na płaszczyźnie danych jest \(\displaystyle{ 9}\) różnych punktów kratowych, z których żadne trzy nie są współliniowe. Udowodnij, że pewne trzy z tych punktów są wierzchołkami trójkąta o środku ciężkości w punkcie kratowym.

[Premislav]

Jak masz niewspółliniowe punkty
\(\displaystyle{ \left( x_1, y_1\right), \ \left( x_2, y_2\right), \ \left( x_3, y_3\right)}\) na płaszczyźnie kartezjańskiej, to ich środek ciężkości wypada w punkcie
\(\displaystyle{ \left( \frac{x_1+x_2+x_3}{3}, \ \frac{y_1+y_2+y_3}{3} \right)}\).
(poszczególne współrzędne to średnie arytmetyczne).
Dalej modulo \(\displaystyle{ 3}\) i jakieś proste Dirichlety.-- 30 cze 2019, o 17:57 --Jakbyś sobie nie poradził, to pisz, ale to serio nie jest trudne.

[PokEmil]

Jest to zadanie nr 5 z obozu OMJ na poziomie OM z 2018 roku. W oryginalnym zadaniu jest słabsza teza - mianowicie trzeba wykazać, że spośród \(\displaystyle{ 13}\) różnych punktów istnieją trzy, które tworzą trójkąt o środku ciężkości w punkcie kratowym. Tę łatwiejszą wersję jestem w stanie dowieść:

Spośród \(\displaystyle{ 13}\) różnych punktów z ZSD istnieje \(\displaystyle{ 5}\) punktów o tej samej pierwszej współrzędnej. Spośród tych pięciu punktów, jeśli wśród nich są trzy o takiej samej drugiej współrzędnej, to te trzy punkty tworzą trójkąt o środku ciężkości w punkcie kratowym. Jeśli nie, to oznacza to, że wśród tych pięciu punktów istnieją trzy takie, których druga współrzędna daje różne reszty z dzielenia przez \(\displaystyle{ 3}\) i te trzy punkty tworzą szukany trójkąt.

Jest adnotacja odnośnie do tego zadania, że liczbę \(\displaystyle{ 13}\) można zastąpić \(\displaystyle{ 9}\) i z tą trudniejszą wersją mam problem. Nie za bardzo rozumiem co mam zrobić modulo \(\displaystyle{ 3}\), proszę o dalszą pomoc.

[Premislav]

Sorry, jednak nie doceniłem tego zadania, mój błąd. Z czystego Dirichleta nie umiem tego sklepać, choć pewnie się jakoś da.

Na zbiorze tych dziewięciu punktów kratowych rozważmy relację równoważności \(\displaystyle{ \sim}\) określoną następująco: \(\displaystyle{ (x_1, x_2)\sim(y_1, y_2)\Leftrightarrow \left( x_1\equiv y_1\pmod{3}\wedge x_2\equiv y_2\pmod{3}\right)}\)

Jeżeli któraś z klas abstrakcji tej relacji równoważności ma moc co najmniej \(\displaystyle{ 3}\), to wybieramy pewną taką klasę abstrakcji i dowolne trzy jej elementy spełniają warunki zadania.
Jeżeli każda klasa abstrakcji jest jednoelementowa, to mamy dziewięć klas abstrakcji, każda odpowiada przez naturalne utożsamienie \(\displaystyle{ (a,b)\rightarrow (a\pmod{3}, b\pmod{3})}\) innemu elementowi zbioru \(\displaystyle{ \left\{ 0,1,2\right\} \times \left\{ 0,1,2\right\}}\), więc można wskazać np. element odpowiadający \(\displaystyle{ (0,1)}\) , element odpowiadający \(\displaystyle{ (2,0)}\) i element odpowiadający \(\displaystyle{ (1,2)}\), takie trzy elementy będą spełniały warunki zadania.
Pozostaje przypadek, w którym żadna klasa abstrakcji nie ma co najmniej trzech elementów, a jednocześnie któraś klasa abstrakcji ma więcej niż jeden element. Tutaj niestety wychodzi mi tylko na totalną pałę.
1) cztery klasy dwuelementowe i jedna jednoelementowa: ćwiczenie dla Ciebie.
2) trzy klasy dwuelementowe i trzy jednoelementowe: ćwiczenie dla Ciebie.
3) dwie klasy dwuelementowe i pięć jednoelementowych: ćwiczenie dla Ciebie.
4) jedna klasa dwuelementowa i siedem jednoelementowych:
tutaj sprawa jest o tyle prosta, że brakuje tylko jednego z odpowiedników elementów \(\displaystyle{ \left\{ 0,1,2\right\}\times\left\{ 0,1,2\right\}}\). Wystarczy więc dla dowolnego ustalonego \(\displaystyle{ (i,j)\in\left\{ 0,1,2\right\}\times\left\{ 0,1,2\right\}}\) wskazać trójkę spełniającą warunki zadania, do której nie należy \(\displaystyle{ (i,j)}\). A to jest proste: trójka
\(\displaystyle{ \left( i+1\pmod{3}, j+2\pmod{3}\right), \ \left( i, j+1\pmod{3}\right), \ \left( i+2\pmod{3}, j\right)}\)
składa się z elementów różnych od \(\displaystyle{ (i,j)}\) i jak dodamy elementy tej trójki po współrzędnych modulo \(\displaystyle{ 3}\), to dostaniemy \(\displaystyle{ (0,0)}\).

W każdym razie to rozwiązanie, którego szkic przedstawiłem, jest mocno siłowe i mi się nie podoba. Nie pisałbym tego, ale w sumie niepotrzebnie wypowiedziałem się w tym wątku i nie chciałem go zostawiać potem bez reakcji, gdy się okazało, że jednak nie jest to takie prościutkie.