Losowanie za pomocą monety

[agusiaczarna22]

Jak wylosować z s wyrazowej populacji element za pomocą monety,
gdy:
a) s = 5,
b) s = 13,
c) s = 32.
d) s = 128,
e) s = 1000, s = 1001?.
Jak element ten można losować za pomocą kostki sześciennej, a jak za pomocą
dwudziestościanu foremnego?

[Panko]

jeżeli \(s=2^n\) to wykonujemy n krotny rzut monetą
c) \(32=2^5\)\(\\)\(\\)d) \(128=2^7\)
Każdy wynik to n wyrazowy ciąg orłów i reszek , ten wynik adresuje jednoznacznie liczbę naturalną ze zbioru \(\left\{ 1,2,....,2^n\right\}\)
Idea jest taka : dziel aktualny zbiór na połowy i jeżeli wypadł orzeł to wybierasz <dolną > połowę , jeżeli reszka to <górną> połowę. ( to da się zrobić bo \(s=2^n\)) . Warunek Stopu dzielenia i wybierania połówek aktualnego zbioru to długość wybranej połówki .
Koniec podziałów jest w momencie kiedy wybrana połówka ma długość \(1\) czyli jeden element, i on jest właśnie adresatem danego ciągu orłów i reszek

NP : \(Z=\left\{ 1,2,3,4\right\}\) czyli \(s=2^2\) , każda z liczb zbioru \(Z\) jest jednoznacznie adresowana przez ciąg 2-wyrazowy orłów i reszek
\((O,O) \to 1\) , \((O,R) \to2\) ,\((R,O) \to 3\) ,\((R,R) \to 4\)

NP : \(Z=\left\{ 1,2,3,4,5,6,7,8\right\}\) czyli \(s=2^3\) , każda z liczb zbioru \(Z\) jest jednoznacznie adresowana przez ciąg 3-wyrazowy orłów i reszek
\((O,O,O) \to 1\) ,\((O,O,R) \to 2\) , \((O,R,O) \to 3\) , \((R,O,O) \to 5\) , \((R,R,O) \to 7\)....

[agusiaczarna22]

A jak pozostałe zrobić?:)