Uzdevums

LV.NOL.2005.8.3 lv

Andris iedomājās patvaļīgu naturālu skaitli \(n\). Juris ar vienu gājienu var pateikt Andrim piecus dažādus naturālus skaitļus \(x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5}\), un Andris pateiks Jurim vienu no skaitļiem \(nx_{1},\ nx_{2},\ nx_{3},\ nx_{4},\ nx_{5}\) (bet nepaskaidros, kura reizinājuma vērtību viņš saka).

Ar kādu mazāko jautājumu skaitu Juris var noteikti noskaidrot \(n\)?

Hide solution

Atrisinājums

Ar 1 gājienu nepietiek. Pirmajā gājienā Andris var atbildēt ar tādu \(x\), kas dalās ar vairākiem \(x_i\).
Ar 2 gājieniem pietiek. Otrajā gājienā Juris nosauc 5 pirmskaitļus \(p_i > x_1\) (kur \(x_1\) - Andra pirmais nosauktais skaitlis). Atkarībā no tā, ar kuru pirmskaitli dalās Andra atbilde \(x_2\), var noteikt \(n\).