Author |
Topic: Coin Tossing Puzzle (Read 1661 times) |
|
Wonderer
Newbie
Posts: 18
|
 |
Coin Tossing Puzzle
« on: Dec 30th, 2005, 2:03am » |
 Quote  Modify
|
I am playing a coin tossing game. Whenever I get a ‘head’, I get x points and add it to the total, S; whenever I get a ‘tail’, I get y points and add it to the total, S. (x and y are positive integers; x > y). I then realize that, no matter how many times I toss the coin or restart, there are 35 positive integers that S can never be. 58 is one of them. Please find x and y.
|
|
 IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Coin Tossing Puzzle
« Reply #1 on: Dec 30th, 2005, 7:24am » |
Quote Modify
|
Some facts to start with:
- the greatest common divisor of x and y must be 1, otherwise there would be an infinite number of unreachable sums.
- y can not be 1, because then each number would be reachable.
- y neither can be 2, because then 58 would be easily reachable.
After some experimenting, I got a formula for the number of unreachable sums:
f(x,y) = (x-1)*(y-1)/2 provided gcd(x,y)=1
(Probably somebody can provide a nice proof.)
This leads to the unique solution x=11 and y=8.
Here is why:
We already know f(x,y)=35, so
(x-1)*(y-1)/2=35
or (x-1)*(y-1)=70
Making a table of divisors of 70 gives following possibilities for x and y:
70=1*70 y=2 x=71
70=2*35 y=3 x=36
70=5*14 y=6 x=15
70=7*10 y=8 x=11
Given that y can not be 2 and that gcd(x,y) has to be 1, only the combination y=8,x=11 remains.
Suffices to check that 58 is indeed unreachable.
[e]Edited following rmsgrey's remark that x > y.[/e]
|
| « Last Edit: Dec 30th, 2005, 3:16pm by JohanC » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2874
|
|
Re: Coin Tossing Puzzle
« Reply #2 on: Dec 30th, 2005, 1:56pm » |
Quote Modify
|
JohanC: x>y...
Otherwise, great solution - looks like what I'd have produced if I'd bothered to work through my ideas.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Coin Tossing Puzzle
« Reply #3 on: Dec 30th, 2005, 3:07pm » |
Quote Modify
|
on Dec 30th, 2005, 1:56pm, rmsgrey wrote:
I really need to learn to look more carefully ...
on Dec 30th, 2005, 1:56pm, rmsgrey wrote:| Otherwise, great solution - looks like what I'd have produced if I'd bothered to work through my ideas. |
|
Do you have some proof for the formula?
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Coin Tossing Puzzle
« Reply #4 on: Dec 30th, 2005, 3:31pm » |
Quote Modify
|
on Dec 30th, 2005, 3:07pm, JohanC wrote:Do you have some proof for the formula?
|
|
I found some interesting reference on the web:
http://math.sfsu.edu/beck/papers/frobeasy.slides.pdf
Matthias Beck's proof doesn't look too straightforward though. But I have a feeling that a simpler proof can be build combining the ideas of the beginning of his document.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Coin Tossing Puzzle
« Reply #5 on: Dec 30th, 2005, 5:08pm » |
Quote Modify
|
on Dec 30th, 2005, 3:07pm, JohanC wrote:
Do you have some proof for the formula?
|
|
It can be shown that if gcd (x,y) = 1 then any number greater than (x-1)(y-1) can be represented ax + by where a >= 0 and b >= 0 are integers.
So we are looking for number between 1 and (x-1)(y-1) which can be represented as ax + by.
For this draw on the 2D plane lattice points (M,N) for which M is a multiple of x and N is a multiple of y. This lattice point corresponds to the number M+N. (Note that if M+N = M' + N' and M != M', this would imply that gcd(x,y) != 1)
We are looking for lattice points which lie in the triangle (0,0) (0, (x-1)(y-1)) and ((x-1)(y-1), 0) which is half the number of lattice points in the rectangle whose diagonal is (0,0) ((x-1)(y-1), (x-1)(y-1))
The number of lattice points in the rectangle is [(x-1)(y-1)/x] multiplied by [(x-1)(y-1)/y] where [k] is the integer part of k.
Maybe we can show that is equal to (x-1)(y-1).
Anyway, using the above I think we can prove it, I haven't tried proving it myself...
|
| « Last Edit: Dec 30th, 2005, 5:11pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Coin Tossing Puzzle
« Reply #6 on: Jan 1st, 2006, 4:00pm » |
Quote Modify
|
It's well known that if gcd(x,y)=1, then for any integer t there are integers a,b such that ax+by=t, and any other solution has the form (a,b) = (a0-ky, b0+kx).
Suppose that for some t, there are no solutions to ax+by=t with a,b nonnegative. Taking the unique solution with 0 < a < y, this means that b<0. Thus a < y-1, and b < -1, so
t = ax+by < (y-1)x - y = xy-x-y.
Thus if t is nonnegative then it is in the interval [0, xy-x-y]. I claim that t is representable (with nonnegative a,b) iff t' = xy-x-y-t is not. This bijection shows that exactly half of the (x-1)(y-1) numbers in this interval are representable.
If t=ax+by with a,b > 0, then
t' = xy-x-y-t = (y-a-1)x + (-1-b)y = a'x + b'y,
with a'<y, b'<0. Thus t' is not representable, because the only way to have b'+kx > 0 is to have a'-ky < 0. Conversely, if t is not representable, then we can take a<y and b<0, so that a',b'>0, and t' is representable.
|
| « Last Edit: Oct 20th, 2009, 6:09pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print