Division exacte et séquences géométriques

Question

J'imagine que ce problème a un nom que je ne connais pas; c'est probablement une sorte de problème de division exacte. Voilà: imaginez que vous devez répartir 4 biscuits entre 11 personnes. Répartissez les cookies de manière égale entre les 11 personnes avec la contrainte que vous êtes un champion du monde de réduction de moitié des cookies. :-)

Alors naturellement, vous divisez par deux tous les biscuits jusqu'à ce qu'il y ait plus de morceaux que de personnes, puis répétez pour chaque nouvelle taille. Avec le boîtier (4, 11) ci-dessus, il y a 4 pièces pour commencer. Coupez-les tous de moitié jusqu'à ce qu'il y ait 16 morceaux et que tout le monde en mange un. Il reste cinq morceaux, divisez-les par deux jusqu'à ce qu'il y en ait 20, tout le monde en mange un ... vous voyez l'idée.

C'est bien que chaque personne obtienne 1/4 + 1/16 + 1/32 + 1/64 + 1/256 + 1/4096 + 1/16384 + ... = 4/11 du total.

Mais la jolie partie - pour moi! - est que la séquence ci-dessus n'est pas géométrique; il s'agit en fait de cinq séquences géométriques différentes. (C'est comme ça que je le vois, de toute façon.) C'est 1/4 + 1/4096 + ... et 1/16 + 1/16384 + ... et ainsi de suite; chacune des cinq séquences a un rapport commun de 1/1024, il est donc simple de montrer que la somme est exactement de 4/11.

Voici la partie Mathematica. Avec un stylo et du papier, il a fallu un peu de jeu pour se rendre compte que les dénominateurs des cinq premiers termes ci-dessus sont 4, 16, 32, 64, 256, puis la structure du problème se répète. À ce stade, le processus de doublement donne le même nombre de pièces «restantes», de sorte que ces cinq dénominateurs sont le fondement de la somme. Juste pour vérifier, j'ai calculé

Total[
 Sum[1/2^# (1/2^10)^n, {n, 0, Infinity}] & /@ {2, 4, 5, 6, 8}
 ]

Le résultat est, en fait, 4/11. Doux. De même, j'ai essayé deux autres cas: 3 cookies et 5 personnes ainsi que 5 cookies et 9 personnes. Le modèle jusqu'à présent est le suivant, où le formatage est [cookies, personnes] -> listOfPortions.

[3, 5] -> {1/2, 1/16, 1/32, 1/256, ...}

[5, 9] -> {1/2, 1/32, 1/64, 1/128, 1/2048, ...}

Chaque cas «fonctionne», et chaque personne se retrouverait avec c / p comme montant total. Mais malgré trois exemples, je ne vois pas de modèle explicite et je pense qu'il y a peu de façons de décrire le modèle. Je pourrais le décrire en termes de portions réelles, ou je pourrais le décrire avec les exposants de chaque dénominateur. Donc, à ce stade, j'ai trois questions:

• Ce problème a-t-il un nom?!

• Avez-vous des conseils ou des suggestions pour une fonction comme portions[c, p, n]celle qui donne les premiers ntermes de la séquence basée sur les ccookies et les ppersonnes?

• Comment présenteriez-vous ce problème à un groupe d'étudiants? Quelles sont vos pensées? Quelles autres fonctions ou calculs voudriez-vous leur montrer?

La logique est simple: doubler le nombre actuel de pièces jusqu'à ce qu'il dépasse le nombre de personnes, soustraire le nombre de personnes de ce nombre doublé et recommencer. Mais je ne sais pas comment traduire cela dans les termes d'une séquence qui résultera en c / p . Cela ressemble à une situation NestList[]ou NestWhileList[], mais je ne l'ai pas encore.

Answer 1

La fonction suivante donne la solution complète au problème:

cookieHalves[c_Integer, p_Integer] /; 
  CoprimeQ[2, p](* Euler's theorem only holds for 2 and p comprime *):=

  Module[
  {
   ratio = 2^EulerPhi[p]
   },
  {1/ratio, DeleteCases[0]@NumberExpand[(ratio - 1) c/p, 2]/ratio}
  ]
cookieHalves[c_Integer, p_Integer] := cookieHalves[c, p/2]/{1, 2}

cookieHalves[4, 11]
(* {1/1024, {1/4, 1/16, 1/32, 1/64, 1/256}} *)

cookieHalves[3, 5]
(* {1/16, {1/2, 1/16}} *)

cookieHalves[5, 9]
(* {1/64, {1/2, 1/32, 1/64}} *)

Le premier nombre est le rapport commun des séquences, la liste donne les nombres de départ.

Pour obtenir le premier $n$ termes par "force brute", vous pouvez utiliser ce qui suit:

cookieHalves[c_, p_, n_] := Most@NumberExpand[c/p*2^n, 2, n + 1]/2^n

cookieHalves[4, 11, 12]
(* {1/4, 0, 1/16, 1/32, 1/64, 0, 1/256, 0, 0, 0, 1/4096, 0} *)

cookieHalves[3, 5, 12]
(* {1/2, 0, 0, 1/16, 1/32, 0, 0, 1/256, 1/512, 0, 0, 1/4096} *)

cookieHalves[5, 9, 12]
(* {1/2, 0, 0, 0, 1/32, 1/64, 1/128, 0, 0, 0, 1/2048, 1/4096} *)

Ceci est essentiellement utilisé NumberExpandpour obtenir la liste des fractions. Puisque la fonction est conçue pour les entiers, nous développons$\frac{c}{p}2^n$ et divisez les termes par $2^n$de nouveau. Le dernier terme est le reste fractionnaire, c'est pourquoi nous le supprimons.

Dérivation de la solution complète

Voici comment j'ai abordé ceci: Pour votre exemple 4/11, vous avez trouvé que

$$\begin{align} \frac{4}{11}&=\left(\frac{1}{4}\frac{1}{1024}+\frac{1}{4}\frac{1}{1024^2}+\cdots\right)\\ &+\left(\frac{1}{16}\frac{1}{1024}+\frac{1}{16}\frac{1}{1024^2}+\cdots\right)\\ &+\left(\frac{1}{32}\frac{1}{1024}+\frac{1}{32}\frac{1}{1024^2}+\cdots\right)\\ &+\left(\frac{1}{64}\frac{1}{1024}+\frac{1}{64}\frac{1}{1024^2}+\cdots\right)\\ &+\left(\frac{1}{256}\frac{1}{1024}+\frac{1}{256}\frac{1}{1024^2}+\cdots\right) \end{align}$$

Sum[Sum[1/n 1/1024^i, {i, 0, ∞}], {n, {4, 16, 32, 64, 256}}]
(* 4/11 *)

Cela peut être réécrit comme une seule série géométrique avec ratio $1024$:

$$\begin{align} \frac{4}{11}&=\left(\frac{1}{4}+\frac{1}{16}+\frac{1}{32}+\frac{1}{64}+\frac{1}{256}\right)\left(\frac{1}{1024}+\frac{1}{1024^2}+\cdots\right)\\ &=\frac{93}{256}\left(\frac{1}{1024}+\frac{1}{1024^2}+\cdots\right)\\ &=4\frac{93}{1024}\left(\frac{1}{1024}+\frac{1}{1024^2}+\cdots\right) \end{align}$$

1/4 + 1/16 + 1/32 + 1/64 + 1/256
(* 93/256 *)

Si efficacement, vous avez trouvé un moyen d'écrire $\frac{1}{11}$ sous forme de série géométrique avec ratio $2^{-n}$. Connaissant la formule de la série géométrique, nous pouvons réécrire ce qui précède comme

$$\begin{align} \frac{4}{11}&=4\frac{93}{1024}\frac{1}{1-\frac{1}{1024}}\\ &=4\frac{93}{1024}\frac{1024}{1024-1}\\ &=4\frac{93}{1024}\frac{1024}{1023}\\ &=4\frac{93}{1024}\frac{1024}{93\cdot11}\\ \end{align}$$

Comme vous pouvez le voir, le truc est d'écrire $11$ comme $\frac{1023}{93}$, ou équivalent,

$$2^{10}-1=11\cdot 93$$

Cela signifie que nous devons trouver $n$ tel que

$$2^n-1\equiv0\ \mod p$$

où $p$est le nombre de personnes. Heureusement, ce problème est déjà résolu par le théorème d' Euler , qui stipule que

$$2^{\varphi(p)}-1\equiv0\ \mod p$$

où $\varphi(n)$est la fonction totient ( EulerPhi).

La dernière étape restante est alors de trouver l'écriture de la fraction (ici $\frac{4\cdot 93}{1024}$) comme somme de termes avec le formulaire $\frac{1}{2^n}$. Le numérateur de la fraction est en général donné par

$$2^{\varphi(p)}\frac{c}{p}$$

(où $c$ est le nombre de cookies et $p$le nombre de personnes), et c'est un entier grâce au théorème d'Euler. Réécrire ceci comme une somme de pouvoirs de$2$(en utilisant NumberExpand), nous obtenons le résultat final, qui est implémenté avec le code en haut.

Answer 2

Tout se résume à une représentation binaire de 4/11, ou n / m si vous avez n cookies et m personnes. Cette représentation peut avoir un nombre fini ou un nombre infini de chiffres. Vous obtenez par exemple 16 chiffres (à partir du premier chiffre différent de zéro) de cette représentation par:

RealDigits[4/11, 2, 16]
(*{{1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0}, -1}*)

ce qui signifie que les premiers chiffres de la représentation binaire sont: 0.01011101000101110 ... Cela vous dit que chaque personne obtient:

1/4 + 1/16 + 1/32 + 1/64 + ... biscuits