XXXV OM - II - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Obliczyć kres dolny pól sześciokątów wypukłych, których wszystkie wierzchołki mają współrzędne całkowite.

Rozwiązanie

W rozwiązaniu zastosujemy następujący lemat, który był treścią zadania konkursowego w poprzedniej Olimpiadzie Matematycznej

Lemat. Podwojone pole trójkąta, którego wszystkie wierzchołki mają współrzędne całkowite jest liczbą całkowitą.

Dowód. Pole trójkąta $ABC$ jest równe połowie wartości bezwzględnej
wyznacznika utworzonego ze współrzędnych wektorów $\overrightarrow{AB}$ i $\overrightarrow{AC}$ . Jeśli współrzędne wierzchołków $A$ , $B$ , $C$ są liczbami całkowitymi, to współrzędne wektorów $\overrightarrow{AB}$ i
$\overrightarrow{AC}$ też są liczbami całkowitymi, wyznacznik utworzony z tych współrzędnych również jest liczbą całkowitą, a w konsekwencji podwojone pole trójkąta $ABC$ jest liczbą całkowitą.

Każdy punkt na płaszczyźnie mający współrzędne całkowite należy do dokładnie jednego z następujących czterech zbiorów

$A$ - zbiór punktów, których obie współrzędne są parzyste,
$B$ - zbiór punktów, których obie współrzędne są nieparzyste,
$C$ - zbiór punktów, których pierwsza współrzędna jest parzysta, druga nieparzysta,
$D$ - zbiór punktów, których pierwsza współrzędna jest nieparzysta, druga parzysta.

Gdy dwa punkty płaszczyzny należą do jednego z tych zbiorów, to mówimy, że mają ten sam typ parzystości. Jeżeli punkty $P = (p_1,p_2)$ i $Q = (q_1, q_2)$ mają ten sam typ parzystości, to środek odcinka $\overline{PQ}$ ma współrzędne
$\left( \displaystyle \frac{1}{2} (p_1+q_1), \frac{1}{2} (p_2+q_2) \right)$ będące liczbami całkowitymi (suma liczb tej samej parzystości jest liczbą parzystą).

Powróćmy do sześciokątów wypukłych, których każdy wierzchołek ma współrzędne całkowite. Wśród sześciu wierzchołków sześciokąta można znaleźć dwa mające ten sam typ parzystości.

Jeśli dwa kolejne wierzchołki (np. $K$ i $L$ ) sześciokąta $KLMNOP$ mają ten sam typ parzystości, to łącząc środek $S$ odcinka $\overline{KL}$ z punktem $M$ otrzymamy sześciokąt $KSMNOP$ mający pole mniejsze od sześciokąta $KLMNOP$ . Przy wyznaczaniu kresu dolnego pól sześciokątów możemy więc ograniczyć się do takich sześciokątów, w których kolejne wierzchołki nie mają tego samego typu parzystości. Wobec tego istnieją pewne dwa niekolejne wierzchołki mające ten sam typ parzystości. Środek odcinka łączącego te wierzchołki ma współrzędne całkowite i leży wewnątrz sześciokąta. Łącząc ten środek z wszystkimi wierzchołkami sześciokąta otrzymamy sześć trójkątów, których suma pól równa jest polu sześciokąta. Wobec tego na mocy lematu pole sześciokąta jest nie mniejsze od $6 \cdot \frac{1}{2} = 3$ . Przykładem sześciokąta wypukłego mającego wierzchołki o współrzędnych całkowitych, którego pole wynosi $3$ , jest sześciokąt o wierzchołkach $K = (- 1, - 1)$ , $L = (0, - 1)$ , $M = (1, 0)$ , $N = (1,1)$ , $O = (0,1)$ , $P = (- 1, 0)$ .

Szukany kres dolny wynosi więc $3$ .