Punkty a proste

[mol_ksiazkowy]

Wyznaczyć \(\displaystyle{ f(n)}\) tj. minimalną liczbą punktów na płaszczyźnie, takich ze istnieje dla \(\displaystyle{ k=1,..,n}\) prosta do której należy dokładnie \(\displaystyle{ k}\) z tych punktów.

[Peter_85]

Jeśli dobrze rozumiem treść zadania, to:

- dla \(\displaystyle{ n=1}\) lub \(\displaystyle{ n=2}\): \(\displaystyle{ f(n)=n}\)

Oczywiście dla dowolnie wybranego punktu płaszczyzny istnieje prosta, która przez niego przechodzi. Również dla dowolnych 2 punktów istnieją zarówno takie proste, które przechodzą przez dokładnie 1 z nich, jak i taka, która przechodzi przez oba te punkty.

- dla \(\displaystyle{ n>2}\) taka liczba nie istnieje

Dla dowolnego \(\displaystyle{ n \ge 3}\) wybierzmy \(\displaystyle{ n}\) punktów na płaszczyźnie tak, żeby były wierzchołkami n-kąta foremnego. Wówczas nie istnieje prosta, która przechodziłaby przez dokładnie 3 z tych punktów, a tym bardziej przez większą ich liczbę.

[a4karo]

Pytanie jest o to, czy istnieje taka konfiguracja.

[Peter_85]

W takim razie \(\displaystyle{ f\left(n \right) =n}\) dla \(\displaystyle{ n=1,2}\) i \(\displaystyle{ f\left( n\right) = \frac{n^{2}-3n+8}{2} }\) dla \(\displaystyle{ n \ge 3}\).

Szkic rozumowania dla \(\displaystyle{ n \ge 3}\): jedna z prostych ma przechodzić przez dokładnie \(\displaystyle{ n}\) punktów, więc zaczynamy od \(\displaystyle{ n}\) współliniowych punktów. Od razu widać, że musimy uzupełnić tę wstępną konfigurację o dodatkowy punkt, który nie leży na tej samej prostej, co poprzednie, aby dokonstruować wymagane proste przechodzące przez dokładnie \(\displaystyle{ 1, 2, \ldots , n-1}\) punktów. Niech \(\displaystyle{ p _{0}}\) będzie punktem leżącym poza "główną" prostą zawierającą dokładnie \(\displaystyle{ n}\) punktów, a \(\displaystyle{ p_{1}, \ldots , p_{n} }\) - punktami leżącymi na tej prostej. Idea konstrukcji pozostałych \(\displaystyle{ \left( n-1\right) }\) prostych jest następująca: prosta przechodząca przez dokładnie 1 punkt to prosta równoległa do "głównej" prostej przechodząca przez punkt \(\displaystyle{ p_{0}}\), natomiast prosta przechodząca przez dokładnie \(\displaystyle{ k}\) punktów (dla \(\displaystyle{ k=2, \ldots, n-1}\)) przechodzi przez punkty \(\displaystyle{ p_{0}}\), \(\displaystyle{ p_{k-1}}\), i pozostałe \(\displaystyle{ \left( k-2\right) }\) punktów, o które należy uzupełnić dotychczasową konfigurację. Łączna liczba wymaganych punktów jest więc sumą \(\displaystyle{ \left( n+1\right) }\) pierwotnych punktów i liczby punktów brakujących dla każdej z \(\displaystyle{ \left(n-2 \right) }\) prostych, i wynosi:

\(\displaystyle{ f\left(n \right)=\left(n+1 \right) +\left(0+1+\ldots+n-3 \right) = n+1+ \frac{\left( n-3\right)\left( n-2\right) }{2} = \frac{n^{2}-3n+8}{2}}\) dla \(\displaystyle{ n \ge 3}\). Dla \(\displaystyle{ n=1,2}\) mamy oczywiście \(\displaystyle{ f\left(n \right)=n}\).

[a4karo]

W takim razie \(\displaystyle{ f\left(n \right) =n}\) dla \(\displaystyle{ n=1,2}\) i \(\displaystyle{ f\left( n\right) = \frac{n^{2}-3n+8}{2} }\) dla \(\displaystyle{ n \ge 3}\).

To jest tylko oszacowanie:
Konfigurację dla `n=5` mamy `f(5)=9`

punkty_1.jpg (29.42 KiB) Przejrzano 199 razy

