1
$\begingroup$

The Baker does not sell individual bear claws, but sells them in boxes of 6, 9, and 20. Assuming an unlimited supply, what is the largest number of bear claws that I cannot buy from the baker.

I'm not sure how to attack one of these problems when given three types.

$\endgroup$
2
$\begingroup$

Hint: You can buy $n$ bear claws, where $n \in N =\{6a+9b+20c \,| a,b,c \in \Bbb{N}\} $.

Let $M = \{m|m \in \Bbb N \wedge m \notin N\}$.

You want $\sup M$.

Notice that if $b,c = 0$, every sixth number is in $N$. This implies that if six consecutive numbers are in $N$, all numbers greater than those will also be in $N$.

$\endgroup$
3
$\begingroup$

As you are probably aware, there is a well-known formula for the largest value not obtainable from the set $\{a, b\}$ where $a,b$ are coprime, called the Frobenius number, and given by $g(a,b) = ab - a - b$.

In the case of three numbers, it appears that there is no known general formula, but there are efficient algorithms for finding $g(a, b, c)$.

In a case such as the one you give, I find that the most sensible approach is to start by looking at $g(9,20) = 180 - 20 - 9 = 151$, so that $g(6,9,20) \le 151$. Then you can use the easily verified fact that the numbers obtainable using just $6$ and $9$ are all multiples of $3$ greater than $3$, from which we can say that if it had been exactly all the multiples of three, then your answer would have been $g(3,20) = 37$.

So we know that $37 \le g(6,9,20) \le 151$, and intuition would indicate it is much more likely to be nearer 37 than 151. From here, you can do a few trials and make use of the 6 consecutive number property that has been given by shade4159 to get the true answer without too much work.

$\endgroup$
0
$\begingroup$

With $6$ and $9$, we see that this creates all multiples of $3$ except $3$ itself.

With $3$ and $20$, we see that the largest number not creatable by these is $3*20-3-20=37$.

The largest number not constructable with the three numbers, is $1$ modulo 3, near $40$, since this number would be created from $40$ and some multiple of $3$. But we can't make $43$, because $3$ can not be made, so $43$ is the largest number not constructable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.