Birkaç güvercin yuvası prensibi (Dirichlet İlkesi) uygulaması

Soru1: {1,2,3,...,24} kümesinden herhangi 13 eleman seçildiğinde bu elemanların içinde toplamı 25 olan 2 tanesinin bulunduğunu ispatlayınız.

Soru2: {1,2,3,...,24} kümesinden 13 eleman nasıl seçilirse seçilsin bu elemanların içinde biri diğerini tam bölen 2 elemanın bulunduğunu gösteriniz.

Soru3: {1,2,3,...,24} kümseinden 13 eleman nasıl seçilirse seçilsin bu 13 elemanın arasında farkları 2 olan 2 elemanın mutlaka bulunduğunu gösteriniz.

Soru4: Birbirinden farklı 12 sayı arasında farkları 11 ile tam bölünen 2 sayının bulunduğunu gösteriniz.

Soru5: Alican’ın 100 çikolatası vardır. Alican bu çikolataları hergün en az 1 tane yiyerek 2 ayda(60 gün) bitimiştir. Alican’ın bu 60 gün içinde tam olarak 19 çikolata yediği kesintisiz bir zaman dilimi (kesintisizden kasıt ardışık günler topluluğu örneğin 3. ve 14. günlerin arasındaki tüm günler) olduğunu gösteriniz.

Soru6: Birim çember (yarıçapı 1 birim olan çember) üzerinde veya içinde seçilecek herhangi 6 noktadan aralarında en fazla 1 birim mesafe olan en az 2 tanesi olduğunu gösteriniz.

Soru7: 1 den 12 ye kadar sayılar bir çemberin üzerine diziliyor. Bu işlem hangi sıralamayla yapılırsa yapılsın toplamları 20 veya daha fazla olan komşu 3 sayının muhakkak bulunacağını gösteriniz

Soru8: Sonu 0001 ile biten 7 nin bir kuvveti olduğunu gösteriniz.

Anlatımda buna benzer ispatlanması istenen ifadeler vardı. Biraz kafa yormak gerekiyor.

1.SORU:
toplamları 25 yapan ikililer (1,24) (2,23) (3,22)...(11,14) (12,13) şeklinde toplam 12 tane vardır. biz 13 sayı seçeceğimizden seçilen 13 sayıdan ikisi yukarıda yazdığımız ikililerden biri olmak zorunda. (yani 13 güvercinimiz var 12 de yuvamız var o halde bir yuvada en az iki güvercin olmak zorunda )

diğer sorulardan bazılarını yaptım (3,5,6,8)
sorular güzel diğer arkadaşlarda uğraşır diye çözümleri yazmadım. yapamadıklarımla bende uğraşıcam.

ya bana güvercin yuvası ile ilgili sorular lazımda nerden bulabilirim yardımcı olursanız sevinirim

Soru1: {1,2,3,...,24} kümesinden herhangi 13 eleman seçildiğinde bu elemanların içinde toplamı 25 olan 2 tanesinin bulunduğunu ispatlayınız.

Soru2: {1,2,3,...,24} kümesinden 13 eleman nasıl seçilirse seçilsin bu elemanların içinde biri diğerini tam bölen 2 elemanın bulunduğunu gösteriniz.

bu guvercin yuvası ilkesi sorularının ilk 5 tane sorunun çözümlü cevaplarını yazablrmsnz ?

1.
elemanları (1,24)-(2,23)-...-(10,15)-(11,14)-(12,13) şklinde 12 tane gruba ayıralım. görüldüğü gibi tüm grupların elamanları toplamı 25 tir.
bu 24 sayıdan 13 tane seçtiğimizde güvercin yuvası prensibine göre 12 grubumuzdan en az 1 tanesi seçilmiş sayılardan 2 tan içerecektir bu da toplamları 25 olan 2 sayı bulunmasını gerektirir.


2.
sayıların en büyük tek çarpalarına göre gruplar oluşturalım
(1,2,4,8,16)-(3,6,12,24)-(5,10,20)-(7,14)-(9,18)-(11,22)-(13)-(15)-(17)-(19)-(21)-(23)

görüldüğü gibi 12 grup vardır ve 13 sayı seçilirse en az 1 grup 2 sayı içermelidir , herhangi bir gruptaki iki sayıdan küçük olan büyük olanı kesinlikle böldüğüne göre de bu 2 sayı içeren gruptaki sayılar aranana sayılar olacaktır.


3.
(1,3)-(2,4)-(5,7)-(6,8)-(9,11)-(10,12)-(13,15)-(14,16)-(17,19)-(18,20)-(21,23)-(22,24) şeklinde 12 grup oluşturulduğunda seçilen 13 sayıdan en az 2 tanesini içeren bir grup kesinlikle olacaktır , o gruptaki iki saının farkı 2 dir.


4.
bir sayı 11 ile bölündüğünde kalanlar 0,1,2,...,10 olmak üzere toplam 11 değer alabilir.
12 farklı sayı seçildiğinde (aslında farklı olmalarına gerek yok aynı olan varsa zaten cevap olur) 11 kalan grubundan en az 1 tanesi 2 tane sayı içerecektir, başka deyişle kalnları aynı olacaktır öyleyse bu iki saının farkı da 11 ile bölünmek zorundadır.


5.
A_i ile Alican'ın i. gün sonunda yediği toplam çikolata sayısını gösterelim.
hergün en az 1 tane yediğinden
1≤A₁<A₂<A₃<...<A₅₉<A₆₀=100 olduğunu biliyoruz
ayrıca
20≤A₁+19<A₂+19<A₃+19<...<A₅₉+19<A₆₀+19=119 da yazabiliriz

şimdi elimizde 60 şarlı 2 grup halinde 120 sayı var (gruplar kendi içinde aynı sayıyı içeremiyor) ve bu sayılar 1 ile 119 arasında değerler alabiliyor öyleyse bu sayılardan en az 2 tanesi aynı değeri almak zorundadır.
yani A_i=A_j+19 olan i ve j sayıları olmalıdır.
öyleyse j. ve i. gün arasındaki ardışık gnlerde Alican tam olarak 19 çikolata yemiştir.

6)
Ardışık noktalar arasındaki yayları düşünürsek tüm yayların toplamı 360 derece yani bu yaylardan biri en çok 60 derecedir ( Hepsi birden 60 dereceden büyük olamaz. ) bu yayın uç noktaları arasındaki mesafe de en çok 1 br olur.

7)
Sayılar saat yönünde a₁,a₂,...,a₁₂ olsun.

b₁=a₁+a₂+a₃
b₂=a₂+a₃+a₄
.
.
b₁₂=a₁₂+a₁+a₂

olsun. b_i'lerin toplamı 3(1+2+..+12)=234 yani bu sayılardan biri 234/12=19,5'dan büyüktür.

8)
7¹,7²,..,7¹⁰⁰⁰¹ sayılarının 10000'e bölümünden kalanlar sırayla k₁,k₂,...,k₁₀₀₀₁ olsun. Olası 10000 kalan olduğundan öyle i,j vardır ki k_i=k_j bu durumda 7ⁱ-7^j 10000 ile bölünür (i>j). 7ⁱ-7^j=7^j(7^i-j-1)≅0 mod 10000 . (7^j,10000)=1 olduğundan (7^i-j-1)≅0 mod 10000 olmalıdır bu da 7^i-j'nin istenen şekilde 7'nin kuvveti olduğunu gösterir.

dirichlet ilkesi güvercin yuvası prensibi
Tüm Etiketler