Geomania.Org Forumları
Yarışma Soruları => Tübitak Lise 1. Aşama => 2023 => Konuyu başlatan: matematikolimpiyati - Temmuz 03, 2023, 05:39:32 ös
-
$0*1*2*3* \cdots *30*31$ ifadesindeki $31$ tane $*$ işaretinin her birinin yerine $+$ ya da $-$ işareti yazarak kaç farklı pozitif tam sayı elde edilebilir?
$\textbf{a)}\ 224 \qquad\textbf{b)}\ 248 \qquad\textbf{c)}\ 312 \qquad\textbf{d)}\ 368 \qquad\textbf{e)}\ 496$
-
Cevap: $\boxed{B}$
Başta tüm işaretlerin $+$ olduğunu ve bizim bazılarını $-$ yaptığımızı varsayalım. İlk başta sayımız $496$'dır. Her $+a$'yı $-a$ yaptığımızda $496-2a$ olur, yani sadece çift sayıları elde edebiliriz. İddiamız tüm çift sayıların yazılabileceğidir. Bu da aslında $\sum a=0,1,2,\dots, 247$ olacak şekilde $A=\{1,2,\dots,31\}$ kümesinden elemanlar seçebildiğimize denktir (Hiçbir eleman seçmezsek $0$ toplamı elde etmiş oluruz). Bunun için de aslında basitçe "en büyük elemanı seçme" algoritmasını uygulayabiliriz. Algoritma şu şekildedir,
$1)$ $S=\sum a$ olsun. Her adımda $S$ veya kümede kalan sayıların en büyüğü arasından en küçük olanı seçeceğiz. Örneğin ilk adımda $\min\{S, \max A\}=\min\{\sum a, 31\}$'i seçeceğiz.
$2)$ Her seçimden sonra $S$'yi toplamdan önceki eleman çıkartılmış olarak değiştireceğiz ($S\to S-\min\{S, \max A\}$) ve kümeden seçilen elemanı çıkartarak ($A\to A- \{\min\{S, \max A\}\}$) seçimlere devam edeceğiz.
$3)$ $S=0$ kaldığında o ana kadar seçilen sayılar bizim aradığımız sayılardır.
Bu algoritma ile $496$'ya kadar olan sayılarda çalışacaktır. İspatı da aslında basittir. Çünkü "minimum eleman" seçimimizi yapamamamız için ya kümede eleman kalmamalı, ya $S$'yi seçmemiz gerekirken kümede $S$ olmamalı, ya da toplam $(S)$ bir anda $+$'dan $-$'ye düşmelidir. İlk durum imkansızdır çünkü $1+2+\cdots+31=496>248$'dir. İkinci durumda olabilecek en büyük elemanı seçmemizle çelişir çünkü $S$'yi seçmemiz gerekiyorsa $S$'nin karşısındaki sayı $S$'den daha büyüktür, o zaman da $S$ hala elenmemiş olmalıdır. Son ihtimalde ise seçimlerde $S$'yi seçebileceğimizden $-$'ye düşmesi imkansızdır.
Örneğin $\sum a=115$ için sırasıyla $31,30,29,25$ sayılarını bulacağız. Bu da bu sayıların işaretini $-$, kalanları $+$ yaparsak $496-2\cdot 115=226$ sayısını elde edeceğimiz anlamına geliyor.
Dolayısıyla $2,4,6,8,\dots, 496$ çift sayılarını elde edebiliriz. Bunlar da tam olarak $248$ tanedir.