Matematické Fórum

check_drummer · 01. 09. 2012 22:46

Ahoj,
při řešení problému zde mě napadla tato úloha: Jaká je (pro pevné m přirozené) průměrná relativní četnost lichých čísel (označme tento počet jako $b(m)$ ) mezi čísly $a_i(m) := [ \frac{m}{2^i} ]$ pro i celé nezáporné takové, že $m\ge 2^i$ . Např. pro m=5 máme pro i=0,1,2 $a_i$ =5,2,1, tj. uvedená četnost je $\frac23$ . Obecně lze úlohu zformulovat tak, že položíme $c_n := \frac{\sum_{m=1}^{n}{b_i(m)}}{\sum_{m=1}^{n}{|\{a_i(m)\}|}}$ , což je průměrná četnost mezi čísly 1 až n a pak lze hledat hodnotu $L := \lim_{n \to \infty}{c_n}$ . Úkolem je tedy zjistit hodnotu L.
Alternativně lze zkoumat hodnotu $d_n := \frac {b_i(m)}{|\{a_i(m)\}|}$ a následně $K := \lim_{n \to \infty}{\frac{\sum_{j=1}^{n}d_i}{n}}$ a hledat hodnotu K.

Volněji lze úlohu zformulovat tak, že hledáme pravděpodobnost pro náhodné přirozené číslo m a náhodné i, pro které platí $m\ge 2^i$ , že $[ \frac{m}{2^i} ]$ je liché.

(Úlohu lze zobecnit a místo $2^i$ uvažovat libovolnou jinou rostoucí funkci a rovněž místo lichých čísel zkoumat obecně nějakou hodnotu zbytku modulo P pro nějaké přirozené P.)

anes · 02. 09. 2012 01:50 — Editoval anes (02. 09. 2012 01:52)

Ahoj, v tuhle dobu už se nechci moc rozepisovat a nejsem si úplně jistý, jak moc rozumím Tvé otázce, takže tenhle příspěvek ber spíš jako pokus o nasměrování (svedení z cesty? :) ) než o vyřešení.

Já si myslím, že odpověď na většinu tvých otázek je jedna polovina. Vybereme úplně náhodně $m$ (řekněme aspoň $\geq 16$ ). K němu bude existovat nějaké $i$ , že $2^i \leq m < 2^{i+1}$ .
Nevím, jestli to je zajímavé, ale pro sebe si kreslím číselnou osu se třemi body -- 0, 2^i, 2^{i+1}. Bod $m$ byl volený náhodně, takže ho nikam nezanáším, ale představuji si ho rovnoměrně rozmatlaný v tom patřičném intervalu.

Je jasné, že $\left\lfloor \frac{m}{2^i} \right\rfloor = 1$ je liché. Pro dělení nižšími mocninami dvojky už to ale bude s paritou 50 na 50 podle toho, jaké máme konkrétní $m$ .
Číslo $2^i+2^{i-1}$ rozdelí interval $[2^i, 2^{i+1})$ na dvě půlky a parita čísla $\left\lfloor \frac{m}{2^{i-1}} \right\rfloor$ bude záležet na tom, ve které z nich $m$ leží.
Když na osu přikreslíme násobky $2^{i-2}$ , interválky si zase rozpůlíme, a opět půlka odpovídá lichým chodnotám $\left\lfloor \frac{m}{2^{i-2}} \right\rfloor$ a půlka sudým...

Z toho bych soudil, že (pokud si nějak špatně nevykládám zápis) posloupnost $c_{2^n}$ půjde v limitě dost rychle k jedné polovině. Jak by ty hodnoty $c_n$ kolísaly mezi těmi mocninami dvojky chce ještě dopromyslet, nevidím teď, jestli by vůbec limita $c_n$ existovala.

... a pořád mám pocit, že to nějak moc komplikuji...

check_drummer · 02. 09. 2012 20:10

↑ anes:
Ahoj, mě právě teď napadlo uvažovat všechna m jako by byla psána ve dvojkové soustavě. Pak zkoumaným číslům odpovídá to, že "odřízneme" z čísla m posledních i číslic. Z toho už by skoro mohlo být zřejmé, že sudých bude stejně jako lichcých, protože mezi číslicemi čísel 1 až n se v jejich binárním zápisu bude objevovat 0 stejně často jako 1 (neuvažujeme-li ovšem první číslici, která je vždy 1).
Snad by se tato úvaha dala dotáhnout precizně do konce. Sice není tak pozdě, ale také už dnes nemám myšlenky na rozvádění dalších úvah. :-)

Matematické Fórum

#1 01. 09. 2012 22:46

Průměrná četnost lichých čísel v dané množině

#2 02. 09. 2012 01:50 — Editoval anes (02. 09. 2012 01:52)

Re: Průměrná četnost lichých čísel v dané množině

#3 02. 09. 2012 20:10

Re: Průměrná četnost lichých čísel v dané množině

Zápatí