można rozszerzyć do konfiguracji dla `n=6' dodając jedynie trzy punkty

punkty_2.jpg (28.51 KiB) Przejrzano 199 razy

a więc \(\displaystyle{ f(6)=12<\frac{6^2-3\cdot 6+8}{2}=13}\)

[Dasio11]

Odpowiedzią jest liczba \(\displaystyle{ f(n) = n + (n-2) + (n-4) + \ldots}\) (suma kończy się na ostatniej liczbie dodatniej).

Dowód: weźmy dowolny podzbiór płaszczyzny \(\displaystyle{ X}\) o żądanej własności. Dla \(\displaystyle{ k = 1, \ldots, n}\) niech \(\displaystyle{ \ell_k}\) oznacza prostą spełniającą \(\displaystyle{ |X \cap \ell_k| = k}\) i niech \(\displaystyle{ X_k = X \cap \ell_k}\). Oczywiście \(\displaystyle{ |\ell_i \cap \ell_j| \le 1}\) dla \(\displaystyle{ i \neq j}\), tym bardziej \(\displaystyle{ |X_i \cap X_j| \le 1}\). Wykażę indukcyjnie, że \(\displaystyle{ |X_n \cup \ldots \cup X_{n-k}| \ge n + (n-2) + \ldots + (n-2k)}\) dla \(\displaystyle{ 0 \le k \le n}\).

Dla \(\displaystyle{ k = 0}\) teza jest oczywista. Ustalmy \(\displaystyle{ k \ge 1}\), takie że teza jest prawdziwa dla \(\displaystyle{ k-1}\). Wtedy

\(\displaystyle{ |X_n \cup \ldots \cup X_{n-k}| = |X_n \cup \ldots \cup X_{n-k+1}| + |X_{n-k}| - |(X_n \cup \ldots \cup X_{n-k+1}) \cap X_{n-k}|}\).

Na mocy założenia indukcyjnego pierwszy składnik jest nie mniejszy niż \(\displaystyle{ n + (n-2) + \ldots + (n-2(k-1))}\). Drugi składnik to oczywiście \(\displaystyle{ n-k}\), natomiast trzeci składnik spełnia nierówność

\(\displaystyle{ |(X_n \cup \ldots \cup X_{n-k+1}) \cap X_{n-k}| \le |X_n \cap X_{n-k}| + \ldots + |X_{n-k+1} \cap X_{n-k}| \le 1 + \ldots + 1 = k}\).

Sumarycznie więc

\(\displaystyle{ |X_n \cup \ldots \cup X_{n-k}| \ge \big[ n + (n-2) + \ldots + (n-2(k-1)) \big] + [n-k] - k = n + (n-2) + \ldots + (n-2k)}\),

co kończy dowód indukcyjny.

W szczególności

\(\displaystyle{ |X| \ge |X_n \cup \ldots \cup X_{n-k}| \ge f(n)}\),

gdzie \(\displaystyle{ k}\) jest tak dobrane, by suma zakończyła się na ostatnim dodatnim wyrazie.

Pozostaje wskazać podzbiór płaszczyzny mocy \(\displaystyle{ f(n)}\), który spełnia żądaną własność. Weźmy \(\displaystyle{ n+1}\) prostych na płaszczyźnie w położeniu ogólnym, tj. parami nierównoległych i takich, że żadne trzy nie przecinają się w jednym punkcie. Oznaczmy proste przez \(\displaystyle{ \ell_0, \ldots, \ell_n}\), a ich punkty przecięcia \(\displaystyle{ p_{ \{ i, j \} }}\) dla \(\displaystyle{ i \neq j}\), tj. \(\displaystyle{ \ell_i \cap \ell_j = \{ p_{ \{ i, j \} } \}}\). Rozważmy zbiór \(\displaystyle{ X}\) złożony z takich \(\displaystyle{ p_{ \{ i, j \} }}\), że \(\displaystyle{ i+j \ge n}\). Tak zdefinowany zbiór spełnia warunek zadania, mamy bowiem

\(\displaystyle{ X \cap \ell_k = \{ p_{ \{ k, j \} } : j \in \{ n-k, n-k+1, \ldots, n \} \setminus \{ k \} \}}\),

czyli

\(\displaystyle{ |X \cap \ell_k| = \begin{cases} k+1 & \text{dla } 0 \le k < \frac{n}{2}, \\ k & \text{dla } \frac{n}{2} \le k \le n. \end{cases}}\)

Łatwo wyliczyć, że \(\displaystyle{ |X| = f(n)}\), co kończy dowód.

[Peter_85]

Tak, moja konstrukcja niestety nie była optymalna.