Chaitanya's Random Pages

September 30, 2012

When is a perfect square the difference of two consecutive cubes?

Filed under: mathematics — ckrao @ 12:13 pm

This post is inspired by an attempt at the final question of the 2008 AIME II.

We consider the question of when a perfect square is equal to the difference of two consecutive cubes. If we let the cubes be a^3 and (a+1)^3, we see that we require \displaystyle (a+1)^3 - a^3 = 3a^2 + 3a + 1 to be a perfect square, say {n^2}.

If you list the first cubes they are 0,1,8,27,64,125,216,343,512,729,1000 and their differences are 1,7,19,37,61,91,127,169,217,271. Of these the squares are 1 = 1^3 - 0^3 and 169 = 13^2 = 8^3 - 7^3. By continuing to list cubes it would take a while to find the next instance of a square as a difference – the next solution is 32761 = 181^2 = 105^3 - 104^3. ūüôā

Initially I tried solving this problem by rearranging n^2 = 3a^2 + 3a + 1 as (n-1)(n+1) = 3a(a+1) but that did not take me far. Another approach was via congruences, noting that the right side is 1 \mod 6 so that n had to be of the form n = 6m \pm 1. The third and most fruitful approach for me was to view the equation as a quadratic in a.

\displaystyle 3a^2 + 3a + 1 - n^2 = 0 \quad \quad (1)

Since this has integer roots, its discriminant must be a perfect square. In other words, 9 - 4.3(1-n^2) = 3(4n^2 - 1) = t^2 for some integer t. This equation implies t must be a multiple of 3, so letting t = 3m we obtain 3(4n^2 - 1) = 9m^2, or

\displaystyle (2n)^2 - 3m^2= 1.

In other words, we need to find (positive) integer solutions to x^2 - 3y^2 = 1 where x is even. An equation of this form is known as Pell’s equation. We claim that solutions to this equation are of the form \pm (x_0 + y_0 \sqrt{3})^n, where x_0 + y_0 \sqrt{3}¬† is the smallest positive solution to x^2 - 3y^2 = 1 while x_0 > 1.

To see why this is so, firstly note that if (x_1, y_1) is another positive solution with x_1 > x_0, then the equation x_0^2 - 3y_0^2 = x_1^2 - 3y_1^2 = 1 leads to 0 < x_1^2 - x_0^2 = 3(y_1^2 - y_0^2), so y_1 > y_0 and x_0 + y_0\sqrt{3} < x_1 + y_1\sqrt{3}. Hence it makes sense to define the “smallest solution”.

Next, we know there exists some k for which

\displaystyle (x_0 + y_0\sqrt{3})^k \leq x_1 + y_1\sqrt{3} < (x_0 + y_0\sqrt{3})^{k+1}.

Multiplying all sides by (x_0 - y_0\sqrt{3})^k and using the fact that x_0^2 - 3y_0^2 = 1 gives us

