Lol, integers

Number Theory Level 4

Let $P_k(a)$ denote the greatest integer n that can not be represented by the form $ax+by=n$ for at least $1$ ordered pair (x,y) and a specific $a$ and $k$ ( $k$ is defined below in "assumptions and details")

For example, the largest integer n that can't be represented by $P_4(5)=5x+9y$ is 31 since no integer values of x and y satisfy $31=5x+9y$

Find $P_{2014}(2015)-P_{2013}(2015$ )

Tip:

$P_{2014}(2015)=2015x+4029y$

$P_{2013}(2015)=2015x+4028y$

Assumptions and details

$(a,b,x,y,n)\epsilon \Bbb{N}$

$b>a$ .

$b-a=k$

$\text{gcd}(a,b)=1$

This is part of the set Trevor's Ten

The answer is 2014.

2 solutions

Daniel Liu
Mar 15, 2015

Chicken McNugget Theorem kills this problem: $\begin{aligned} P_{2014}(2015)-P_{2013}(2015) &= (2015\times 4029 - 2015 - 4029)\\&-(2015\times 4028 - 2015 - 4028)\\ &= 2015(4029- 4028) -4029+4028\\ &= 2015-1\\ &= \boxed{2014} \end{aligned}$

I always love applications of Chicken McNugget.

-.-

I hate you McDonalds.

This just destroys my 2 page solution that I took forever to type.

Trevor Arashiro - 6 years, 3 months ago

Sorry $\ddot\frown$

Daniel Liu - 6 years, 3 months ago

lol. It's alright, at least now I know this theorem and everyone can learn from both our solutions.

Trevor Arashiro - 6 years, 3 months ago

Well, the problem is not stated well. It sometimes(in the example) gives the hint that $x,y \in Q$ (as then $36$ would be the answer in the example) and then it says that $a,x,b,y,n \in N$ . I didn't get it.

Kartik Sharma - 6 years, 2 months ago

Trevor Arashiro
Mar 15, 2015

Keep in mind $b>a$ and $k=b-a$

Let's derive a general formula for $P_k(a)$ First, let k=1

$ax+(a+1)y$

Here we will plug and chug values of a.

a	max n
a=2	n=1
a=3	n=5
a=4	n=11
a=5	n=19

Clearly, the formula here is $a^2-a-1$ . Yes, it's that golden ratio formula.

Now let k=2. However, $\textbf{remember that we have to have a and b be co-prime}$ . Thus not all values of a will work.

a	max n
a=3	n=7
a=5	n=23
a=7	n= 47
a=9	n=79

The formula here is $a^2-2$

Let $k=3$

a	max n
a=2	n=5
a=4	n=8
a=5	n= 47
a=9	n=79

Thus the formula is $a^2+a-3$

Let $k=4$

a	max n
a=3	n=11
a=5	n=31
a=7	n= 59
a=9	n=95

Thus the formula is $a^2+2a-4$

Looking at our values of k and our formulas for various k.

k	$P_k(a)$
k=1	$a^2-1a-1$
k=2	$a^2-0a-2$
k=3	$a^2+1a-3$
k=4	$a^2+2a-4$

We can observe that the formula for $P_k(a)=a^2+(k-2)a-k$

Thus

$P_{2014}(2015)=2015^2+2012\cdot 2015-2014$

$P_{2013}(2015)=2015^2+2011\cdot2015-2013$

Thus $P_{2014}(2015)-P_{2013}{2015}=\boxed{2014}$

What you did was basically guess the formula in Chicken McNugget Theorem in a really convoluted way...

Just use the fact that the greatest integer not representable by $ax+by$ for constant positive integers $a,b$ and non-negative integers $x,y$ is $ab-a-b$ .

Challenge: try to prove this!

Daniel Liu - 6 years, 3 months ago

I guess I did a wacky derivation... Technically it works, but it's not a very good one lol.

Trevor Arashiro - 6 years, 3 months ago

Lol, integers

The answer is 2014.

2 solutions

0 pending reports