LIV OM - I - Zadanie 7

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

\[<br />
(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}.<br />
\]

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

\[<br />
x_R\geq \left[ \frac{n+3}{5} \right].<br />
\]

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:

\[<br />
A_1,A_2,\ldots,A_{3k-r} , \  B_1,B_2,\ldots,B_{2k-r} , \    C_1,C_2,\ldots ,C_r .<br />
\]

(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:

  1. Każda osoba $ A_i $, $ C_i $ daje 1 prezent osobie siedzącej po jej prawej stronie;
  2. Każda osoba $ A_i $ daje 2 prezenty cioci Reni;
  3. Każda osoba $ B_i $ daje 3 prezenty cioci Reni;
  4. Każda osoba $ C_i $ daje 5 prezentów cioci Reni;
  5. 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

\[<br />
2(3k - r) +3(2k - r) + 5r = 12k = 12[(n+3)/5]<br />
\]

prezentów, sama zaś podarowała $ 2k $ upominków, czyli sześciokrotnie mniej.

Odpowiedź: Ciocia Renia mogła otrzymać co najmniej 12[(n+3)/5] prezentów.

Komentarze

Dodaj nową odpowiedź