Kans deler is kwadraat

[Drieske]

Een uitdaging van meer kanstheoretische aard die ik tegenkwam: Zij n een natuurlijk getal strikt groter dan 1. Neem nu willekeurig 2 verschillende delers van n. Noem deze n₁ en n₂. Wat is de kans dat exact één van deze twee delers een "perfect" kwadraat is?

PS: voor de duidelijkheid: ik omschrijf het als een 'uitdaging', waarmee ik gewoon bedoel dat ikzelf het antwoord wel weet, denk ik, maar er hier graag over wou 'nadenken' en misschien komen tot een betere/mooiere oplossing.

[Erik Leppen]

Is 't de bedoeling dat we openlijk reageren?

Hoe dan ook. Ten eerste hangt die kans natuurlijk van n af, dus laten we die kans P(n) noemen of zoiets, dan is dat helder. Merk op dat n > 1 omdat n twee verschilende delers moet hebben. Merk ook op dat P(n) > 0 omdat 1 een kwadraat is.

Ten tweede is dit niet heel moeilijk uit te rekenen als we weten hoeveel delers n heeft en hoeveel er een kwadraat zijn.

Bijvoorbeeld, als n 15 delers heeft waarvan er 3 een kwadraat zijn, dan is de kans gewoon de kans op exact één witte knikker bij een trekking van twee knikkers uit drie witte plus twaalf zwarte zonder teruglegging. Dat is een kwestie van binomiale verdelingen. En dit valt te veralgemeniseren naar elk aantal delers en elk aantal kwadratische delers.

De uitdaging die rest is, hoeveel delers heeft n en hoeveel daarvan zijn een kwadraat. Ik zou gaan kijken naar de priemfactorisatie van n; een deler van n is een kwadraat dan en slechts dan als elke priemfactor een even aantal keer voorkomt. Volgens mij is het zelfs zo dat als ik m definieer als hieronder, dat dan het aantal kwadratische delers van n gelijk is aan het aantal delers van m, maar dat durf ik niet met zekerheid te stellen nog.

Definitie van m = m(n) uit n:

Zij

\(n = p_1^{e_1} \cdots p_k^{e_k}\)

met p_i priem, definieer dan

\(m := p_1^{\left| e_1/2 \right|} \cdots p_k^{\left| e_k/2 \right|}}\)

Hierbij is |x| de floor van x (weet de tex-code daar niet voor).

Nog geen hele oplossing, maar allicht voer voor discussie

[Drieske]

Uiteraard mag de (gedeeltelijke) oplossing gepost worden indien iemand een idee/suggestie heeft . Het leek me net 'leuk' om te zien wat anderen ervan maken.

Je opzet met ontbinding in priemfactoren is alvast een goede opzet vind ik. Dat was ook de mijne alleszins... Kun je voort?

[317070]

Een uitdaging van meer kanstheoretische aard die ik tegenkwam: Zij n een natuurlijk getal strikt groter dan 1. Neem nu willekeurig 2 verschillende delers van n. Noem deze n₁ en n₂. Wat is de kans dat exact één van deze twee delers een "perfect" kwadraat is?

Ik heb er eventjes over zitten nadenken, maar er is volgens mij iets mis met de vraag. Je kunt namelijk geen willekeurig natuurlijk getal nemen, toch? Hoe definieer je je 'kans' dan?

[Rogier]

Ik heb er eventjes over zitten nadenken, maar er is volgens mij iets mis met de vraag. Je kunt namelijk geen willekeurig natuurlijk getal nemen, toch? Hoe definieer je je 'kans' dan?

Kansreken-technischerwijs kun je niet zeggen "zij n een willekeurig natuurlijk getal, wat is de kans dat n even is" maar je voelt intuïtief aan dat dit 1/2 moet zijn.

Wellicht moet je in zo'n situatie een extra voorwaarde n < N denken, of in Drieske's geval n1 en n2 < N, en dan de limiet voor N naar oneindig nemen.

[Erik Leppen]

Ik heb er eventjes over zitten nadenken, maar er is volgens mij iets mis met de vraag. Je kunt namelijk geen willekeurig natuurlijk getal nemen, toch? Hoe definieer je je 'kans' dan?

