Divisão exata e sequências geométricas

Question

Imagino que esse problema tenha um nome que não conheço; é provavelmente algum tipo de problema de divisão exata. Aqui vai: imagine que você deva dividir 4 biscoitos entre 11 pessoas. Divida os biscoitos igualmente entre as 11 pessoas, com a restrição de que você é um campeão mundial ao dividir os biscoitos pela metade. :-)

Então, naturalmente, você apenas divide todos os biscoitos pela metade até que haja mais pedaços do que pessoas e repita para cada novo tamanho. Com o caso (4, 11) acima, existem 4 peças para começar. Divida todos eles pela metade até que haja 16 pedaços e todos comam um pedaço. Sobram cinco pedaços, divide-os todos pela metade até ficarem 20, todo mundo come um ... essa é a idéia.

É ótimo que cada pessoa receba 1/4 + 1/16 + 1/32 + 1/64 + 1/256 + 1/4096 + 1/16384 + ... = 4/11 do total.

Mas a parte bonita - para mim! - é que a seqüência acima não é geométrica; são na verdade cinco sequências geométricas diferentes. (É assim que eu vejo, de qualquer maneira.) É 1/4 + 1/4096 + ... e 1/16 + 1/16384 + ... e assim por diante; cada uma das cinco sequências tem uma proporção comum de 1/1024, então é simples mostrar que a soma é exatamente 4/11.

Aqui está a parte do Mathematica. Com caneta e papel, demorou um pouco para perceber que os denominadores dos primeiros cinco termos acima são 4, 16, 32, 64, 256, e então a estrutura do problema se repete. Nesse ponto, o processo de duplicação dá o mesmo número de peças "restantes", de modo que esses cinco denominadores são a base da soma. Só para verificar, eu calculei

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

O resultado é, na verdade, 4/11. Doce. Da mesma forma, tentei dois outros casos: 3 cookies e 5 pessoas, bem como 5 cookies e 9 pessoas. O padrão até agora é este, onde a formatação é [cookies, pessoas] -> listOfPortions.

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

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

Cada caso "funciona" e cada pessoa acabaria com c / p como o valor total. Mas, apesar de ter três exemplos, não vejo um padrão explícito e acho que existem algumas maneiras de descrever o padrão. Eu poderia descrevê-lo em termos de porções reais ou poderia descrevê-lo com os expoentes de cada denominador. Portanto, neste ponto, tenho três perguntas:

• Este problema tem nome ?!

• Você tem dicas ou sugestões para uma função como portions[c, p, n]aquela que fornece os primeiros ntermos da sequência baseada em ccookies e ppessoas?

• Como você apresentaria esse problema a um grupo de alunos? Quais são seus pensamentos? Que outras funções ou cálculos você mostraria a eles?

A lógica é direta: dobre o número atual de peças até que exceda o número de pessoas, subtraia o número de pessoas desse número duplicado e repita. Mas não tenho certeza de como traduzir isso nos termos de uma sequência que somará c / p . Parece uma situação NestList[]ou NestWhileList[], mas ainda não a tenho.

Answer 1

A função a seguir fornece a solução completa para o 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}} *)

O primeiro número é a proporção comum das sequências, a lista fornece os números iniciais.

Para obter o primeiro $n$ termos por "força bruta", você pode usar o seguinte:

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

Basicamente, isso é usado NumberExpandpara obter a lista de frações. Uma vez que a função é projetada para inteiros, expandimos$\frac{c}{p}2^n$ e divida os termos por $2^n$novamente. O último termo é o resto fracionário, e é por isso que o abandonamos.

Derivação de solução completa

Aqui está como abordei isso: Para o seu exemplo 4/11, você descobriu 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 *)

Isso pode ser reescrito como uma única série geométrica com proporção $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 *)

Então, efetivamente, você encontrou uma maneira de escrever $\frac{1}{11}$ como uma série geométrica com proporção $2^{-n}$. Conhecendo a fórmula para a série geométrica, podemos reescrever o anterior como

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

Como você pode ver, o truque é escrever $11$ como $\frac{1023}{93}$, ou equivalente,

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

Isso significa que precisamos encontrar $n$ de tal modo que

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

Onde $p$é o número de pessoas. Felizmente, este problema já foi resolvido pelo teorema de Euler , que afirma que

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

Onde $\varphi(n)$é a função totient ( EulerPhi).

A última etapa restante é encontrar a escrita da fração (aqui $\frac{4\cdot 93}{1024}$) como soma dos termos com o formulário $\frac{1}{2^n}$. O numerador da fração é geralmente dado por

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

(Onde $c$ é o número de cookies e $p$o número de pessoas), e este é um inteiro graças ao teorema de Euler. Reescrevendo isso como uma soma de poderes de$2$(usando NumberExpand), obtemos o resultado final, que é implementado com o código na parte superior.

Answer 2

Tudo se resume a uma representação binária de 4/11, ou n / m se você tiver n cookies e m pessoas. Essa representação pode ter um número finito ou um número infinito de dígitos. Você obtém, por exemplo, 16 dígitos (começando do primeiro dígito diferente de zero) desta representação por:

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

o que significa que os primeiros dígitos da representação binária são: 0,01011101000101110 ... Isso diz a você, cada pessoa recebe:

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