Bob's game

This is a simple case of Chicken McNugget Theorem .

In this case, $m = 4, n = 9 \Rightarrow mn-m-n = \boxed{23}$

This number (greatest positive integer that can't be written in form of $ak + bm$ where $gcd of given number (gcd(a,b)=1$ and $a,b,k,m$ are positive integers.) is called Frobenius number.

Here's the formula for this number. $Frobenius(a,b) = ab - (a + b)$ .

Apply to this formula we get $4 \times 9 - (4 + 9) = \boxed{23}$ .

PS: There's no formula for finding Frobenius of more than 2 numbers.

This is trivial by the McNugget Theorem.

the numbers that can be landed are of the form : 9a+4b.
=4(2a)+a+4b.
=4{2a+b}+a.
now let a =0,1,2,3.
all numbers can be written as 4n+0,1,2,3.
now if the answer is of the form 4n+0, then a=0 and all such values can be formed by taking different values of b if the answer is of the form 4n+1, then a=1 and hence all such values greater than 4(2.1)+1=9 can be formed.
if the answer is of the form 4n+2, then a=2 and hence all such values greater than 4(2.2)+2=18 can be formed.
if the answer is of the form 4n+3, then a=3 and hence all such values greater than 4(2.3)+3=23 can be formed.
the answer is 23

I don't have a smart solution for this, but here goes.

I just listed a few terms that could be formed by either adding $3$ or $9$ to the previous terms. I got a series of the form $\{ 4,8,9,12,13,16,17,18,20,21,22,24,25,26,27,28,29, \dots \}$ . I postulated that any number $> 29$ can be obtained using $4$ and/or $9$ . This obviously isn't rigorous, but this is how I solved it.

The line number 28+4t,29+4t,30+4t,31+4t can be landed on with that game. So, Suppose greatest positive integer cannot be landed of the token is N. Simple check for N=23 cannot be landed of that game.

We know that gcd(9,4)=1, hence they are co prime. So the above problem can be represented in the form:- 4x+9y=z, where x and y are positive integers, so what can be the maximum non-valid value of z. Using the chicken mcNugget Theorem (cool name, isn't it!!), which says that for two co prime positive integers a and b, the largest number which cannot be written in the form ax+by (where x and y are positive integers) is ab-a-b. By this theorem the largest non valid value for z is (9)(4) - 9 - 4 = 23. Hence the desired result. Q.E.D.

After understanding that we need to find the greatest number which cannot be written in the form 4X+9Y I used the following java program ::

import java.io.*;

public class BobGame

{

public static void main(String args[])

{

    int i=0;

    BobGame obj=new BobGame();

    for(i=1000;i>0;i--)

    {

        if(obj.fun(i,0)==0)

            break;

    }

    System.out.println(i);

}

int fun(int n,int p)

{

    int h=0;

    h=9*p;

    h=n-h;

    if(h<0)

        return 0;

    else if(h%4==0)

        return 1;

    else return fun(n,p+1);

}

}

Rant : Why is there a problem that can be solved using a simple application of a theorem named after a product of a fast food chain ?

Complete proof : Use the coin theorem (linked above) to see that the answer is $(4-1)(9-1) - 1 = \boxed{23}$ .

Chicken McNugget: 4*9-4-9=23

According to the Chicken McNuggets Theorem, the largest positive integer $n$ that has no non-negative integer solutions for $x$ and $y$ where $a$ and $b$ are positive integer constants to the Diophantine equation $ax+by=n$ is $ab-a-b\text{.}$

In this problem, we are looking for the largest $n$ for which there is no non-negative integer solutions for $x$ and $y$ to the equation $4x+9y=n\text{.}$ Here, $x$ represents the number of heads and $y$ represents the number of tails. The largest $n$ is found by applying the CMT where $\{a,b\}=\{4,9\}\text{.}$ $4\times9-4-9=\boxed{23}\text{.}$

It is possible to directly apply the Chicken McNugget Theorem to this problem. The greatest possible positive integer that cannot be expressed as the sum of a specific amount of $m$ 's and a specific amount of $n$ 's can be expressed as $mn-m-n$ , or simply stated, the product minus the sum. Substituting the values $4$ and $9$ , we get $36-13=\boxed{23}$ .

For this problem, you compute (9x4)-(9+4) which is 36-13, which is 23