Gondoltam egy egész számra 0 és végtelen között. Milyen módszer szerint érdemes tippelgetni, ha a tipp végén mindig megmondom, hogy kisebb volt-e vagy nagyobb?

A végtelen nem egy szám, pusztán annak jellegnek a leírása, hogy valami bármely véges számnál nagyobb.

Ha véges az intervallum és véletlenszám generátorod eloszlása egyenletes, akkor triviális út az intervallumfelezéses módszer.

Ha véges az intervallum és a véletlenszám generátorod nem egyenletes eloszlású, akkor az eloszlásfüggvény alapján meg lehet határozni, hogy melyik az a szám, ami esetén 50% eséllyel a gondolt szám kisebb, 50% eséllyel a gondolt szám nagyobb.

Ha végtelen az intervallum, és a véletlenszám generátorod nem egyenletes eloszlású, akkor lehet olyan helyzet, mikor tudsz olyan véges számot mondani, aminél 50% az esélye, hogy a gondolt szám kisebb, 50% az esélye, hogy nagyobb. Mondok erre egy példát… Generálsz egy egyenletes eloszlású valós számot [0;90] intervallumban. Legyen ez „a”. Aztán ebből generálsz egy „x” számot, ahol:

x = 100*tan(a)

(Ahol itt most a fokban van megadva.)

Így tudsz generálni egy valós véletlen számot 0 és végtelen között, csak éppen nem egyenletes eloszlással. Ezt a valós véletlen számot lefele kerekítve kapsz egy természetes számot. És bár az intervallum végtelen, mégis működik az intervallumfelezés, hiszen tudni fogjuk, hogy 50% eséllyel a számod 100-nál (100*tan(90°-90°/2)=100) kisebb lesz, 50% eséllyel 100 vagy annál nagyobb. Ha ez utóbbi eset áll fenn, akkor is tudni fogjuk, hogy a számod kb. 50% eséllyel esik a [101;241] intervallumba, és közel 50% eséllyel esik a [242;∞] intervallumba (100*tan(90°-90°/4)=241,42). Ha ez utóbb a helyzet, akkor a következő tippnél tudni fogjuk, hogy a számod közel 50% eséllyel fog a [243;502] intervallumba esni, és közel 50% eséllyel fog a [503;∞] intervallumba esni (100*tan(90°-90°/8)=502,73).

Gyakorlatilag itt tulajdonképpen „a”-t fogod intervallumfelezéssel kitalálni, és alkalmazni rá azt a függvényt, ami aztán előállítja a gondolt számot, annak az eloszlásával. És már itt probléma van. Ugyanis szélsőséges esetben egy 90-hez nagyon közeli számot is generálhatsz. Azt mondod, hogy 2 lépés? Tudok olyan 90-nél kisebb „a”-t mondani, amikor továbbra is egy végtelen intervallumban kell találgatnod. Azt mondod, hogy 10 lépés? Megint tudok egy 90-nél kisebb „a”-t mondani, amikor továbbra is egy végtelen intervallumban kell találgatnod. Bármilyen véges lépésszámot mondasz, tudok mondani egy olyan minimális „a”-t mondani, ami esetén továbbra is egy végtelen intervallumban kell eltalálnod a generált számot.

Persze minél nagyobb „n”-t mondok, annál kisebb a valószínűsége, hogy mindig csökken az esélye annak, hogy a gondolt számot nem tudod „n” lépésből kitalálni, de mindig 0-nál nagyobb lesz a valószínűsége, hogy a szám „n” lépésből – kettő, száz, egymillió, googolplex, Graham-szám darab lépésszámból – még mindig nem található ki.

~ ~ ~

És akkor jön az alapeseted, ami azt feltételezi, hogy – mivel nincs kimondva, ez az alapfeltételezés – a véletlenszám generátorod egyenletes eloszlású. És ez végtelen intervallumban eleve problémás. Hiszen ha azt mondom, hogy 2, akkor elmondható, hogy végtelenszer több természetes szám nagyobb 2-nél, mint amennyi kisebb. Azt mondom, hogy 1000? Akkor elmondható, hogy végtelenszer több 1000-nél nagyobb természetes szám van, mint kisebb. Azt mondom, hogy Graham-szám? Elmondható, hogy végtelenszer több Graham-számnál nagyobb természetes szám van, mint kisebb. Bármilyen nagy valós számot is mondasz, mindig igaz lesz, hogy nálánál végtelenszer több véges természetes szám van, mint kisebb.

Anno egyébként bennem is felmerült a gondolat, hogy lehet-e olyan véletlenszám generátort kreálni, ami 0 – vagy 1 – és végtelen között egyenletes eloszlással generált véletlen számot. Hát nem igazán…

~ ~ ~

Másik oldalról ha van egy ilyen gondolt számod, az potenciálisan egy végtelen elemszámú halmaz egyik eleme. Egy végtelen halmazt meg ha két részhalmazra bontasz, akkor a részhalmazok ugyanúgy végtelen halmazt alkotnak, sőt a számosságuk is azonos marad. Osztással nem lehet elhagyni egy számosságot. Véges lépésben legalábbis biztos, hogy nem.

~ ~ ~

Tehát ha nem foglalkozunk a fizikai korlátokkal – hogy ismerned kellene a számod összes számjegyét, nekem el kellene mondanom a tippelt számot, ami nyilván korlátot jelent –, valamint feltételezzük, hogy valahogy mégis sikerült egyenletes eloszlású véletlent generálnod, akkor arra a kérdésre, hogy milyen módszerrel érdemes tippelni, a legjobb válasz az, hogy semmilyennel. Ha belemész a tippelgetésbe, bármilyen módszert is találsz ki, véges idő alatt nem fogod kitalálni a számot. Tehát teljesen mindegy, hogy milyen módszert használsz, attól még jó eséllyel továbbra is végtelen intervallum marad, amibe a gondolt számod esik.

> Akkor lezárhatjuk azzal a kérdést, hogy a fent vázolt problémám ekvivalens a "Gondoltam egy racionális számra a [0;1] intervallumban..." játékhoz?

Bizonyos nézőpontból igen.

Bizonyos nézőpontból meg ha belegondolunk, akkor inkább a „gondoltam egy racionális számra” játék vezethető vissza a „gondoltam egy természetes számra 1 és végtelen között” esetére, hiszen egy racionális szám két egész szám hányadosa, ahol a számláló és a nevező tetszőlegesen nagy szám lehet, csak legyenek relatív prímek. Kvázi bármelyik n/(n+1) tovább nem egyszerűsíthető racionális szám lesz, amiből végtelen sok létezik, tetszőlegesen nagy „n”-nel. És ez még csak egy igen szűk részhalmaza a racionális számoknak.

Szerintem közelítsük meg gyakorlati szempontból a kérdést.

Áruld el először is, hogy milyen módszerrel hasonlítod össze a gondolt számot a tippjeimmel!

Ilyen nem megfelelő megfogalmazás hogy "Így tudsz generálni egy valós véletlen számot 0 és végtelen között, csak éppen nem egyenletes eloszlással." mivel eloszlása valószínűségi változónak van nem számnak. Továbbá a [0;90] intervallum se helyes abba a tangeses példába, hanem [0;90[ lenne, mivel a 90 az nem eleme az eseménytérnek, vagyis nem eleme a halmaznak.

Egyébként meg szerintem ki van "vesézve" a kérdés.