Last chance to look at me, Hector

Number Theory Level 2

I am going to Los Pollos Hermanos to buy a few buckets of fried chickens for the party later tonight. This restaurant only carries two sizes of bucket: one for 9 fried chickens and the other for 13 fried chickens.

Will I be able to buy precisely 105 fried chickens?

Bonus: What about 95 fried chickens?

Yes No

2 solutions

Rahil Sehgal
May 10, 2017

Let the number of chicken buckets having $9$ fried chickens be $x$ and number of chicken buckets having $13$ fried chickens be $y$ . Therefore, $9x+13y=105$ . We need to consider cases to solve this question:

Case 1: $x=1 \Rightarrow 105-9=96$ which is not a multiple of $13$

Case 2: $x=2 \Rightarrow 105-18=87$ which is not a multiple of $13$

Case 3: $x=3 \Rightarrow 105-27=78$ which is a multiple of $13$ .

Hence, we get our answer as $x=3$ and $y=6$ .

For the bonus part , we need to again consider the cases. This time $9x+13y=95$ .

Case 1: $x=1 \Rightarrow 95-9=86$ which is not a multiple of $13$

Case 2: $x=2 \Rightarrow 95-18=77$ which is not a multiple of $13$

Case 3: $x=3 \Rightarrow 95-27=68$ which is not a multiple of $13$

Case 4: $x=4 \Rightarrow 95-36=59$ which is not a multiple of $13$

Case 5: $x=5 \Rightarrow 95-45=50$ which is not a multiple of $13$

Case 6: $x=6 \Rightarrow 95-54=41$ which is not a multiple of $13$

Case 7: $x=7 \Rightarrow 95-63=32$ which is not a multiple of $13$

Case 8: $x=8 \Rightarrow 95-72=23$ which is not a multiple of $13$

Case 9: $x=9 \Rightarrow 95-81=14$ which is not a multiple of $13$

Case 10: $x=10 \Rightarrow 95-90=5$ which is not a multiple of $13$ .

As none of the cases satisfy, therefore answer is no for the bonus part.

Note:- We can also solve without considering the cases, just by finding the integral solutions.

Good standard approach.

By the way, there's a one-line solution.

Pi Han Goh - 4 years, 1 month ago

There's one line solution if we directly find the integral value of $x$ and $y$ without forming any cases.

Rahil Sehgal - 4 years, 1 month ago

Let me clarify: There's a one-line solution without knowing that (x,y) = (3,6) in the first place. And we are also able to answer the bonus question at the same time.

Pi Han Goh - 4 years, 1 month ago

@Pi Han Goh – My understanding(For this case and generally): So let us transform it into an equation of the form 9x+13y=105. But for any equation of this form, that is ax + by=c, c can take any value after (a b-(a+b)) but c cannot take the value of (a b-(a+b)). So this explains that 95 is not possible. Can you confirm please.

Sathvik Acharya - 4 years, 1 month ago

@Sathvik Acharya –

that is ax + by=c, c can take any value after (ab-(a+b)) but c cannot take the value of (ab-(a+b)).

Are you sure this is always true? If yes (or no), why is it true?

Pi Han Goh - 4 years, 1 month ago

@Pi Han Goh – I have no idea of the proof I got it by trying out numerous smaller examples and creating tables

Sathvik Acharya - 4 years, 1 month ago

@Sathvik Acharya – you have the right idea. But there are some conditions that you need to establish first:

$c$ is a positive integer.
$a$ and $b$ are non-negative integers.
$a$ and $b$ are coprime (do you know why?)

After all these conditions are laid out, you would have accidentally stumbled upon a famous theorem. It's best (or the most fun) that you try to figure out this theorem on your own (even though I've very very subtly given hints in the question itself)

Pi Han Goh - 4 years, 1 month ago

@Pi Han Goh – Yes a and b have to be coprime and if not it does not work though I do not know why and I am clueless with the proof of this theorem, can you please help with a website or something easier to understand. Thank you

Sathvik Acharya - 4 years, 1 month ago

@Sathvik Acharya – Here you go .

Pi Han Goh - 4 years, 1 month ago

@Pi Han Goh – Thank you. This is going to help me a lot and I am just trying to write a solution though not quite one-line

Sathvik Acharya - 4 years, 1 month ago

@Pi Han Goh – I guess this can help-' https://brilliant.org/wiki/postage-stamp-problem-chicken-mcnugget-theorem/ '. I cannot figure it out in any case and there seem to be much harder problems based on the same idea

Sathvik Acharya - 4 years, 1 month ago

@Sathvik Acharya – Yup, that's the correct theorem. Well done! Now, can you construct the one-line solution that answers both my question and the bonus question?

Pi Han Goh - 4 years, 1 month ago

Siva Budaraju
May 15, 2017

For the regular problem: By the Chicken McNugget theorem, 13•9-13-9 = 95 is the highest number which cannot be bought. Since 105>95, it can be bought; namely with 3 9 chickens and 6 13 chickens.

Bonus: No because by the Chicken McNugget theorem, 95 cannot be bought (it is the highest number that cannot be bought).