Algoritmiski meklēšanas uzdevumi, izņemot uzdevumus ar sviras svariem
Laboratorijā \(64\) mēģenēs atrodas siekalu paraugi (siekalu daudzums paraugā ir pietiekams vairākām pārbaudēm). Zināms, ka viens paraugs ir inficēts ar vīrusu. Laborantam ir \(6\) testa trauki, kuros var ieliet siekalas no mēģenēm, un \(6\) reaģenti, ko pieliet testa traukā izveidotajam siekalu maisījumam (tiklīdz reaģentu ielej testa traukā, tas uzrāda vai neuzrāda vīrusa klātbūtni, un pēc tam kļūst neaktīvs). Kā, izmantojot \(6\) testa traukus un \(6\) reaģentus, noskaidrot, kurā paraugā ir vīruss?
Katrs no trīs rūķīšiem ir iedomājies vienu no skaitļiem \(1,\ 2\) vai \(3\), katrs - citu skaitli. Katrs rūķītis zina, kādus skaitļus ir iedomājušies pārējie rūķīši.
Kā var noskaidrot, kuru skaitli katrs rūķītis ir iedomājies, ja katram rūķītim var uzdot tieši vienu jautājumu, uz kuru viņš var atbildēt tikai ar "jā" vai "nē"? Katram rūķītim drīkst jautāt arī par citu rūķīšu iedomātajiem skaitļiem.
Katrīna iedomājusies divciparu naturālu skaitli, bet Profesors Cipariņš cenšas to uzminēt. Ar vienu jautājumu viņš nosauc Katrīnai kaut kādu savu iedomātu divciparu skaitli, bet Katrīna pasaka, cik šķirās (nevienā, vienā vai divās) profesora nosauktais skaitlis sakrīt ar viņas iedomāto. Pierādiet, ka profesors var noskaidrot Katrīnas iedomāto skaitli, uzdodot ne vairāk kā \(10\) jautājumus.
Piezīme. Ja Jūs nevarat izdomāt stratēgiju ar \(10\) jautājumiem, bet varat ar \(11,\ 12\) utt., uzrakstiet labāko no savām atrastajām.
Profesoram Cipariņam ir \(10\) monētas; tieši \(2\) no tām ir viltotas, bet viņš nezina, kuras. Cipariņš pazīst burvi, kuram vienā reizē var iedot pārbaudīt \(3\) monētas; pēc pārbaudes burvis atdod monētas atpakaļ un klusējot norāda uz vienu no tām. Ir zināms: burvis nenorāda uz īstu monētu, ja starp viņam iedotajām trim monētām ir kaut viena viltota. Kā ar \(4\) pārbaudēm Cipariņš var garantēti noskaidrot vismaz vienu viltoto monētu?
Rūķītis ir iedomājies skaitļus \(x_{1}, x_{2}, x_{3}\) un \(x_{4}\), katrs no tiem ir vai nu \(0\), vai \(1\). Ja rūķītim pajautā: "Kāds ir \(i\)-tais skaitlis?" (\(i=1,2,3\) vai \(4\) pēc izvēles), tad viņš pasaka \(x_{i}\) vērtību.
Pierādīt, ka ar \(3\) jautājumiem pietiek, lai uzzinātu, vai virkne \(x_{1},\ x_{2},\ x_{3},\ x_{4}\) ir monotona.
Skaitļu virkne \(x_{1},\ x_{2},\ x_{3},\ x_{4}\) ir monotona, ja tā ir nedilstoša vai neaugoša (t. i., \(x_{1} \leq x_{2} \leq x_{3} \leq x_{4}\) vai \(x_{1} \geq x_{2} \geq x_{3} \geq x_{4}\) ).
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\)?
Sivēnam ir \(10\) podi ar medu, kas pēc kārtas sanumurēti ar skaitļiem no \(1\) līdz \(10\). Kādu dienu viņš uzzināja, ka Vinnijs Pūks slepeni ir izēdis četrus no tiem, pie tam to numuri veido aritmētisko progresiju. Katra poda saturu Sivēns var pārbaudīt. Pierādīt, ka viņš var noskaidrot, kuri tieši ir izēstie podi, pārbaudot ne vairāk kā četrus podus!