Er wordt toch geen willekeurig natuurlijk getal genomen? Er staat alleen dat n een natuurlijk getal is. Hoe n gevonden is doet er verder niet toe. Vervolgens wordt gevraagd op de kans dat van twee willekeurig gekozen verschillende delers van n er precies één een zuiver kwadraat is. Ik concludeer daaruit dat de gevraagde kans dus van n moet afhangen. We krijgen dus een functie van de natuurlijke getallen (groter dan 1) naar [0, 1]. En die is goed gedefinieerd, want n heeft slechts eindig veel delers en je kan dus een uniforme verdeling definiëren op alle paren van verschillende delers, en daaruit één paar aselect kiezen.

Nemen we bijvoorbeeld n = 3, dan heeft n twee delers, 1 en 3. Daarvan is 1 een zuiver kwadraat en 3 niet. De enige manier om twee verschillende delers te kiezen is om 1 en 3 te kiezen, en daarvan is er precies één een kwadraat. Oftewel, P(3) = 1.

Verder wat ik nog bedacht wat interessant is, is dat als je de priemontbinding van n hebt,

\(n = p_1^{e_1} \cdots p_k^{e_k}\)

dan hangt het kwadraat-zijn van delers, alsmede het aantal delers, alleen af van k en de e_i. Wat de p_i zijn is niet belangrijk. Oftewel, P(2⁴ 3³ 7¹) = P(17⁴ 5³ 2¹), want de exponenten zijn gelijk.

Dus als p priem is, is P(p) = 1

Kun je voort?

Volgens mij kun je dit allemaal best uitrekenen. Alleen heb ik het idee dat het heel lelijk wordt. Het zou meer een algoritme worden dan een enkele formule volgens mij. De functie voor het aantal delers van n (gegeven de priemfactorisatie) is al een heel ding. Voortschrijdende inzichten van anderen zijn zeker gewenst

[Drieske]

Ik begrijp ook niet volledig wat volgens jullie de 'dubbelzinnigheid' is . Ik dacht namelijk hetzelfde als Erik reeds zei. Mis ik iets? Misschien kun je het verduidelijken adhv een voorbeeld ofzo?

[kee]

Ik had het bij het lezen ook anders geïnterpreteerd, net zoals 317070 en Rogier, en kwam tot hetzelfde probleem met de vraag. Wij interpreteren de vraag als de vraag naar een kans die niet afhangt van n, maar nu ik goed kijk wat er staat 'zij n een natuurlijk getal', is de interpretatie als een kans die afhangt van n dan idd de correcte. Alleen volgt de oplossing dan denk ik vrij rechtstreeks uit de priemfactorisatie (mss daarom dat we het anders interpreteerden om er een grotere uitdaging van te maken).

Maar om dan het afhankelijk te maken van n.

Het aantal delers van

\(n = p_1^{e_1} \cdots p_k^{e_k}\)

(ontbinding in priemfactoren

\(p_i\)

en

\(p_i\neq p_j\)

voor

\(i\neq j\)

) is

\(\prod_{i=1}^k(e_i+1)\)

. Het aantal delers dat een volkomen kwadraat is is

\(\prod_{i=1}^k\left\lfloor e_i/2+1\right\rfloor\)

. Klopt dit?

[kee]

Correctie: ik bedoel het aantal verschillende positieve delers. Geldt dit ook voor je vraagstuk?

[Drieske]

Dit klopt al ja . Of beter: ik had hetzelfde (heb ook geen 'officiële oplossing'). Maar dat geeft je nog niet de kans, hè... Wel quasi uiteraard .

[kee]

(Uitgaande van positieve delers in de vraagstelling), noem a het in de vorige post berekende aantal delers van n en b het aantal delers daarvan dat een volkomen kwadraat is.

De gevraagde kans wordt dan als ik mij niet vergis

\(P(n)=2\cdot\frac{b(a-b)}{a(a-1)}\)

.

Heb ik een boom voor getekend (ben niet zo heel goed in die dingen en met een boom dan minder kans op redeneerfouten, en aangezien die nu maar vier blaadjes heeft).

Geldt voor elk natuurlijk getal n groter dan 1 gezien elk natuurlijk getal groter dan 1 minstens twee verschillende positieve delers heeft.

Is dit wat je ook hebt?

[Drieske]

Sorry voor het late antwoord. Beetje uit het oog verloren . Dat is inderdaad de kans die je moet bekomen.

Je kunt ze ook exact berekenen. Je moet, mocht je willen, maar eens denken over P(kwadraat daarna niet-kwadraat).