$100$'den küçük sayılardan birini bulmak için kaç soru sormak gerekir?

Question

Salih $1\le k \le 100$ olmak üzere, bir $k$ tam sayısı tutuyor. Merve her seferinde tutulan sayının, kendisinin belirleyip söylediği bir tam sayıya bölünüp bölünemediğini soruyor. Salih, Merve'nin her sorusunu "evet" yada "hayır" diye yanıtlıyor. Salih'in tuttuğu sayı ne olursa olsun Merve, bu sayıyı bulmasını garanti etmek için en az kaç soru hakkı istemelidir?

Ben $p,a\in\mathbb{N^+}$ ve $p$ asal sayı olmak üzere $p^a$ şeklinde yazılabilen sayıların sayısının olduğunu düşümdüm. Bunlardanda

$$2^1,\cdots,2^6$$

$$3^1,\cdots,3^4$$

$$5^1,5^2$$

$$7^1,7^2$$

$$11,13,\cdots,97$$

Bunu sağlar deyip sonucu $35$ buldum ama sonuçta $30$ olduğu söyleniyor. Bu sonuca nasıl gidebiliriz acaba?

Comments

Emre 

Merve bu sayıyı bulmayı garanti etmek için, en az $100$ den kucuk bütün asal sayıları sorma hakkı istemelidir, sence?

---

100 den küçük asallar 

$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$

Ama senin cevap 30 diyor burada 100 den küçük asal sayıların kümesi 25 adet cevabına bir daha bakarmışım.

---

Tam olarak emin değilim ama şöyle düşündüm ben: $2$'nin kuvvetlerinin hepsini sormak zorunda değilim. Sormaya $2^3$'ten başlarsam en fazla üç hamlede $2$'nin kuvvetlerini bitirebilirim? Eğer cevap hayır ise $2^1$ ve $2^2$'yi sorarım. Eğer cevap evet ise ilk önce $2^5$'i sorarım. Cevabına göre $2^4$ veya $2^6$'yı sorarım. Buradan üç hamle kazandık.

Üçün kuvvetlerinden de bir hamle kazanabiliriz $3^2$'den ya da $3^3$'den başlayarak.

$35$'ten $31$'e düştük.

---

Öte yandan $5$ ve $7$ için de bir numara var. $35$'e bölünüyor mu? Cevap evet ise $5$ ve $7$ ye bölünüyordur. $5^2$ be $7^2$ ile de bölünmüyordur. Cevap hayır ise $5$ ve $7$'den yalnızca birine bölünüyordur. $5$'e bölünüyor mu diye sorup hangisine bölündüğünü öğrenirim. Hangisine bölünüyorsa onun karesini sorarım ondan sonra.

Bu yöntemle de $30$a indik.

Içimden bir ses sanki $2$ ve $3$e (ya da onların kuvvetlerine) de bu numarayı uygulayıp $29$'a bile inebiliriz diyor ama bulamadım.

---

Gerçektende çok mantıklı bir cevap olmuş teşekkürler. Kitapta cevap yanlış verilmiş.

Answer 1

Salih $1\leq k\leq 100$ olmak üzere bir tam sayısı tutuyor.

Salih, Merve nın bu sayıyı bulamaması için 100 den küçük en büyük asal sayı olan 97 yi seçmesi yani 97 ye kadar hayır demesi gerekir o zaman

Merve bu sayıyı bulmayı garanti etmek için, en az $100$ den küçük bütün asal sayıları sorma hakki istemelidir.

Aciklama;

Salihin tuttuğu sayı 1 ise, Merve 100 den küçük olan tüm asal sayılara (yani 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 sayılarına) bölünüp bölünmediğini öğrenmeden bu sayıyı bulamaz.Dolasıyla soru sayısı $25$ ten az olamaz. $25$ sorunun yeterli olduğunu gösterelim. Merve ilk ''evet'' yanıtını alana kadar asal sayıları küçükten büyüğe doğru sorar.Örneğin, sayı $2$`ye bölünüyorsa, $2^2$`ye, $2^3$ e vs.. bölünüp bölünmediğini de sorar, sonra yine asal sayılara devam eder. $2$`ye bölünen bir sayı 71,73,...,97 asal sayılarına bölünemeyeceği için soru sayısı yine $25$`i geçmez.$100$ den küçük asal sayıların kümesi $25$ adettir.

Doğru yanıt:$25$`tir.

Comments

Bu soruya bakarken asal sayı ile ilgili bir algoritma ya rastladım ilginizi çekebilir. 

Eratosten Kalburu

---

Bu çözüm (cevap tan hangi soruların sorulacağı tam anlaşılmıyor, tüm asallara bölünebilirliği sorulmak istendiğini anlıyorum) anladığım gibi ise olmaz. 

Öyle ise, 25 soru sonunda,

"2 ye bölünüyor ve diğer 24 asaldan hiç birine bölünmüyor" 

cevabını alırsak sayını kaç olduğunu bulabiliyor muyuz?

---

Salihin tuttuğu sayı 1 ise, Merve 100 den küçük olan tüm asal sayılara (yani 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 sayılarına) bölünüp bölünmediğini öğrenmeden bu sayıyı bulamaz.Dolasıyla soru sayısı $25$ ten az olamaz. $25$ sorunun yeterli olduğunu gösterelim. Merve ilk ''evet'' yanıtını alana kadar asal sayıları küçükten büyüğe doğru sorar.Örneğin, sayı $2$`ye bölünüyorsa, $2^2$`ye, $2^3$ e vs.. bölünüp bölünmediğini de sorar, sonra yine asal sayılara devam eder. $2$`ye bölünen bir sayı 71,73,...,97 asal sayılarına bölünemeyeceği için soru sayısı yine $25$`i geçmez.Doğru yanıt:$25$`tir.

---

A-ha! Çok mantıklı. Ama bu yorumu orijinal cevabına eklemelisin bence. Orijinal cevabından sadece asal sayıları sormak yeter gibi anlaşılıyor.

---

Tamam şimdi oldu.