Induction Q...PLZ!

Bellemz

Can't figure out this question, please help!

"The Clondalkin Poker CLub lays with blue chips worth €5 and red chips worth €8. What is the largest bet that cannot be made? (Hint: use induction)"

I am at a loss as to what equation I'm supposed to source from the poker bet...
Thanks!

StephenRyan

Well, you can't make 39.

You can make 40 and 41.

If you can make a bet of n, and n > 41 then n has to have at least 3 8-chips or at least 5 5-chips.

If it has 3 8-chips then you can make n+1 by swapping them for 5 5-chips.

If it has 5 5-chips then you can make n+1 by swapping three of them for 2 8-chips.

So you can do any number bigger than 40.


Possible interesting generalisation - if a and b are coprime, is it true that a*b-1 is the largest bet that can't be made?

Bellemz

Thanks!

Still pretty confused though. THe largest bet is half the total number of chips??
Ok...is there something i'm missing about the number of chips? Is there a limit to the number of chips? Fair enough 5*8 is 40 (-1 is 39) but as far as I was concerned there was nothing preventing there being an infinite number of chips... I know NOTHING about poker if you hadn't guessed!

Fremen

Seems like every number above 31 can be written as X*8 + Y*5

Suppose N = A*8 + B, with N > 31

If B is divisible by five, you're finished.


Suppose not, then note that

N = (A-1)*8 + (B + 8)
= (A-2)*8 + (B + 16)
= (A-3)*8 + (B + 24)
= (A-4)*8 + (B + 32)

Now let B leave C as a remainder when divided by five.
Then,

(B + 8) is divisible by five with remainder c + 3
(B + 16) is divisible by five with remainder c + 1
(B + 24) is divisible by five with remainder c + 4
(B + 32) is divisible by five with remainder c + 2

And one of these remainders be zero, because B is not divisible by five by assumption, so c is not zero, so one of c + 1, c + 2, c + 3, c + 4 must be divisible by five


Now 31 can't be written as a sum of eights and fives, so that's your answer.
I can't see a neat way to use induction here, though.

EDIT: stephen, 39 = 3*8 + 3*5
You gave me a scare, I thought you had found a counterexample to my proof there :pac:

Thomas_S_Hunterson

StephenRyan wrote:

Well, you can't make 39.

You can make 39, 8,8,8,5,5,5

I did it before in an exam, can't quite remember the method I used. Here's a bit of a roundabout way. Try and get the set of the lowest possible numbers who's last digits are from 0-9. You can then make any number above these by just adding multiples of 10 (2*5), and the greatest element of the set is the highest number.

So the answer is 31 I think, if the lowest combinations are 5,8,10,13,16,21,24,27,29,32

/edit beaten to it. In the exam I used induction, but I can't think of how I did it now.

StephenRyan

Actually, 31 = 5 + 5 + 5 + 8 + 8

Stealing Sean's answer, the highest bet you can't make is 22.

Oops on my part. Oh well, at least I used induction.

Fremen

Hm, good point. In that case, all my proof did was show it's possible for every number above 31, not that the answer is 31.
That's a nice proof sean.

Thomas_S_Hunterson

StephenRyan wrote: »

Actually, 31 = 5 + 5 + 5 + 8 + 8

Stealing Sean's answer, the highest bet you can't make is 22.

Oops on my part. Oh well, at least I used induction.

Yea **** sorry (not on the ball today), that was my exam answer now that i think of it, it's a good while ago now, but it's coming to me slowly.:o

Bellemz

Still confused...brain has turned to mush after a day of studying!
N = 8x + 5y
How do I use induction to solve for the max that cannot be made...i need the method behind the answer plz.

Fremen

Re-read stephen's post. You don't solve for the max, you just prove that every number above 22 can be made using 3's and 5's

Thomas_S_Hunterson

Ok we make the smallest possible linear combination of 5 and 8, which happens to be 2*8-3*5 = 1, so provided our n number has at least three 5 chips, we can form n+1 by adding 2 8-chips and taking away 3 5-chips....

Start by taking initial value as 23.

ugh my head's a mess.

