Madness - Hlavolam

Pre zjednodušenie majme 8 vzoriek(nie 100000).
Očíslujem ich v dvojkovej sústave 000, 001, 010,..., 111.
Spustím 3 testy súčasne, takto:
Do prvého namiešam vzorky, ktoré majú čísla: xx1 - spolu 4 vzorky.
Do druhého namiešam: x1x - 4 vzorky.
Do tretieho: 1xx.
Zapíšem si výsledok testov v tvare: tretí, druhý, prvý. Napr.:
negativ, positiv, negativ. Prevediem to na číslo:
napr: 010 a mám číslo kontaminovanej vzorky.
3 testy spustené naraz, ukončené za 2 hodiny.
Teraz 100000 vzoriek. Pre ľahšie počítanie, nech ich je 131072.
Očíslujem ich 17-bitovým číslom 00000000000000000, 00000000000000001, ..., 11111111111111111.
Spustím 17 testov naraz.
Prvý test: xxxxxxxxxxxxxxxx1.
Druhý: xxxxxxxxxxxxxxx1x.
atď.
Výsledok zoradím od 17-ho až po prvý. A mám číslo vzorky.
17 testov spustených naraz. Čas: 2 hod.

ziadam opravit zadanie, inac sa to neda bud za 2 hodiny, lebo na 20 testov

Autor nestastne sformuloval zadanie ulohy:

Text "do dvoch hodin." nedefinuje cas, dokedy treba ulohu vyriesit, ale blizsie definuje slovo test.

Kedze vsak v zadani sa nespomina iny ako 2-oj hodinovy test, uloha mala zniet:

Úlohou je odhaliť, ktorý odber obsahuje kontaminovanú krv na čo najmenší počet testov.

Pri inej interpretacii je uloha neriesitelna.

Matematika je matematika a logika zase logika.
2 na 17 je síce 131 072, čo je viac ako 100 000 vzoriek, ale test môže trvať max. 2 hodiny. Jedno ci bezi 1 test, alebo testujem naraz vsetkych 17 vzoriek - teda bezi naraz 17 testov. Vid. postup mata. O.K.

A čo ďaľej keď zistím napr. že vzorka zmiešana z 25 000 odberov je kontaminovaná a 2 hodiny sú v prdeli ???

Alebo je zadanie správne postavené a neviem to vyriešiť nie len ja, ale ani nikto na tomto blogu.
Nech sa vyjadrí autor.

Možno autor urobil nejakú chybu v logike zadania, alebo som blbec ja.

Howgh.

chlapci a dievcata ziadne take, že najprv a potom, alebo pokracujeme...vsetky testy musia bezat sucasne, lebo test trva 2 hodiny a vy mate kontaminovanu krv odhalit do dvoch hodin

celkom lahke..na prvy pohlad sa zdalo tazsie

nie je to az take tazke....

zoberiem si prvych 50,000 vzoriek a skusim test, ak je zmiesana krv tam, rozdelim na polovicu (25,000) a opat skusim len na jednej z nich a podla toho, ktora bude poz. alebo neg. budem hladat dalej.. bude mi stacit 17 testov..

Dam ochutnat kazdemu v nemocnici a kto to nerozchodi mal kontaminovany kusok.A usetrim za testy

a co ak budu na zaciatku obidva testy kontaminovane?

To je prípad toho financmajstra ale on mal iba 14 kdí s mincami.
alebo odmena kráľa za" naučenie šachu" (na prvé pole jedno zrnko, na kaťdé ďalšie dvojnásobok).
Z polovice vzoriek zoberieme kvapku (poznačíme) a otestujeme (je alebo nie je). Ostane nám 50 000 (testovaných ak je - netestovaných ak je test NEGATÍVNY). Pokračujeme s polovicou, ostane 25 000 a zas napoly a zas. Počet určuje exponent mocniny 2.
(napr.: 2^8 = 256 , nebudem rátať, ale 2^16 = 65536, teda na 17 meraní to musím zistiť)