matematikk.net

Gravde litt i noen gamle tråder og fant en morsom oppgave opprinnelig av daofeishi:

Definer en egoistisk mengde som en mengde som har sin egen kardinalitet (antall elementer i mengden) som element. Finn antall undermengder av {1, 2, ... n} som er minimale egoistiske mengder, altså egoistiske mengder som ikke har undermengder som er egoistiske.

La S være en egoistisk delmengde med kardinalitet K. La det minste elementet i S være M.

Dersom M<K kan vi fjerne K-M elementer fra S\{M} slik at vi får en ekte egoistisk delmengde av S. Ergo er S ikke minimal.


Så dersom S skal være minimal må K være det minste elementet i S og da må K<n/2+1.

Antallet minimale ekte ikketomme egoistiske delmengder blir derfor [tex]\sum_{k=1}^{<\frac{n}{2}+1}\frac{(n-k)!}{(n-k-(k-1))!(k-1)!}[/tex]

Ja, det stemmer det, men kan du finne den på en mye finere form?

Er verdt å nevne i hvert fall.

Antall minimale egoistiske mengder er faktisk fibonaccitallene.