How many positive integers cannot be expressed in the form 2 0 1 5 a + 2 0 1 6 b for non-negative integers a and b ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Are there any restrictions on m and n ? What if both m and n are even? (Say like m = 4 , n = 6 )
Log in to reply
Yes, sorry, I forgot to specify that m , n must be coprime for this formula to apply. I've made the appropriate edit.
Why is it called the Chickdn McNugget theorem , haha?
Log in to reply
The "origin story" is provided in the link. :)
I did it the old-fashioned way since I didn't realize the existence of Chicken Mcnugget Theorem until I read the wiki. Thanks for introducing this neat theorem through the question :)
We call n representable if n can be expressed as 2 0 1 5 a + 2 0 1 6 b for non-negative integers a , b .
Claim: For n > 4 0 6 2 2 4 0 = ( 2 0 1 5 ) ( 2 0 1 6 ) , n is always representable.
Proof:
Write 4 0 6 2 2 4 0 = ( 2 0 1 5 ) ( 2 0 1 6 ) . We have
4 0 6 2 2 4 0 + 1 = ( 2 0 1 5 ) ( 2 0 1 5 ) + ( 2 0 1 6 ) ( 1 )
4 0 6 2 2 4 0 + 2 = ( 2 0 1 5 ) ( 2 0 1 4 ) + ( 2 0 1 6 ) ( 2 )
⋯
4 0 6 2 2 4 0 + 2 0 1 6 = ( 2 0 1 5 ) ( 0 ) + ( 2 0 1 6 ) ( 2 0 1 6 ) = ( 2 0 1 5 ) ( 2 0 1 6 ) + ( 2 0 1 6 ) ( 1 )
4 0 6 2 2 4 0 + 2 0 1 7 = ( 2 0 1 5 ) ( 2 0 1 5 ) + ( 2 0 1 6 ) ( 2 )
⋯
It is obvious that this can be continued, so any n > 4 0 6 2 2 4 0 can be represented indeed.
Now, we will attempt to devise an algorithm to generate the set of "representable" integers for n ≤ 4 0 6 2 2 4 0 .
Note that if c = 2 0 1 5 d , then
c + 1 = 2 0 1 5 ( d − 1 ) + 2 0 1 6 ( 1 )
c + 2 = 2 0 1 5 ( d − 2 ) + 2 0 1 6 ( 2 )
⋯
c + d = 2 0 1 5 ( 0 ) + 2 0 1 6 ( d ) .
Therefore, if c is representable, so are c + 1 , c + 2 ⋯ , c + d .
We claim that if we take d = 1 , 2 , ⋯ , 2 0 1 5 , we will generate the whole set of representable integers for n ≤ 4 0 6 2 2 4 0 .
Proof that the algorithm generates all members of the set:
Note that we have a + b = d − k + k = d for d = 1 , 2 , ⋯ , 2 0 1 5 . For d > 2 0 1 5 , n = 2 0 1 5 a + 2 0 1 6 b > 2 0 1 5 ( 2 0 1 6 ) = 4 0 6 2 2 4 0 , which lies outside the range we are interested in. Note also that for every d , our algorithm generates a complete 2 -partition of d as non-zero integers ordered pairs ( a , b ) , thus generating every member of the set.
Proof that every member of the set is unique:
Since 2 0 1 5 ( d + 1 ) = c + 2 0 1 5 > c + d is true for d < 2 0 1 5 , it is easy to see that there is no overlap of representation for d ≤ 2 0 1 4 . We need not worry about cases where d + 1 > 2 0 1 5 ⟹ d > 2 0 1 4 since this implies 2 0 1 5 ( d + 1 ) ≥ 2 0 1 5 ( 2 0 1 6 ) , but our algorithm has already terminated at this point, taking note of the fact that 2 0 1 5 ( 2 0 1 6 ) is already generated when d = 2 0 1 5 ⟹ c + d = 2 0 1 6 ( 2 0 1 5 ) .
Taking d = 1 , 2 , ⋯ , 2 0 1 5 , we have
d = 1 ∑ 2 0 1 5 ( d + 1 ) = 2 ( 2 0 1 5 ) ( 2 0 1 6 ) + 2 0 1 5 representable integers for 1 ≤ n ≤ 4 0 6 2 2 4 0 .
Therefore, the desired answer is ( 2 0 1 5 ) ( 2 0 1 6 ) − 2 ( 2 0 1 5 ) ( 2 0 1 6 ) − 2 0 1 5 = 2 0 2 9 1 0 5 .
Great that you re-discovered this proof!
Great! Thanks for posting the "first principles", (aka "old-fashioned"), solution. :)
Let N = 2 0 1 5 . Any integer can be uniquely written as N p + q where 0 ≤ q < N .
We want know if ∃ a , b : N ( a + b ) + b = N p + q .
If p ≥ q , choose a = p − q , b = q , and we have a solution.
Since b ≡ q , b ≥ q .
So if p < q then a + b ≥ b ≥ q > p and b ≥ q Therefore N ( a + b ) + b > N p + q so there's no solution.
So we just need to count the ( p , q ) s.t. p < q
For p = 0 there are N − 1 values of q, for p = 1 there are N − 2 values of q, ....
So the answer is N − 1 + N − 2 + . . . + 1 = ( N − 1 ) N / 2
Problem Loading...
Note Loading...
Set Loading...
A corollary to the Chicken Mcnugget Theorem states that, for positive coprime integers m , n , there are exactly 2 ( m − 1 ) ( n − 1 ) positive integers which cannot be expressed in the form a m + b n for non-negative integers a , b . In this case m = 2 0 1 5 , n = 2 0 1 6 , giving us an answer of
2 ( 2 0 1 5 − 1 ) ( 2 0 1 6 − 1 ) = 2 0 2 9 1 0 5 .