Odgadywanie liczby z zakresu Mikołaj: Ile maksymalnie pytań z odpowiedziami tak/nie trzeba zadać, aby odgadnąć liczbę: a) z przedziału od 0 do 100 000, b) z przedziału od 0 do 1 000 000? Ktoś może pomóc wyjaśnić jak rozwiązać takie zadanie?

wredulus_pospolitus: zanim się do zadania odniesiemy −−− jaki poziom nauczania? Jeżeli studia to na jakim kierunku? Jeżeli szkoła średnia to klasa o jakim profilu?

ABC: wyższa szkoła gotowania na gazie

Mikołaj: Studia, informatyka

wredulus_pospolitus: no dobra Mikołaj ... jako informatyk powinieneś zastanawiać się nad 'najgorszym możliwym rozwiązaniem'. Więc tak ... mamy 100'001 liczb zadając pytanie na które można odpowiedzieć "tak/nie"ile tak naprawdę liczb możemy 'wyeliminować' ? Pamiętaj, że chodzi o zadanie takiego pytania aby zoptymalizować (zapewnić sobie odpowiednią liczbę) ilość nieinteresujących nas liczb. Ile może zlikwidować? ~10% ? ~25%? ~50%? ~75%? ~90%? A może jeszcze inna wartość ? I dlaczego

Mikołaj: 50%, można zapytać, czy jest większa/mniejsza od 50000

wredulus_pospolitus: to jest przykładowe pytanie (można zadać inne, ale to nieistotne). Najważniejsze jest to, że nie możesz pytaniem z dwoma możliwościami odpowiedzi odrzucić więcej jak 50% możliwości

	n
a konkretniej, możesz odrzucić maksymalnie [		] (w momencie w którym bierzemy za każdym
	2

razem mniej korzystną sytuację). związku z tym szukamy takiego minimalnego 'n' dla którego (a) 2ⁿ > 100'000 ; (b) 2ⁿ > 1'000'000

Mikołaj: czyli odpowiedzi to a) 2¹7 b)2²0 ?

Mikołaj: sorki, a)2¹⁷ b)2²⁰

wredulus_pospolitus: nie ... odpowiedzi to n=17 i n=20

Mikołaj: Okej, chyba rozumiem, dziękuję!