Jeden kontaminovaný odber krvi

Predstavte si, že ste v nemocnici, kde sa denne kontrolujú odbery krvi, či nie sú kontaminované. K dispozícii máte test, ktorý so 100% istotou dokáže aj z mikroskopického vzorku krvi určiť, či je krv kontaminovaná alebo nie. Testu to trvá 2 hodiny. Ďalej máme 100.000 odberov krvi, kde práve jeden odber je kontaminovaný.

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

Pomôcka: test môžte vykonať na krvi zmiešanej z viacerých odberov. Ak bude čo i len jeden z nich kontaminovaný, výsledok testu ukáže celú zmes ako kontaminovanú. Bude stačiť menej ako 20 testov.

Pridané 22. február 2008 by Admin

Kategória Hlavolam | 11 komentárovAndy

« Odbery krvi bez straty ( 213 / 278 ) »

Hodnotenie:Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10Hodnotenie: 7 / 10
Počet hlasov:Hlasovali: 4 ľudia
Počet zobrazení:Čítalo 8051 ľudí.

Pridaj komentár k hlavolamu


*

*

Nepoužívajte HTML kód. Môžte použiť špeciálne značky.

*
Dva plus päť slovom.

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.

Pridané 30. august 2010 12:54:04

Zdeno

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

Pridané 23. máj 2009 01:18:13

mudrc

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.

Pridané 11. máj 2009 11:49:07

Peter

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.

Pridané 25. marec 2009 05:39:28

Smazo Peky - profesor pivológie

8 bodov

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

Pridané 17. december 2008 16:56:05

Nico

7 bodov

celkom lahke..na prvy pohlad sa zdalo tazsie :D :D

Pridané 18. august 2008 19:08:09

yanush

3 body

nie je to az take tazke....

Pridané 25. júl 2008 16:07:32

m

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..

Pridané 25. júl 2008 15:54:16

mata

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

Pridané 31. máj 2008 22:21:55

Mafioso

10 bodov

a co ak budu na zaciatku obidva testy kontaminovane?

Pridané 6. máj 2008 21:32:38

orava

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ť)

Pridané 11. marec 2008 17:22:55

financ kréľa Václava