Solve the Hot Dog Mystery: Find the Greatest Number

[hi-liter]

Hello.
Has anyone ever noticed that hot dogs only comes in packages of 8 & 15 ? I've been trying to figure out what the largest number of hot dogs that I CANNOT have using packages of 8 & 15?
Can you please help me ?

 

[sjb-2812]

Sounds like you need something like http://en.wikipedia.org/w/index.php?title=Coin_problem&oldid=344225100 or similar.

 

[Gerenuk]

My little brute force program says the largest values are
59, 65, 66, 67, 73, 74, 81, 82, 89, 97

 

[DaveC426913]

Around here, hotdogs travel in packs of 12. 15 is very strange.

 

[HallsofIvy]

x hot dogs can be purchases as m packages of 8 and n packages of 15 if and only if x= 8m+ 15n for some non-negative integers m and n.

Notice that 8 divides into 15 once with remainder 7: 7= 15- 8. and 7 divides into 8 once with remainder 1: 1= 8- 7. Replace that "7" with 15- 8 to get 1= 8- (15- 8)= 2(8)- 7. (I bet you already knew that!) Now multiply each side by x to bet x= (2x)(8)+ (-x)(8). That is, one solution to the equation 8m+ 15n= x is m= 2x, n= -x.

That is not a valid solution because -x is non-negative only in the trivial case of x= 0. But it is easy to see that m= 2x- 15k, n= -x+ 8k is a solution for any integer k: 8m+ 15n= 8(2x- 15k)+ 15(-x+ 8k)= 16x- 120k- 15x+ 120k= x because the "120k" terms cancel.

In order to have a valid solution, then, we must have $2x- 15k\ge 0$ and $-x+ 8k\ge 0$. Those give $x\ge(15/2)k$ and $x\le 8k$.
We must have $(15/2)k\le x\le 8k$

For example, if k= 1, we have $15/2\le x\le 8$ 8 is a valid solution: 8= 1(8)+ 0(15), of course. If k= 2, $15\le x\le 16$. 15= 0(8)+ 3(15) and 16= 2(8)+ 0(15) are valid solutions. Every value of x in such an interval is a valid solution. Notice that it does NOT follow that numbers NOT in such an interval are not valid solutions: 13= 8+ 5 is not in such an interval, but any non-valid solutions must be in such gaps between intervals.

If k= 3, $22.5\le x\le 24$ so 23= 1(8)+ 1(15) and 24= 3(8)+ 0(15) are valid solutions.

In order NOT to have such "gaps" between valid solutions, we must have the upper limit for one value of k, 8k, larger than the lower limit for the next: $8k\le (15/2)(k+1)$. Multiplying both sides by 2, $16k\le 15k+ 15$ or $k\ge 15$.
If k= 15, $(15/2)(15)= 112.5\le x\le 8(15)= 120$ while if k= 16, $(15/2)(16)= 120\le x\le 8(16)= 128$ so we have missed no numbers. We know now that there will be no gaps between the intervals where we are assured to have valid solutions so every value of x equal to or above 112.

It does NOT follow that the numbers immediately below 112 have valid solutions but now we can search downward through a finite number of possibilities.

In order to have a valid solution for x= 111, we would have to have $m= 2(111)- 15k= 222- 15k\ge 0$ and $n= -(111)+ 8k\ge 0$. The first of those gives $15k\le 222$ or $k\le 222/15= 14.8$ and the second gives $8k\ge 111$ or $k\ge 111/8= 13.875$. Again, 14 is in that interval. m= 2(111)- 15(14)= 12 and n= 1 work: 111= 12(8)+ 1(15).

In order to have a valid solution for x= 110, we would have to have $m= 2(110)- 15k= 220- 15k\ge 0$ and $n= -(110)+ 8k\ge 0$. The first of those gives $15k\le 220$ or $k\le 222/15= 14.666...$ and the second gives $8k\ge 110$ or $k\ge 110/8= 13.75$. Again, 14 is in that interval. m= 2(110)- 15(14)= 10 and n= 2 work: 111= 10(8)+ 2(15).

Keep doing that until you find a value of x for which m and n cannot both be positive. That will be the largest number of hot dogs which we cannot buy in packages of 8 and 15.

 

[HallsofIvy]

Around here, hotdogs travel in packs of 12. 15 is very strange.

Yes, the problem is hotdogs in packs of 12 and hot dog buns in packs of 8 that cause the problem. But that's too easy!