Zbiór zadań, (zadania różne)
Zadanie 334
Dana jest siatka $14 \times 14$ punktów kratowych. Jaka jest maksymalna liczba linii prostych, które można poprowadzić przez dwa punkty siatki tak, aby żadne dwie nie były równoległe?
Rozwiązanie
Rozpatrzmy dowolną siatkę $n \times m$ punktów kratowych w układzie kartezjańskim, gdzie $n,m \ge 2$
Dla każdej takiej siatki mamy dwie proste równoległe do osi układu. Pozostałe proste będą pochylone pod pewnym kątem. Każda taka ukośna prosta przechodząca przez dwa punkty kratowe będzie wyznaczała prostokąt, którego przekątna należy do tej prostej. Prostych nierównoległych maksymalnie otrzymamy zatem dwa razy tyle, ile różnych prostokątów o bokach długości względnie pierwszych plus dwie proste równoległe do osi. Dwa razy dlatego, bo w każdym prostokącie mamy dwie przekątne i proste należące do tych przekątnych nie będą równolegle.
Należy zatem znaleźć liczbę różnych par $(x,y)$, spełniających warunki $1 \le x \le n-1$, $1 \le y \le m-1$, i które są względnie pierwsze.
Dla $n=m=14$ otrzymujemy:
$1 (13): \{1,2,3,4,5,6,7,8,9,10,11,12,13\}$
$2 (7): \{1,3,5,7,9,11,13\}$
$3 (9): \{1,2,4,5,7,8,10,11,13\}$
$4 (7): \{1,3,5,7,9,11,13\}$
$5 (11): \{1,2,3,4,6,7,8,9,11,12,13\}$
$6 (5): \{1,5,7,11,13\}$
$7 (12): \{1,2,3,4,5,6,8,9,10,11,12,13\}$
$8 (7): \{1,3,5,7,9,11,13\}$
$9 (9): \{1,2,4,5,7,8,10,11,13\}$
$10 (6): \{1,3,7,9,11,13\}$
$11 (12): \{1,2,3,4,5,6,7,8,9,10,12,13\}$
$12 (5): \{1,5,7,11,13\}$
$13 (12): \{1,2,3,4,5,6,7,8,9,10,11,12\}$
Takich różnych prostokątów mamy $13+7+9+7+11+5+12+7+9+6+12+5+12=115$
Rozwiązaniem są $2 \cdot 115 + 2 = 232$ proste.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>