Matematyka.pl

Mamy 16 szufladek. Do jednej z nich wkładamy przedmiot. Ile bitów informacji potrzeba(minimalnie) aby powiedzieć, w której szufladce jest przedmiot?

Dodano po 1 godzinie 8 minutach 39 sekundach:
Myślałem żeby móc wykorzystać tutaj być może silnie. Ale pewności nie mam.

Nie myśl kategoriami silnia się przyda bądź nie. Silnia to tylko matematyczna notacja upraszająca szczególne mnożenie. Staraj się myśleć raczej kategoriami idei algorytmów które ciągi bitów zamieniają na jednoznaczną odpowiedź w której szufladzie jest przedmiot. Przykładowo cztery bity wystarczą. Bo istnieje algorytm który \(\displaystyle{ 4}\) bitową informację przekształci na odpowiedź. Taką \(\displaystyle{ 4}\) bitową informacją może być ciąg \(\displaystyle{ \leftarrow \leftarrow \rightarrow \leftarrow }\) lub każdy inny układ czterech strzałek prawo/lewo np: \(\displaystyle{ \leftarrow \leftarrow \leftarrow \leftarrow }\). Algorytm działa tak, że pierwsza strzałka określa czy przedmiot jest w szufladzie od \(\displaystyle{ 1}\) do \(\displaystyle{ 8}\) albo od \(\displaystyle{ 9}\) do \(\displaystyle{ 16}\). To znaczy rząd \(\displaystyle{ 16}\) szuflad dzielisz na dwa i strzałka mówi Ci którą połowę wybrać. Kolejna strzałka wskazuje połowę wcześniejszej połowy więc na tym kroku wiesz, że przedmiot jest w jednej z \(\displaystyle{ 4}\) wskazanych szuflad. Kolejna strzałka kolejna połowa. Teraz zasłały już tylko dwie szuflady, ale masz jeszcze ostatnią strzałkę która mówi czy wybrać prawą czy lewą. To samo rozumowanie można rozbić bez strzałek. Wystarczy zauważyć, że binarnie \(\displaystyle{ 16}\) wartości przypiszemy ciągom zer i jedynej długości \(\displaystyle{ 4}\). Na koniec trzeba jeszcze pokazać, że \(\displaystyle{ 3}\) bity to za mało. Na \(\displaystyle{ 3}\) bitach można zakodować \(\displaystyle{ 8}\) wartości. To jednak za mało po potrzebujemy \(\displaystyle{ 16}\) jako, że przedmiot może być w jednej z \(\displaystyle{ 16}\) szuflad.

Ok. To co napisałeś też w rozważałem i to nawet przed silnią lecz odrzuciłem z uwagi na to że jak np. zrobić taki algorytm gdyby jakiś przedmiot wylądował w 1 albo w 16 szufladzie. Mam przedmiot w 1 szufladzie. I co teraz. Myślałem też żeby ułożyć jakiś wzór ciągu, który pozwoliłby coś takiego w miare prosty sposób obliczyć.

Jeśli masz Teorię Informacji, to skorzystaj ze wzoru Claude Shannona na ilość bitowej informacji:

\(\displaystyle{ H(x) = - \sum_{i=1}^{n} p(x_{i})\cdot \log_{2}[p(x_{i})]. }\)

Zrobiłem to tak:
\(\displaystyle{
\sum_{1}^{16} \frac{1}{16} \cdot \log_{2} \frac{1}{16} = - \frac{1}{16} \cdot \left( -4\right) = \left( \frac{1}{4} \right)^{-1} = 4
}\)