\displaystyle 1 \leq (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k < x_0 + y_0\sqrt{3}.\quad \quad (2)

Define u + v\sqrt{3} := (x_1 + y_1 \sqrt{3})(x_0 - y_0\sqrt{3})^k. We can use norms in \mathbb{Z}[\sqrt{3}] or explicit computation to show that u^2 - 3v^2 = 1. Equation (2) then contradicts the minimality assumption on x_0 + y_0\sqrt{3} unless we have u =1, v= 0. We conclude that (x_1 + y_1 \sqrt{3}) = (x_0 + y_0 \sqrt{3})^k, so all solutions are of this form proving the claim.

In our case, the minimal solution is x_0 = 2, y_0 = 1, so we have the general solution

x_k + y_k \sqrt{3} = \pm (2 + \sqrt{3})^k, \quad k = 0, 1, 2, \ldots

We can use the recurrence x_{k+1} + y_{k+1}\sqrt{3} = (x_k + \sqrt{3}y_k)(2 + \sqrt{3}) = (2x_k + 3y_k) + (x_k + 2y_k)\sqrt{3} to see that x_{k+1} and y_k have the same parity (odd or even), as do y_{k+1} and x_k. Since initially x_0 = 2, y_0 = 1, we see that the solutions alternate in parity. Since we are looking for x being even, we are looking for odd k.

x_{2k+1} + y_{2k+1}\sqrt{3} = \pm (2 + \sqrt{3})^{2k+1} = \pm (2 + \sqrt{3})(7 + 4\sqrt{3})^k.

Using the same method as before this leads to the recurrences

\begin{aligned} x_{2k+3} &= 7x_{2k+1} + 12y_{2k+1}\\ y_{2k+3} &= 4x_{2k+1} + 7y_{2k+1}\end{aligned}

We can decouple these by taking 7 times the first equation minus 12 times the second to obtain 7x_{2k+3} - 12 y_{2k+3} = x_{2k+1}. Then x_{2k+3} = 7x_{2k+1} + 12y_{2k+1} = 7x_{2k+1} +(7x_{2k+1} - x_{2k-1}) = 14x_{2k+1} - x_{2k-1}. Similarly we find y_{2k+3} = 14y_{2k+1} - y_{2k-1}.

Initial solutions are (2,1), (26, 15), (362, 209), .... From (1) we have a = (-1 \pm t)/2 = (-1 \pm 3m)/2, so we require m = y to be odd. This will indeed be the case by our parity arguments from before (that x_k and y_k have different parity). We conclude that this recurrence gives us the entire solution set for (2n, m). The non-negative (a_k,n_k) solutions are (0, 1), (7,13), (104, 181), (1455, 2521), .... In other words,

\begin{aligned} 8^3 - 7^3 &= 13^2\\105^3 - 104^3 &= 181^2\\ 1456^3 - 1455^3 &= 2521^2, \ldots \end{aligned}

The recurrence linking these can be found to be a_{k+1} = 14a_k - a_{k-1} + 6 and n_{k+1} = 14 n_k - n_{k-1} and it can be verified that (a_k+1)^3 -a_k^3 = n_k^2. The factor of 14 in the recurrence indicates that the solution set is relatively sparse (though still infinite).

A similar approach is shown in [3], where the Pell’s equation is obtained by completing the square to obtain (2n)^2 - 3(2a+1)^2 = 1 rather than using the discrminant.

References

[1] DuŇ°an ńźukińá, “Pell’s equation”, The IMO Compendium Group

[2] Matthew Wright, “Solving Pell’s equation”, available here.

[3] 2008 AIME II Problems/Problem 15 – AoPSWiki

Advertisements

September 27, 2012

High averages in both test and ODI series against a nation

Filed under: cricket,sport — ckrao @ 12:12 pm

Recently Hashim Amla from South Africa performed a rare feat in averaging over 100 in both test and ODI cricket series against England. It led me to look up others who have performed similarly. The following lists in chronological order those who have averaged over 100 in both test and ODI series against a single team with the restriction that at least 180 ODI runs were scored. I collected the data manually starting with this list of high ODI series averages. Corrections/additions are welcome.

 

Tests ODIs
Name (nation) Opposition, venue Season Tests Inn Runs Ave 50/100 HS Inn Runs Ave 50/100 HS
Sir Viv Richards (WI) vs England in England 1976 4 7 829 118.42 2/3 291 3 216 108 1,1 119*
Javed Miandad (Pak) vs India in Pakistan 1982/83 6 6 594 118.8 1/2 280* 4 234 0,2 119*
Jacques Kallis (SA) vs West Indies in South Africa 2003/04 4 6 712 178 1/4 177 3 361 180.5 2,1 139
Shivnarine Chanderpaul (WI) vs England in England 2007 3 5 446 148.67 3/2 136* 3 202 202 1,1 116*
Graeme Smith (SA) vs Bangladesh in Bangladesh 2007/08 2 3 304 101.33 1/1 232 3 199 199 1,1 103*
Jonathan Trott (Eng) vs Bangladesh in England 2010 2 3 265 132.5 0/1 226 2 204 102 1,1 110
Hashim Amla (SA) vs England in England 2012 3 5 482 120.5 0/2 311* 4 335 111.67 1,1 150

 

We see that Richards and Kallis were the only two to aggregate over 1000 runs, with Amla getting both a triple hundred in the tests and a 150 in ODIs.

Honourable mentions/close calls:

  • In 2001 Steve Waugh averaged 100 in the NatWest series against England and Pakistan (200 runs in 4 innings), then 107 in the subsequent Ashes series.
  • In 1983/84 Desmond Haynes averaged 340 in the ODI series (4 innings) and 93.6 (468 runs in 8 innings) in the test series against Australia.

September 23, 2012

7^7 – 6^6

Filed under: mathematics — ckrao @ 11:07 am

I didn’t expect this number to be so memorable.

\displaystyle 7^7 - 6^6 = 776,887

  • It starts and ends with the digit 7.
  • It has only 3 different digits (consecutive ones at that and including 6 and 7).
  • The first three digits of the number are the same as the first three digits of the original expression 7^7 - 6^6. They are also easy to recall if you link it to when the ancient Olympics were first held or when the US Declaration of Independence was signed. (I often link numbers to years of events as a memory aid.)
  • The two three-digit numbers 776 and 887 making up the six-digit number differ by 111. ūüôā

For what it’s worth the result also happens to be prime.

September 13, 2012

Tournament wins before a first grand slam

Filed under: sport — ckrao @ 11:30 am

This week Andy Murray broke through with his first grand slam singles title in the 2012 US Open. This led me to compile the following list of the grand slam singles champions (winning for the first time in the Open era from 1968) along with the number of tournaments they won before winning that first grand slam. As can be seen, only a handful won more than a dozen tournaments before their first major, with Ivan Lendl leading the way with 40 tournament wins spanning four years before his first major! Aside from Murray and his coach Lendl, Chris Evert, Martina Navratilova, Jana Novotna, Kim Clijsters, Guillermo Vilas, Thomas Muster and Goran IvaniŇ°evińá won more than 20 tournaments before finally achieving that first grand slam win.

A few players won a grand slam as their first tournament victory, Gustavo Kuerten the most recent to do so. As far as I can tell only Chris O’Neil won her one and only singles tournament at a grand slam.

As an aside, I noticed that Thomas Muster had an amazing run in 1995, winning 11 tournaments in just over six months, all on clay!

Men # tournament wins before first slam Women # tournament wins before first slam
Andy Murray 23 Victoria Azarenka 9
Juan Martín del Potro 6 Samantha Stosur 2
Novak Djokovic 7 Petra Kvitov√° 4
Rafael Nadal 6 Li Na 4
Gastón Gaudio 2 Francesca Schiavone 3
Andy Roddick 10 Ana Ivanovińá 6
Roger Federer  8 Amélie Mauresmo 19
Juan Carlos Ferrero 9 Kim Clijsters  27
Albert Costa 11 Svetlana Kuznetsova 3
Thomas Johansson 6 Maria Sharapova 3
Lleyton Hewitt 9 Anastasia Myskina 7
Goran IvaniŇ°evińá 21 Justine Henin 9
Marat Safin 4 Jennifer Capriati 12
Carlos Moy√° 4 Venus Williams 9
Petr Korda 9 Serena Williams 3
Patrick Rafter 1 Lindsay Davenport 17
Gustavo Kuerten 0 Jana Novotn√° 21
Richard Krajicek 9 Iva Majoli 8
Yevgeny Kafelnikov 9 Martina Hingis 3
Thomas Muster 28 Mary Pierce 5
Sergi Bruguera 7 Conchita Martínez 18
Andre Agassi  15 Gabriela Sabatini 14
Michael Stich 1 Monica Seles 6
Jim Courier 3 Arantxa S√°nchez Vicario 2
Pete Sampras 2 Steffi Graf 14
Andrés Gómez 19 Hana Mandlíková 11
Michael Chang 1 Tracy Austin 7
Pat Cash 3 Barbara Jordan 1?
Boris Becker 1 Martina Navratilova 22
Stefan Edberg 5 Virginia Ruzici 2
Ivan Lendl 40 Chris O’Neil 0
Yannick Noah 13 Mima JauŇ°ovec 2
Mats Wilander 0 Kerry Melville Reid ?
Johan Kriek 3 Sue Barker 5
Brian Teacher 3 Chris Evert [3] 30
John McEnroe 11 Evonne Goolagong Cawley 6
Vitas Gerulaitis 7 Virginia Wade 0
Guillermo Vilas 22
Roscoe Tanner 8
Adriano Panatta 5
Mark Edmondson 0
Manuel Orantes 18
Björn Borg 4
Jimmy Connors 17
Ilie NńÉstase 17
Andrés Gimeno 3
Stan Smith 7
Jan KodeŇ° 0
Arthur Ashe 1

References

[1] http://en.wikipedia.org/wiki/List_of_Grand_Slam_men%27s_singles_champions

[2] http://en.wikipedia.org/wiki/List_of_Grand_Slam_women%27s_singles_champions

[3] Chris Evert – Match Results & Records

Blog at WordPress.com.

%d bloggers like this: