1

I'm stuck on the following problem, and I will appreciate it very much if anyone could direct me with to the right way of thinking, because I currently have no idea how to proceed after the initial attempt.

Question: If a store sells beers only in packages of $9$ cans and $14$ cans, prove that there is no way to buy exactly $103$ cans of beers from the store.

My Solution: First, since $9\nmid 103$ and $14\nmid 103$, there is no way to buy exactly 103 cans of beers with only 9-pack beers OR(exclusive) with only 14-pack beers.

However, if we mix and match the packs to get exactly $103$ cans of beers, eg) $x$ amount of $14$-packs plus $y$ amount of $9$-packs, I'm uncertain if the following method of proof is on the right track:

Second, since $(103 \mod 14) \equiv 5$ where the remainder is $5$ cans, and $(103 \mod 9)= 4$ has a remainder of $4$ cans. It's impossible to buy $5$ cans or $4$ cans of beers to add up to exactly $103$ cans. Therefore, it's impossible to get $103$ cans with the given packages of beers.

Mason
  • 3,792
TerminatorOfTerminators
  • 315
  • I don't think your proof is really valid. For example, you could say $16 \pmod 5 \equiv 1$, which does not divide $3$, and $16 \pmod 3 \equiv 1$, which does not divide $5$, so $16$ can't be the sum of $3$s and $5$s. This is false of course: $16=3+3+5+5$. – Noble Mushtak Nov 28 '18 at 22:49

3 Answers3

3

Suppose $103=9a+14b$ with $a,b\ge0$. Then

$$9\cdot14=126=103+9+14=9(a+1)+14(b+1)$$

Since $9$ and $14$ are relatively prime, we must have $9\mid b+1$ and $14\mid a+1$. This implies $b\ge8$ and $a\ge13$. But then

$$9a+14b\ge9\cdot13+14\cdot8=117+112=229\gt103$$

which is a contradiction.

Barry Cipra
  • 79,832
2

$9x+14y =103$ has no solutions in the positive integers. But it does have solutions in the integers. $x=27, y=-10$ satisfies this equation.

Do you know about Bezout's Lemma?

Because you can write down all the solutions using Bezout's lemma and then argue that none of these solutions have both positive $x$ and $y$.

You'll find the solutions to be $x=14n+13, y=-9n-1$

And now all we have to do is argue that for all $n$ whenever $x$ is positive $y$ is not and whenever $y$ is positive $x$ is not.

Mason
  • 3,792
2

I think the easiest way to prove this is by contradiction. This is certainly not the most elegant method, but it still works and does not require any special theorems.

Let's say it is possible to buy $103$ cans from the store by buying $a$ packs of $9$ and $b$ packs of $14$. Thus:

$$103=9a+14b$$

Since $9a$ plus a positive number (i.e. $14b$) is $103$, we can conclude $9a < 103\rightarrow a \leq 11$. Furthermore, you can't buy negative packs of $9$, so $a \geq 1$. Now, let's rearrange the equation above:

$$14b=103-9a$$

What we are showing here is that $103-9a$ must be a multiple of $14$. Moreover, as we showed before, $1 \leq a \leq 11$. Therefore, let's just try all $11$ possibilities and see if we get any multiples of $14$. $$103-9\cdot 1=94\equiv 10 \pmod {14}$$ $$103-9\cdot 2=85\equiv 1 \pmod {14}$$ $$103-9\cdot 3=76\equiv 6 \pmod {14}$$ $$103-9\cdot 4=67\equiv 11 \pmod {14}$$ $$103-9\cdot 5=58\equiv 2 \pmod {14}$$ $$103-9\cdot 6=49\equiv 7 \pmod {14}$$ $$103-9\cdot 7=40\equiv 12 \pmod {14}$$ $$103-9\cdot 8=31\equiv 3 \pmod {14}$$ $$103-9\cdot 9=22\equiv 8 \pmod {14}$$ $$103-9\cdot 10=13\equiv 13 \pmod {14}$$ $$103-9\cdot 11=4\equiv 4 \pmod {14}$$

Thus, $103-9a$ is never a multiple of $14$ for any $1 \leq a \leq 11$, so we have reached a contradiction. This means our original assumption that buying exactly $103$ cans from the store is possible must be false, so it is impossible to buy exactly $103$ cans from the store.

Noble Mushtak
  • 18,402
  • 28
  • 44