6
$\begingroup$

tl;dr.: Is there any number for which $2^{i}\mod 3 = 0$ where $i \in \mathbb{N}$

Some friends and I made a bet recently. Basically, if you are 3 persons who are to share a pizza, and you start out by cutting it into 4 even sized pieces, can you ever keep doubling the number of slices so that everyone will be able to pick up the same amount of pieces and get the same amount of pizza?

We did some mathematics on this ourselves, but seeing as we're all IT-engineers, our math skills are quite rusty :) We did come up with a small application to check it out, and it seems that there is no solution for $i < 1000$ or so. However, we're not quite satisfied with this solution. Can anyone provide a proof that it will never happen (or the opposite)? :)

English is not my first language, so I might not have been able the formulate the question clear enough. If more information is needed, please ask :)

  • 0
    Also, in the future, please try to use titles for your posts that help people browsing the titles to decide whether they might be able to help in your question. Eg. here you could use the title “Is there a power of two divisible by three?” or “Splitting pizza to three people evenly by repeatedly halving slices”.2012-03-04

3 Answers 3

10

No, you can't, because the decomposition of a number into primes is unique and a $3$ does not appear in the prime decomposition of $2^i$.

5

On the other hand, if you're willing to cut infinitely often, you cut the pizza into four equal pieces, then take one piece each, and repeat with the remaining piece. If you do this exponentially faster you can finish the pizza in a finite amount of time.

  • 2
    O$n$ the other other hand, if you're willing to allow an infinite amount of toppings on your pizza... (^^ ?!?!)2011-10-14
4

For an argument without appealing to prime factorization, just note the following fact: the product of two odd numbers is odd.

Now suppose that we could write $2^i = 3n$ for some integer $n$. $2^i$ is clearly even, so $n$ must be even: $n = 2m$ for some integer $m$. Therefore, dividing both sides by 2, we have $2^{i-1} = 3m$, so $2^{i-1}$ can also be written as a multiple of 3. Repeating this process $i$ times, we find that $2$ can be written as a multiple of $3$, which is absurd.