What's the Largest #2?

Number Theory Level pending

Bill found a new supplier of oysters. Their specialty is Captain McCloeskey's Oysters available in 3 different sized tins containing 6, 15, and 20 oysters. Again he wishes to feed his guests exactly 1 oyster each with none left over.

What is the largest number of guests he can't feed?

The answer is 49.

1 solution

Brian Charlesworth
Apr 29, 2017

Dr. @Worranat Pakornrat has developed a formula for the Frobenius number $G(a,b,c)$ under the following conditions: if the sizes $a,b,c$ are such that $c|\text{lcm}(a,b)$ and $\text{gcd}(a,b,c) = 1$ then

$\large G(a,b,c) = \text{lcm}(a,c) + \text{lcm}(b,c) - a - b - c$

In this case $\text{gcd}(20,15,6) = 1$ and we could have either $c = 6$ since $6|\text{lcm}(15,20) = 60$ or $c = 15$ since $15|\text{lcm}(6,20) = 60$ , so the conditions are met to apply the formula. Trying both values of $c$ we have

(i) $G(15,20,6) = \text{lcm}(15,6) + \text{lcm}(20,6) - 15 - 20 - 6 = 30 + 60 - 41 = 49$ ,

(ii) $G(6,20,15) = \text{lcm}(6,15) + \text{lcm}(20,15) - 6 - 20 - 15 = 30 + 60 - 41 = 49$ .

Thus the largest number of guests Bill can't feed is $G(15,20,6) = \boxed{49}$ .

@Worranat Pakornrat It was a pleasant surprise to find your Theorem! Have you published it anywhere, (besides Brilliant, that is)?

Brian Charlesworth - 4 years, 1 month ago

Hi, thank you for your application of my formula. And no, I have not published it elsewhere. Do you think it's worth publishing it?

Worranat Pakornrat - 4 years, 1 month ago

It's a useful result, but it would probably need to be part of a larger analysis, (establishing results for other special cases, for example), to be worth the effort of publishing. It is here on Brilliant, and there is a reference to it on Wikipedia, so it will receive plenty of exposure that way. :)

Brian Charlesworth - 4 years, 1 month ago

@Brian Charlesworth – Yes, I agree. Honestly, I've endeavored to modify the formula for all cases of three numbers, but it proved harder than I thought. :p

Worranat Pakornrat - 4 years, 1 month ago

Thanks Brian. I wondered why the set 3, 7, 13 didn't compute with this formula or does it?

Guiseppi Butel - 4 years, 1 month ago

Unfortunately with $3,7,13$ , while $\text{gcd}(3,7,13) = 1$ none of the numbers divides the lcm of the other two, so the conditions aren't met. I find that $G(3,7,13) = 11$ . We can form $12 = 4*3, 13 = 13$ and $14 = 2*7$ , so by adding multiples of $3$ to any of $12,13,14$ we can form any integer $\ge 12$ , but $11$ cannot be formed so must be the maximum such number. Along with $11$ we have that $1,2,4,5$ and $8$ cannot be formed.

Brian Charlesworth - 4 years, 1 month ago

Sorry, Brian, I am not familiar with the notation c vertical line lcm(15,20). What is the meaning of the vertical line?

Guiseppi Butel - 4 years, 1 month ago

@Guiseppi Butel – $c|\text{lcm}(a,b)$ translates to " $c$ divides the lowest common multiple of $a$ and $b$ ". So in this problem, since $6$ divides the lcm of $15$ and $20$ , namely $60$ , the conditions to use Worranat's theorem are met. However, with $3,7,13$ we see that

$3$ does not divide the lcm of $7$ and $13$ , which is $91$ ,

$7$ does not divide the lcm of $3$ and $13$ , which is $39$ , and

$13$ does not divide the lcm of $3$ and $7$ , which is $21$ .

So since none of the three numbers divides the lcm of the other two, the conditions to apply Worranat's theorem are not met. Actually, since $13 = 2*3 + 1*7$ it is the case that $13$ is redundant in this trio of numbers, i.e., any linear combination $3x + 7y + 13z$ can in fact be written as $3(x + 2) + 7(y + 1)$ , so $G(3,7,13) = G(3,7)$ , and using the formula for the two-number scenario we have that $G(3,7) = 3*7 - 3 - 7 = 11$ , as mentioned above.

Brian Charlesworth - 4 years, 1 month ago

@Brian Charlesworth – Thanks, Brian. I was not acquainted with that notation.

Guiseppi Butel - 4 years, 1 month ago

Thank you for using my formula. :)

Worranat Pakornrat - 4 years, 1 month ago

What's the Largest #2?

The answer is 49.

1 solution

0 pending reports