Bellemz

Thank you! I'll come back to this tomorrow with a fresh head!

Thomas_S_Hunterson

Btw, is this Dr. Osbourne's Numbers & Functions?

MathsManiac

So, ya reckon 22 is the highest you can't make, eh.

How exactly are you planning on making 27?

MathsManiac

...and here's my proof that 27 is the answer:
Part 1: one can make everything above it:
I can make 28 = 5,5,5,5,8
I can make 29 = 5,8,8,8
I can make 30 = 5,5,5,5,5,5
I can make 31 = 5,5,5,8,8
I can make 32 = 8,8,8,8
And I can make any number bigger than 32 by adding fives to one of the above. (This assertion could be proved by induction, but that's a bit pedantic since it's so obvious).

Part 2: one can't make 27:
You can't make 27 because you would have to use 0,1,2 or 3 eights (since 4 or more eights is too big), and this would require that one of {27, 19, 11, 3} is divisible by 5, which is false.

MathsManiac

Next problem:
Give a provably correct formula or algorithm for calculating the answer in the more general case of any two coprime betting chips!

Fremen

Bah. MM strikes again.

Fremen

Well, if P and Q are coprime, it's fairly trivial to modify my earlier proof to show that the highest number must be less than PQ... Beyond that, need to think.

MathsManiac

I've just been messing around with the general case now, and I reckon I've found a formula, but I can't prove it yet. Maybe 'twill come in my dreams...

Fremen

Great, now I'm going to be up all night.
Feel like putting me out of my misery?

Healio

Is the answer not 7 ??

MathsManiac

Fremen wrote: »

Great, now I'm going to be up all night.
Feel like putting me out of my misery?

I reckon, by experimental observation, that it's: m*n-m-n
(or, equivalently (m-1)(n-1)-1).

Now to prove it...

Michael Collins

MathsManiac wrote: »

I've just been messing around with the general case now, and I reckon I've found a formula, but I can't prove it yet. Maybe 'twill come in my dreams...

I have a truely marvellous proof of this but...ah no wait, I don't!

MathsManiac

Should be possible to replicate the proof for the 5, 8 case. Assuming n<m:
1. Demonstrate that the n consecutive integers staring at (m-1)(n-1) can each be constructed
2. Demonstarte that (m-1)(n-1)-1 can't, by showing that repeatedly subtracting n can't yield a multiple of m.

I'll give it a go after work!

Bellemz

Sean_K wrote: »

Btw, is this Dr. Osbourne's Numbers & Functions?

Yes it is...

Fremen

MathsManiac wrote: »

Should be possible to replicate the proof for the 5, 8 case. Assuming n<m:
1. Demonstrate that the n consecutive integers staring at (m-1)(n-1) can each be constructed
2. Demonstarte that (m-1)(n-1)-1 can't, by showing that repeatedly subtracting n can't yield a multiple of m.

I'll give it a go after work!

2 seems fairly easy.
Without loss of generality, let n < m.
let A >= 1
m*n - Am - n is not divisible by n, because
n | m*n
n | n
but n does not divide Am, unless n divides A. Then A > n, and
m*n - Am - n = m*(n -A) - n < 0

StephenRyan

a and b coprime

ka - lb = 1 some positive k and l

If ax + by = n, then a(x+k) + b(y-l) = n+1

but this doesn't work if y<l

Also, (k-b)a - (l-a)b = 1 and (k-b) and (l-a) are negative

ie (a-l)b - (b-k)a = 1

So if ax + by = n we have a(x-b+k) + b(y+a-l) = n+1

but this doesn't work if x<b-k


So if we can get n, but we can't get n+1 then we must have:

x <= b - k - 1
y <= l - 1

so n = ax + by <= a(b - k - 1) + b(l - 1) = ab - a - b - 1

as bl = ka - 1


We also need to note that we can get ab - a - b +1 as:

ab - a - b + 1 = ab - a - b + ka -lb
= (k-1)a +(a-l-1)b

and k >= 1, l<= a-1


And then we have 1)

MathsManiac

Great stuff. Now I can go out and do something on this sunny evening isntead.