Tübitak Ortaokul 1. Aşama 2022 Soru 32

[matematikolimpiyati]

Başlangıçta $1$'den $30$'a kadar numaralandırılmış otuz kutunun her birinde numarası kadar top bulunmaktadır. Her işlemde bir veya birkaç kutudan eşit sayıda top çıkarılıyor. En az kaç işlem sonucunda tüm kutuların boş olması sağlanabilir?

$\textbf{a)}\ 4  \qquad\textbf{b)}\ 5  \qquad\textbf{c)}\ 6  \qquad\textbf{d)}\ 7  \qquad\textbf{e)}\ 8$

[Lokman Gökçe]

Yanıt: $\boxed{B}$

Genel halde problemi çözelim ve $m$ tane kutu olduğunu düşünelim. Bir $n$ pozitif tam sayısı için $2^{n-1} \leq m < 2^n$ eşitsizlikleri yazılabilir.

$1.$ işlemde $2^{n-1}$ tane top alınabilen tüm kutuların her birinden $2^{n-1}$ tane top alalım.
$2.$ işlemde $2^{n-2}$ tane top alınabilen tüm kutuların her birinden $2^{n-2}$ tane top alalım.
$\vdots $
$n.$ işlemde $2^{n-1}$ tane top alınabilen tüm kutuların her birinden $2^0 = 1$ tane top alalım.

Böylece $n$ işlemde tüm kutulardaki topları almış oluruz. Üstelik bu yöntemle en az sayıda işlem uygulanmış olur. Çünkü, başlangıçta farklı top sayılarının oluşturduğu küme $m$ elemanlı iken, herhangi bir $1.$ işlem sonunda bu küme en az $2^{n-1}$ elemanlı, $2.$ işlem sonunda bu küme en az $2^{n-2}$ elemanlı, ... , $n.$ işlem sonunda bu küme en az $1$ elemanlı olacaktır.

$m = 30$ için $2^4 \leq 30 < 2^5$ olduğundan $n=5$ işlem yaparak tüm kutular boşaltılmış olur.

$m=7$ için bu yöntemi açıklayalım. Kutulardaki top sayıları sırasıyla $1, 2 ,3, 4, 5, 6, 7$ dir ($7$ elemanlı bir küme).
$1.$ işlemde $4$ top alırız ve $1, 2, 3, 0, 1, 2, 3$ top kalır ($4$ elemanlı bir küme).
$2.$ işlemde $2$ top alırız ve $1, 0, 1, 0, 1, 0, 1$ top kalır ($2$ elemanlı bir küme).
$3.$ işlemde $1$ top alırız ve $0, 0, 0, 0, 0, 0, 0$ top kalır ($1$ elemanlı bir küme).