3
$\begingroup$

I imagine this problem has a name that I don't know; it's probably some sort of exact division problem. Here goes: imagine you have to divide 4 cookies among 11 people. Divide the cookies equally among the 11 people with the constraint that you are a World Champion at halving cookies. :-)

So naturally, you just halve all the cookies until there are more pieces than people, then repeat for each new size. With the (4, 11) case above, there are 4 pieces to start. Halve them all until there are 16 pieces and everyone eats one piece. There are five pieces left over, halve them all until there are 20, everyone eats one...you get the idea.

It's lovely that each person will get 1/4 + 1/16 + 1/32 + 1/64 + 1/256 + 1/4096 + 1/16384 + ... = 4/11 of the total.

But the pretty part -- for me! -- is that the sequence above is not geometric; it's actually five different geometric sequences. (That's how I see it, anyway.) It's 1/4 + 1/4096 + ... and 1/16 + 1/16384 + ... and so on; each of the five sequences has a common ratio of 1/1024, so it's straightforward to show the sum is exactly 4/11.

Here's the Mathematica part. With pen & paper, it took a little playing around to realize that the denominators of the first five terms above are 4, 16, 32, 64, 256, and then the structure of the problem repeats. At that point, the doubling process gives the same number of "remaining" pieces, so those five denominators are the foundation of the sum. Just to check, I computed

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

The result is, in fact, 4/11. Sweet. Similarly, I tried two other cases: 3 cookies and 5 people as well as 5 cookies and 9 people. The pattern so far is this, where the formatting is [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, ...}

Each case "works," and each person would end up with c/p as the total amount. But despite having three examples, I don't see an explicit pattern, and I think there are few ways to describe the pattern. I could describe it in terms of the actual portions, or I could describe it with the exponents on each denominator. So at this point, I have three questions:

  • Does this problem have a name?!

  • Do you have hints or suggestions for a function like portions[c, p, n] that gives the first n terms of the sequence based on c cookies and p people?

  • How would you present this problem to a group of students? What are your thoughts? What other functions or computations would you show them?

The logic is straightforward: double the current number of pieces until it exceeds the number of people, subtract the number of people from that doubled number, and repeat. But I'm not sure how to translate that into the terms of a sequence that will sum to c/p. This feels like a NestList[] or NestWhileList[] situation, but I don't have it yet.

$\endgroup$
  • 1
    $\begingroup$ Tell them it's worms instead of cookies. Nobody will want them, and you won't spend now to infinity cutting things in half. $\endgroup$ – Daniel Lichtblau Sep 21 at 14:26
  • $\begingroup$ @DanielLichtblau I figure I'm the one holding the knife...I can keep them as cookies and have them all myself. :-) $\endgroup$ – mathalicious Sep 22 at 0:46
  • $\begingroup$ Holding the knife...yes, good point. $\endgroup$ – Daniel Lichtblau Sep 22 at 13:19
5
$\begingroup$

The following function gives the full solution to the problem:

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

The first number is the common ratio of the sequences, the list gives the starting numbers.

To get the first $n$ terms by "brute force", you can use the following:

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

This is essentially using NumberExpand to get the list of fractions. Since the function is designed for integers, we expand $\frac{c}{p}2^n$ and divide the terms by $2^n$ again. The last term is the fractional remainder, which is why we drop it.

Derivation of full solution

Here's how I approached this: For your 4/11 example, you have found that

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

This can be rewritten as a single geometric series with 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 *)

So effectively, you have found a way to write $\frac{1}{11}$ as a geometric series with ratio $2^{-n}$. Knowing the formula for the geometric series, we can rewrite the above as

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

As you can see, the trick is to write $11$ as $\frac{1023}{93}$, or equivalently,

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

This means that we need to find $n$ such that

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

where $p$ is the number of people. Luckily, this problem is already solved by Euler's theorem, which states that

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

where $\varphi(n)$ is the totient function (EulerPhi).

The last remaining step is then to find the write the fraction (here $\frac{4\cdot 93}{1024}$) as sum of terms with the form $\frac{1}{2^n}$. The numerator of the fraction is in general given by

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

(where $c$ is the number of cookies and $p$ the number of people), and this is an integer thanks to Euler's theorem. Rewriting this as a sum of powers of $2$ (using NumberExpand), we get the final result, which is implemented with the code at the top.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is really thorough, Lukas, and the link to Euler's theorem and EulerPhi[] is perfect. Thank you. $\endgroup$ – mathalicious Sep 21 at 13:37
6
$\begingroup$

It all boils down to a binary representation of 4/11, or n/m if you have n cookies and m people. This representation can have a finite number or infinite number of digits. You get e.g. 16 digits (starting from the first non-zero digit) of this representation by:

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

meaning the first few digits of the binary representation are: 0.01011101000101110... This tells you, each person gets:

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Oh jeez...yes, of course. It is precisely the binary representation. Thanks, Daniel. $\endgroup$ – mathalicious Sep 21 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.