Odhad zovšeobecneného narodeninového paradoxu podľa Halmosa

The joy of suddenly learning a former secret and the joy of suddenly discovering a hitherto unknown truth are the same to me -- both have the flash of enlightenment, the almost incredibly enhanced vision, and the ecstasy and euphoria of released tension.
P. Halmos, I want to be a Mathematician, 1985.

Moji študenti, teda aspoň tí, ktorí tesne pred hodinami so mnou nestrácajú chuť do života, poznajú maďarsko-amerického matematika Paula Halmosa. Niet totiž väčšej radosti ako tej, ktorú človek zažíva, keď rozochvenou rukou kreslí v pravom dolnom rohu dokončeného dôkazu "▯" - malý štvorček zvaný halmos, po Paulovi Halmosovi, ktorý túto grafickú skratku (významovo podobnú Q.E.D.) pomohol rozšíriť medzi matematikmi. A samozrejme, snažím sa, aby sme tých halmosov na matike mohli kresliť čo najviac.

Na Paula som pred pár dňami náhodou narazil pri krátkom texte J. D. Barrowa k narodeninovému paradoxu. Túto krásnu úlohu pokladám priam za kultúrne dedičstvo dvadsiateho storočia a tak sa jej venujem s každou študijnou skupinou, s ktorou narazíme na teóriu pravdepodobnosti. Barrow vo svojej knižke uvádza pekný odhad zovšeobecnenia úlohy, ktorý pochádza práve od Halmosa.

Nech nejaký parameter náhodne nadobúda n rôznych hodnôt (pri birthday probleme je n=365). Koľko ľudí treba náhodne vybrať, aby pravdepodobnosť výskytu aspoň dvojice s rovnakou hodnotou tohto parametru bola prinajmenšom 50%? Halmosov odhad je 1,18√n. Po tom, ako som si porovnal hodnoty z tohto vzorčeka s výpočtami pre niekoľko rôznych n sa mi vzorček páči ešte viac. Dúfam, že potešil aj Vás.

PS: Je strašne zaujímavé sledovať, ako takéto odhady vznikajú. Pamätám si, že nás na matfyze napríklad Chalmo učil robiť dolné a horné odhady zložitosti geometrických algoritmov. Ale keď pozerám na tohto Halmosa, tak nechápem, odkiaľ zbadal, že sa to správa takto "odmocninovo" a ako došiel na 1,18...