Piles of Coins

Have an interesting puzzle? Let's hear it!

Piles of Coins

Before getting to the puzzle, there are a few things I would like to mention about it:
1. If at some point in solving this, you come across something that would be implausible or even impossible in reality, that's fine. This problem is not meant to be realistic.
2. This problem is meant to be solved entirely without a calculator (or other computational aids). There's a certain theorem involved in solving this problem that you'll have to look up if you've never seen it before (you'll likely recognize when you'll need to do this), but aside from that, electronic aids are unnecessary.
3. Yes, this problem is very contrived. That's because I wrote it with a certain fact in mind that can be used to simplify part of it.

You are playing a game with 32 rounds, numbered 0 through 31. In each round you are asked a question. If you get the question in round n correct, you receive $2^n$ coins (assume all coins are identical). You continue until you get a question wrong (you don't lose coins for getting a question wrong).

At the end of the game, you are told to put your coins into piles, with each pile containing the same number of coins. Let's call that number n. Having done this, you are then presented with (n-1)! coins and told to put them into n piles, each with the same number of coins. If you have exactly one coin left over upon doing this, you win n-1 coins. If not, you win nothing.

What is the maximum number of coins you can win
1) if you get every question right?
2) by getting any number of questions right? (you may have to look something up for this)

DeathRowKitty
Mathlete

Posts: 68
Joined: Fri Feb 11, 2011 8:38 am

Re: Piles of Coins

A hint since no one's responded:
Spoiler! :
You'll need Wilson's Theorem

DeathRowKitty
Mathlete

Posts: 68
Joined: Fri Feb 11, 2011 8:38 am

Re: Piles of Coins

I think the solution is:
Spoiler! :
I'll write the proof later, but I'm sure its 1

the proof:
Spoiler! :
I'll begin with the second part of the problem, where we have (n-1)! coins and are told to split them in n piles with the same number of coins.
The number of coins that we have left upon doing this is the remainder of dividing (n-1)! by n.
If n is not a prime number $(n-1)!\equiv 0 \ (mod \ n)$, thus if n is not a prime we won't get any coins as a reward.
Even more, if n is a prime number we have that $(n-1)!\equiv -1 \ (mod \ n)$, which means that the only way to have one coin left is when n is 2, and this will give us the great prize of 1 coin.
As whenever we answer a question correctly we get a power of 2 tokens (I'm calling this ones tokens to avoid confussion with the coins that are used later) we will always be able to distribute the tokens that we get in piles with 2 tokens in each pile.
This means that whenever we answer at least 1 question correctly we will be able to get our maximum reward.
Spoiler! :
The Spanish Inquisition

Clearly every even integer greater than 2 can be expressed as the sum of two primes.
I have discovered a truly wonderful proof of this proposition, but the signature is too small to contain it.

Ardilla
High School

Posts: 26
Joined: Fri Feb 11, 2011 6:15 pm
Location: Argentina

Re: Piles of Coins

Oops, I put the condition wrong for the second half of the problem. I meant n-1 coins left over. Bleh.

Your answer is correct for the problem I posted though...except that you'd need at least 2 questions right, since you can't split 1 coin into 1 pile and have 1 coin left over.

Edit: Not that it makes a difference, but
Spoiler! :
$(n-1)! \equiv 0 (\mbox{mod }n)$ for composite n is only true for sufficiently large n....where sufficiently large means greater than 4

DeathRowKitty
Mathlete

Posts: 68
Joined: Fri Feb 11, 2011 8:38 am

Re: Piles of Coins

DeathRowKitty wrote:Edit: Not that it makes a difference, but
Spoiler! :
$(n-1)! \equiv 0 (\mbox{mod }n)$ for composite n is only true for sufficiently large n....where sufficiently large means greater than 4

Oh, you are right, I completely forgot that case!!

I'll think the puzzle another time.
Spoiler! :
The Spanish Inquisition

Clearly every even integer greater than 2 can be expressed as the sum of two primes.
I have discovered a truly wonderful proof of this proposition, but the signature is too small to contain it.

Ardilla
High School

Posts: 26
Joined: Fri Feb 11, 2011 6:15 pm
Location: Argentina

Re: Piles of Coins

Ok, I don't have the answer yet, but I have the following:

Spoiler! :
Once you are presented with (n-1)! coins, using Wilson's Theorem, the only way to have n-1 coins left over is if n is a prime number, this means that we have to find the greatest prime number that divides the number of coins that we receive after answering the questions.

We do have the following:
Spoiler! :
after answering the questions we are left with
$\sum_{i=1}^n2^i=2^{n+1}-1$
where n is the number of questions that we answered correctly.
Now the only thing that we have to do to answer question 1) is find the greatest prime divisor of $2^{33}-1$.
For question 2), we have that $2^{31}-1$ is a mersenne prime number. I guess that this is the greater prime number that we can get, but I'm not sure.

Edit: I have the answer for 2)
Spoiler! :
We have the identity:
$2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+\ldots +2^{(b-1)a}$
Using this we have that:
$2^{33}-1=(2^{11}-1)(1+2^{11}+2^{22})$
Clearly both divisors are lesser than $2^{31}-1$
We also have that:
$2^{32}-1=(2^{8}-1)(1+2^{8}+2^{16}+2^{24})$
Again both divisors are lesser than $2^{31}-1$, and so this is the greater prime divisor that we will be able to find.
This means that the answer to 2) is that the greatest number of coins that you can get is $2^{31}-2$, and this is attained answering 31 questions correctly.

To answer 1) I have to factorize $2^{33}-1=(2^{11}-1)(1+2^{11}+2^{22})$, I'll do this later, maybe
Spoiler! :
The Spanish Inquisition

Clearly every even integer greater than 2 can be expressed as the sum of two primes.
I have discovered a truly wonderful proof of this proposition, but the signature is too small to contain it.

Ardilla
High School

Posts: 26
Joined: Fri Feb 11, 2011 6:15 pm
Location: Argentina

Re: Piles of Coins

Your answer to part 2 is correct. I think you misread how I labeled the rounds though for your answer to part 1. (I labeled them 0-31, not 1-32.)

Edit: Remember: these are meant to be solved with minimal calculation required. If you find yourself having to do tedious calculations on large numbers, you're either on the wrong track or making things too difficult on yourself.

DeathRowKitty
Mathlete

Posts: 68
Joined: Fri Feb 11, 2011 8:38 am