Russelle’s Perfect Square

Our featured problem today is from one of the Philippines Representatives in 2011 International Math Olympiad , Russelle Guadalupe. He is currently studying at the University of the Phillipines – Diliman, taking up BS Mathematics.  He also won several championships in local math challenges.

russelle

 

Here are some of the of his achievements in his Mathematics career.

2009 MTAP Math Challenge Individual Cat B( 2nd Place Sectoral, 8th Place Regional )

2009 MTAP Math Challenge Team Orals Cat B ( 3rd Place Sectoral, 2nd Place Regional )

2010 MTAP Math Challenge Individual Cat B( 1st Place Sectoral, 7th Place Regional )

2010 MTAP Math Challenge Team Orals Cat B ( 3rd Place Sectoral )

2011 MTAP Math Challenge Individual ( 2nd Place Sectoral, 4th Place Regional )

2011 MTAP Math Challenge Team Orals ( 1st Place Sectoral, 2nd Place Regional )

13th Phil Math Olympiad Area Stage ( 3rd Place )

13th Phil Math Olympiad Nat’l Stage ( Finalist )

2011 International Math Olympiad ( Participant)

2012 MTAP Math Challenge Individual ( 1st Place Sectoral, 1st Place Regional )

2012 MTAP Math Challenge Team Orals ( 1st Place Sectoral )

2012 1st Raffles Invitational Math Olympiad (RIMO) ( Bronze Medal )

2011 – Canadian Mathematics Contest Senior Category ( Medalist )

2012 – Euclid Mathematics Contest ( Top 25% of all contestants )

2011 – 6th Philippine Sudoku Super Challenge Elims ( Finalist )

2011 – Sharp MTG Math Trail and Problem Solving Competition ( 3rd Runner Up )

2013 – International Regions Math League ( Top Scorer )

Now, here is a breathtaking problem from Russelle himself. Hope you will learn from this.

Problem:

Let f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2. Determine the sum of all positive integers n\leq 1000 for which f(n) is a perfect square.

( 2014 EMC Online Test Problem 14)

Solution:

First, we need to find a closed-form expression for f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2 by summing each term involving j and treating terms involving i as a constant. Thus, we have

f(n)=\sum_{i=1}^n\sum_{j=1}^{n} (i-j)^2=\sum_{i=1}^n\sum_{j=1}^{n} (i^2-2ij+j^2)=\sum_{i=1}^n[i^2\sum_{j=1}^n 1-2i\sum_{j=1}^n j+\sum_{j=1}^n j^2]

=\sum_{i=1}^n[ni^2-2i\cdot \displaystyle\frac{n(n+1)}{2}+\displaystyle\frac{n(n+1)(2n+1)}{6}

=n\sum_{i=1}^n i^2-n(n+1)\sum_{i=1}^n i+\displaystyle\frac{n(n+1)(2n+1)}{6}\sum_{i=1}^n 1

=n\cdot \displaystyle\frac{n(n+1)(2n+1)}{6}-n(n+1)\cdot \displaystyle\frac{n(n+1)}{2}+\displaystyle\frac{n(n+1)(2n+1)}{6}\cdot n

=n^2(n+1)[ \displaystyle\frac{2n+1}{3}-\displaystyle\frac{n+1}{2}]

=\displaystyle\frac{n^2(n^2-1)}{6}

Thus, f(n)=\displaystyle\frac{n^2(n^2-1)}{6}. We then find all positive integers N such that f(N)=t^2 for some nonnegative integers

t. This is equivalent to N^2(N^2-1)=6t^2 or (2N^2-1)^2=24t^2+1. Letting x=2N^2-1. We have x^2-24t^2=1, a Pell’s equation. The general solution for this equation is given by

x_k=\displaystyle\frac{(x_1+t_1\sqrt{24})^k+(x_1-t_1\sqrt{24})^k}{2}, t_k=\displaystyle\frac{(x_1+t_1\sqrt{24})^k-(x_1-t_1\sqrt{24})^k}{2\sqrt{24}}

 

For all integers k\geq 0, where (x_1,t_1) is the initial solution. Clearly, by testing values with t_1>0, we have (x_1,t_1)=(5,1). Thus, we can then make a sequence \{N_k\}_{k\geq 0} of values of N based from the solutions of the given Pell’s equation. Note that

N_k^2=\displaystyle\frac{x_k+1}{2}=\displaystyle\frac{1}{2}[\displaystyle\frac{(5+\sqrt{24})^k+(5-\sqrt{24})^k}{2}+1]

=\displaystyle\frac{1}{2}[\displaystyle\frac{(5+2\sqrt{6})^k+(5-2\sqrt{6})^k}{2}+1]

=\displaystyle\frac{1}{2}[\displaystyle\frac{(\sqrt{3}+\sqrt{2})^{2k}+(\sqrt{3}-\sqrt{2})^{2k}}{2}+1]

=\displaystyle\frac{(\sqrt{3}+\sqrt{2})^{2k}+2+(\sqrt{3}-\sqrt{2})^{2k}}{4}

=[\displaystyle\frac{(\sqrt{3}+\sqrt{2})^k+(\sqrt{3}-\sqrt{2})^k}{2}]^2

Thus, we have N_k=\displaystyle\frac{(\sqrt{3}+\sqrt{2})^k+(\sqrt{3}-\sqrt{2})^k}{2}. Since

(\sqrt{3}+\sqrt{2})^k=\sum_{p=0}^k {k\choose p}3^{\frac{p}{2}}\cdot 2^{\frac{k-p}{2}}(\sqrt{3}-\sqrt{2})^k=\sum_{p=0}^k {k\choose p}3^{\frac{p}{2}}\cdot 2^{\frac{k-p}{2}}(-1)^p

we have N_k=\sum_{m=0}^{\lfloor \displaystyle\frac{k}{2}\rfloor} {k\choose 2m}3^m\cdot 2^{\frac{k}{2}-m},  which follows that  N_k  is an integer when k  is even. Thus, it suffices to check the values of  N_k  for  k\leq \log_{\sqrt{3}+\sqrt{2}} 200<7 (since N_k\leq 1000) and \sqrt{3}+\sqrt{2}>1.7+1.4=3.1>3  implies  (\sqrt{3}+\sqrt{2})^7>2187>2000.) Thus, k\in \{0,2,6\}, so by brute force calculation we get N_0=1,N_2=5,N_4=49 and N_6=485. Therefore, the sum of all integers N\leq 1000 such that f(N) is a perfect square is 1+5+49+485=\boxed{540}.

You may also like...

Leave a Reply

Your email address will not be published.

Protected by WP Anti Spam