Divisione esatta e sequenze geometriche

Question

Immagino che questo problema abbia un nome che non conosco; probabilmente è una sorta di problema di divisione esatta. Ecco qui: immagina di dover dividere 4 biscotti tra 11 persone. Dividi i biscotti equamente tra le 11 persone con il vincolo di essere un Campione del Mondo a dimezzare i biscotti. :-)

Quindi, naturalmente, devi solo dimezzare tutti i biscotti finché non ci sono più pezzi che persone, quindi ripetere per ogni nuova dimensione. Con il caso (4, 11) sopra, ci sono 4 pezzi per iniziare. Tagliali a metà finché non ci sono 16 pezzi e tutti ne mangiano un pezzo. Ci sono cinque pezzi rimasti, dimezzali tutti fino a quando non sono 20, tutti ne mangiano uno ... hai capito.

È bello che ogni persona riceva 1/4 + 1/16 + 1/32 + 1/64 + 1/256 + 1/4096 + 1/16384 + ... = 4/11 del totale.

Ma la bella parte - per me! - è che la sequenza sopra non è geometrica; in realtà sono cinque diverse sequenze geometriche. (È così che la vedo io, comunque.) È 1/4 + 1/4096 + ... e 1/16 + 1/16384 + ... e così via; ciascuna delle cinque sequenze ha un rapporto comune di 1/1024, quindi è semplice mostrare che la somma è esattamente 4/11.

Ecco la parte Mathematica. Con carta e penna, ci è voluto un po 'di tempo per capire che i denominatori dei primi cinque termini sopra riportati sono 4, 16, 32, 64, 256, e quindi la struttura del problema si ripete. A quel punto, il processo di raddoppio dà lo stesso numero di pezzi "rimanenti", quindi quei cinque denominatori sono il fondamento della somma. Solo per controllare, ho calcolato

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

Il risultato è, infatti, 4/11. Dolce. Allo stesso modo, ho provato altri due casi: 3 biscotti e 5 persone, 5 biscotti e 9 persone. Lo schema finora è questo, dove la formattazione è [cookies, people] -> listOfPortions.

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

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

Ogni caso "funziona" e ogni persona finirebbe con c / p come importo totale. Ma nonostante abbia tre esempi, non vedo uno schema esplicito e penso che ci siano pochi modi per descrivere lo schema. Potrei descriverlo in termini di porzioni effettive, oppure potrei descriverlo con gli esponenti su ogni denominatore. Quindi, a questo punto, ho tre domande:

• Questo problema ha un nome ?!

• Hai suggerimenti o suggerimenti per una funzione come portions[c, p, n]quella che fornisce i primi ntermini della sequenza in base ai ccookie e alle ppersone?

• Come presenteresti questo problema a un gruppo di studenti? Quali sono i tuoi pensieri? Quali altre funzioni o calcoli gli mostrereste?

La logica è semplice: raddoppia il numero corrente di pezzi finché non supera il numero di persone, sottrai il numero di persone da quel numero raddoppiato e ripeti. Ma non sono sicuro di come tradurlo nei termini di una sequenza che si sommerà in c / p . Sembra una situazione NestList[]o NestWhileList[], ma non ce l'ho ancora.

Answer 1

La seguente funzione fornisce la soluzione completa al problema:

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}} *)

Il primo numero è il rapporto comune delle sequenze, l'elenco fornisce i numeri di partenza.

Per ottenere il primo $n$ termini per "forza bruta", puoi utilizzare quanto segue:

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} *)

Questo è essenzialmente utilizzato NumberExpandper ottenere l'elenco delle frazioni. Poiché la funzione è progettata per numeri interi, ci espandiamo$\frac{c}{p}2^n$ e dividi i termini per $2^n$ancora. L'ultimo termine è il resto frazionario, motivo per cui lo eliminiamo.

Derivazione della soluzione completa

Ecco come mi sono avvicinato a questo: per il tuo esempio dell'11 / 4, l'hai trovato

$$\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 *)

Questo può essere riscritto come una singola serie geometrica con rapporto $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 *)

In modo così efficace, hai trovato un modo per scrivere $\frac{1}{11}$ come una serie geometrica con rapporto $2^{-n}$. Conoscendo la formula per la serie geometrica, possiamo riscrivere quanto sopra come

$$\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}$$

Come puoi vedere, il trucco sta nello scrivere $11$ come $\frac{1023}{93}$, o equivalentemente,

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

Ciò significa che dobbiamo trovare $n$ tale che

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

dove $p$è il numero di persone. Fortunatamente, questo problema è già risolto dal teorema di Eulero , che lo afferma

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

dove $\varphi(n)$è la funzione totient ( EulerPhi).

L'ultimo passaggio rimanente è quindi trovare la scrittura della frazione (qui $\frac{4\cdot 93}{1024}$) come somma dei termini con il modulo $\frac{1}{2^n}$. Il numeratore della frazione è generalmente dato da

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

(dove $c$ è il numero di cookie e $p$il numero di persone), e questo è un numero intero grazie al teorema di Eulero. Riscrivendolo come somma di poteri di$2$(utilizzando NumberExpand), otteniamo il risultato finale, che viene implementato con il codice in alto.

Answer 2

Il tutto si riduce a una rappresentazione binaria di 4/11, o n / m se hai n cookie em persone. Questa rappresentazione può avere un numero finito o un numero infinito di cifre. Ottieni ad esempio 16 cifre (a partire dalla prima cifra diversa da zero) di questa rappresentazione da:

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

il che significa che le prime cifre della rappresentazione binaria sono: 0.01011101000101110 ... Questo ti dice che ogni persona ottiene:

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