Polinom Oyunu Sorusu

Question

Galiba aslinda ortaogretim sorusu. Editorler degistirebilirler uygun gorurlerse kategoriyi.

Handan ile Sercan bir oyun oynuyorlar. Oyun basit: Sercan bir polinom sececek ve Handan da bu polinomun ne oldugunu bulacak. Oyunun kurallari soyle:

Sercan'in sectigi polinom istedigi dereceden olabilir ancak butun katsayilari pozitif tamsayi olmak zorunda.

Handan ise Sercan'a bu polinomun pozitif tamsayilardaki (Handan bu pozitif tamsayilari kendi secebilir) degerini sorabilir. Ornegin Handan "Sercan sectigin polinomum 1234'teki degeri kactir?" diyebilir ve Sercan da buna dogru cevap vermek zorunda. Sonra Handan "Peki 3456'daki degeri kactir?" diyebilir ve Sercan buna da dogru cevap vermek zorunda. Ve bu boyle devam edebilir, Sercan hep dogru cevap vermek zorunda.

Soru: Handan en az kac tane soru sormalidir ki Sercan'in sectigi polinomu dogru tahmin etsin?

Comments

icinde Sercan gectigi icin begeniyorum, gerci gecmese de begenirdim. Bu arada puan da 999 :) +2 geliyor.. 

---

Özgür; joker hakkimi kullanmak istiyorum: yanıma seni, Safak'i birde fizikseveri almalıyım;))

---

Ipucu vereyim: Cevap iki. Neden iki? Nasil iki? Polinomun derecesi ne olursa olsun, sadece iki soru sorarak polinomu bulabiliyorsunuz.

---

hala cevap verilmedi, cevabı paylaşıcak mısınız ?   :)

---

@Ozgur, buradaki pozitif herhangi gercel mi yoksa sadece tam sayi mi?:
"Sercan'in sectigi polinom istedigi dereceden olabilir ancak butun katsayilari pozitif olmak zorunda."

Yoksa $P(1)+1$ her zaman tam sayi olmaz. Bu durumda ikincide sorulamayabilir. 

---

Ben cevabın 2 yerine n+1 olması gerektiğini düşünüyorum. 2. Dereceden polinom için bile 3 noktaya ihtiyaç var interpolasyondan dolayı.

---

Peki Handan Sercanin  kaçıncı dereceden polinom seçtiğini biliyormu?

---

$P(x)=x^2+3x+5$ olsun.

$P(1)=9$ ve $P(10)=10^2+3\cdot10+5=(135)_{10}$ yapar, yani taban aritmetigi ile kat sayilari bulabiliriz.

$P(x)=17+x+2x^2+3x^3+4x^4+x^5$ olsun.

$P(1)=27$ ve $P(28)=(1,4,3,2,17)_{28}$ olur. Polinom katsayilarini yine bulabiliriz.

---

@Sercan düzelttim, sağol.

@Okkes Dulgerci bilmiyor. Oyunun güzel yanı da bu. Ama katsayıların pozitif tam sayı olduğunu biliyor.

---

$P(1)=a$

$P(P(1)+1)=P(a+1)=b$  degerlerine sahip iki farkli polinom olamaz mi.

Yani

$P(x)=x^2+3x+5$

$P(1)=9$

$P(10)=10^2+3\cdot10+5=135$   olsun.

$G(x)=\sum_{k=0}^{n}a_kx^k\neq P(x),\quad a_k\in\mathbb{Z^+}$  icin

$G(1)=9$
$G(10)=135$   olamayacagini nasil garanti ediyoruz?

---

Sercan'ın cevabı bunu garanti ediyor. Oncelikle $10$'un bütün katsayilardan büyük olduğunu görüyoruz. Sonra da $$G(10) = a_0 + a_1 . 10+ a_2 .10^2+\ldots + a_n 10^n =135$$ olduğunu görüyoruz. Bu $135$'in $10$ tabanında yazılımı demek. $135$'i $10$ tabanında yalnızca bir şekilde yazabilirsin. Bu da $a_i$'lerin tek (unique) oldugunu söylüyor.  

Answer 1

Murad'in dedigi gibi baslayalim. Ilk olarak $P(1)$'i soralim. Bu tum terimlerin toplami olacagindan tum terimlerden buyuk olur. (Eger sadece tek terimli ise o terimin katsayisina esit olur).

Ikinci adimda da $P(P(1)+1)$'' soralim. Tum katsayilar $P(1)+1$'den kucuk oldugundan taban aritmetigindeki kat sayilarin tekligini kullanarak tum kat sayilari bulabiliriz.

Comments

hangi madalyadan veriyim hocam.

---

No madalya no cry.

---

$P(1)=15$

$P(P(1)+1)=P(16)=2,295,555$  olsun. Hangi polinomu tuttum ben?

---

$P(1)=13+3\sqrt{2}$

$P(P(1)+1)=P(14+3\sqrt{2})=198403+2162688 \sqrt{2}$

$P(x)=?$

---

Yukarida bir Ozgur'e sorayim. Ilk pozitif dedigi de tam sayi mi diye. Galiba ben cozerken o sekilde dusunmusum.

Ikinci soruyu bu polinom icin soramam cunku tam sayi olan bir deger sorabilirim anca. 

---

Evet 2.soru kurala aykırı olmuş, zaten büyük ihtimalle katsayılar pozitif tamsayidir.

Answer 2

Handan, Sercan'a tek bir soru sorarak polinomu bulabilir. Katsayıları pozitif olan polinomu $P(x)$ ile gösterelim. Soru şu: $$P(10)=?$$

Mesela Sercan $P(x)=2x^4+5x^2+x+7$ polinomunu seçmiş olsun.

$$P(10)=2.10^4+5.10^2+10+7=20000+500+10+7=20517$$

olur. Bu sayıdaki rakamların soldan sağa doğru bakıldığında polinomun katsayıları olduğunu görmek zor olmasa gerek.

Comments

$P(x) = x^2$ ve $Q(x) = 10x$ polinomlarini ayiramaz Handan bu taktikle.

---

Haklısınız. Bu durumu atlamışım. O zaman $P(1)$ kaçtır sorusunu da sorması gerekecek.

---

$P(x) = x^2 + 10x$ ve $Q(x)= 11x$ fonksiyonlarina bakalim o zaman. $$P(1) = Q(1) = 11 \quad ; \quad P(10) = Q(10) = 110$$ Bunlari ayiramadin bu sefer de.

Bana $a_1, \ldots, a_n$ noktalarini ver, sana bu noktalarda ayni degeri alan ve istenilen sartlari saglayan iki farkli polinom bulabilirim. Bu yuzden Handan onceden belirledigi sayilari sorarak kazanan bir strateji bulamaz.

---

Haklısınız. Bu durumu da atlamışım. Biraz daha düşünelim.