From year to year

A corollary to the Chicken Mcnugget Theorem states that, for positive coprime integers $m,n$ , there are exactly $\dfrac{(m - 1)(n -1)}{2}$ positive integers which cannot be expressed in the form $am + bn$ for non-negative integers $a,b$ . In this case $m = 2015, n = 2016$ , giving us an answer of

$\dfrac{(2015 - 1)(2016 - 1)}{2} = \boxed{2029105}$ .

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 $2015a+2016b$ for non-negative integers $a,b$ .

Claim: For $n > 4062240= (2015)(2016)$ , $n$ is always representable.

Proof:

Write $4062240=(2015)(2016)$ . We have

$4062240+1=(2015)(2015)+(2016)(1)$

$4062240+2=(2015)(2014)+(2016)(2)$

$\cdots$

$4062240+2016=(2015)(0)+(2016)(2016)=(2015)(2016)+(2016)(1)$

$4062240+2017=(2015)(2015)+(2016)(2)$

$\cdots$

It is obvious that this can be continued, so any $n > 4062240$ can be represented indeed.

Now, we will attempt to devise an algorithm to generate the set of "representable" integers for $n \leq 4062240$ .

Note that if $c=2015d$ , then

$c+1=2015(d-1)+2016(1)$

$c+2=2015(d-2)+2016(2)$

$\cdots$

$c+d=2015(0)+2016(d)$ .

Therefore, if $c$ is representable, so are $c+1,c+2 \cdots, c+d$ .

We claim that if we take $d=1,2, \cdots, 2015$ , we will generate the whole set of representable integers for $n \leq 4062240$ .

Proof that the algorithm generates all members of the set:

Note that we have $a+b=d-k+k=d$ for $d=1,2, \cdots ,2015$ . For $d>2015, n=2015a+2016b>2015(2016)=4062240$ , 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 $2015(d+1)=c+2015>c+d$ is true for $d < 2015$ , it is easy to see that there is no overlap of representation for $d \leq 2014$ . We need not worry about cases where $d+1>2015 \implies d>2014$ since this implies $2015(d+1)\geq 2015(2016)$ , but our algorithm has already terminated at this point, taking note of the fact that $2015(2016)$ is already generated when $d=2015 \implies c+d=2016(2015)$ .

Taking $d=1,2, \cdots, 2015$ , we have

$\displaystyle \sum_{d=1}^{2015} (d+1) = \frac{(2015)(2016)}{2}+2015$ representable integers for $1 \leq n \leq 4062240$ .

Therefore, the desired answer is $(2015)(2016)-\frac{(2015)(2016)}{2}-2015=\boxed{2029105}$ .

Let $N=2015$ . Any integer can be uniquely written as $Np+q$ where $0 \leq q < N$ .

We want know if $\exists a,b: N(a+b)+b=Np+q$ .

If $p \geq q$ , choose $a=p-q, b=q$ , and we have a solution.

Since $b \equiv q$ , $b \geq q$ .

So if $p<q$ then $a+b \geq b \geq q > p$ and $b \geq q$ Therefore $N(a+b)+b>Np+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$