LIV OM - I - Zadanie 7

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

U cioci Reni spotkało się (łącznie z ciocią) $n \geq 4$ osób. Każdy z obecnych podarował co najmniej jednej z pozostałych osób co najmniej jeden prezent. Okazało się, że każdy podarował trzykrotnie więcej prezentów niż sam otrzymał, z jednym wyjątkiem: ciocia Renia podarowała zaledwie $\frac{1}{6}$ liczby prezentów, które dostała. Wyznaczyć, w zależności od $n$ , najmniejszą możliwą liczbę prezentów, które mogła otrzymać ciocia Renia.

Rozwiązanie

Oznaczmy przez $x_i$ ( $i = 1,2, \ldots ,n-1$ ) liczbę prezentów otrzymanych przez $i$ -tego gościa cioci Reni oraz niech $x_R$ oznacza liczbę prezentów, które otrzymała ciocia Renia. Wówczas łączna liczba prezentów wynosi

$ (1) \qquad \sum^{n-1}_{i=1} x_i+x_R=\sum^{n-1}_{i=1} 3x_i+\frac{1}{6} x_R,\ \textrm{skąd}\ \sum^{n-1}_{i=1} x_i=\frac{5}{12}{x_R}. $

Zatem liczba $x_R$ jest podzielna przez $12$ , powiedzmy $x_R = 12k$ , gdzie $k$ jest pewną liczbą całkowitą nieujemną.

Ponieważ każda osoba podarowała co najmniej jeden prezent, więc musiała ona także otrzymać przynajmniej jeden upominek. Stąd wnioskujemy, że $x_i \geq 1$ dla $i = 1,2,\ldots ,n-1$ , co na mocy drugiej równości (1) daje $5k \geq n- 1$ . Ponieważ liczba $k$ jest całkowita, więc ostatnia nierówność jest równoważna nierówności $k \geq [(n-1+4)/5]$ , gdzie $[a]$ oznacza największą liczbę całkowitą nie większą niż $a$ . Zatem

$ x_R\geq \left[ \frac{n+3}{5} \right]. $

Pozostaje wykazać, że przy spełnieniu warunków zadania możliwe jest, aby ciocia Renia dostała dokładnie $12 [(n+3)/5]$ prezentów.

Załóżmy, że $n - 1 = 5k - r$ , gdzie $r = 0,1,2,3,4$ , zaś $k$ jest pewną liczbą całkowitą dodatnią. Podzielmy $n-1$ gości cioci Reni na (co najwyżej) trzy rozłączne grupy:

$ A_1,A_2,\ldots,A_{3k-r} , \ B_1,B_2,\ldots,B_{2k-r} , \ C_1,C_2,\ldots ,C_r . $

(Ponieważ $n \geq 4$ , więc $2k-r \geq 0$ .) Następnie posadźmy wszystkie osoby $A_i$ oraz $C_i$ przy okrągłym stole i przyjmijmy, że:

Każda osoba $A_i$ , $C_i$ daje 1 prezent osobie siedzącej po jej prawej stronie;
Każda osoba $A_i$ daje 2 prezenty cioci Reni;
Każda osoba $B_i$ daje 3 prezenty cioci Reni;
Każda osoba $C_i$ daje 5 prezentów cioci Reni;
Ciocia Renia daje po 1 prezencie każdej osobie $B_i$ oraz $C_i$ .

W ten sposób każda osoba $A_i$ oraz $B_i$ podarowała $3$ prezenty, zaś otrzymała jeden, natomiast każda osoba $C_i$ dała $6$ prezentów, a sama dostała dwa. Zatem każdy gość cioci Reni podarował trzykrotnie więcej prezentów niż sam dostał. Z kolei ciocia Renia otrzymała