The Proof is Trivial!

Original post by Mladenov

There probably is. :tongue:

As all the possible pairs consist of consecutive Fibonacci numbers, I found it obvious that the required maximum is

987^3+1597^3

.

How is information of the two largest Fibonacci numbers below 2013 obvious? :lol:

Granted you don't have to show working but you should at least write them down bro :tongue:

And also, you haven't justified that the all solutions are Fibonacci which requires a fair bit of work and can certainly not be stated as a property of the identity you used. I can only assume an IMO examiner would have started at 7 and knocked off 1, 2 or 3 marks even if you did actually write the solution. Do you not agree?

Here is my proof:

Solution 233 (2)

First we say that

n \ge m \ \forall n, m

without loss of generality. This is because, for any solution

(n_a, m_a)

there exists a solution

(m_a,n_a)

as

(n^2_a-n_a m_a -m^2_a)^2=(m^2_a-m_a n_a - n^2_a)^2=1

.

Noting that

\displaystyle (n^2-nm-m^2)^2=((n+m)^2-(n+m)n-n^2)^2

, we deduce that, if

(n_a , m_a)

is a solution, so too is

(n_a+m_a , n_a)

. If we restrict the values of

n_a

and

m_a

to be positive integers, we can see that the sum of the cubes of the second expression is greater than that of the first.

We now observe that a trivial solution is

(1,1)

. From the formula derived above, combined with

n \ge m

and the fact that the combined sum of the solutions are increasing, we deduce that, if we assume

(1,1)

to be the base case (a=1), that there exists an increasing sequence

S_a

such that all solutions are of the form

(S_a , S_{a-1})

. By using the formula above once more, we get that

(S_{a+1}, S_{a})=(S_a+S_{a-1}, S_{a})

which implies that

S_{a+1}=S_a+S{a-1}

. As the sum of the cubes increases as a increases, we seek the largest pair of consecutive terms that are both below 2013. Given the base case we have defined, we note that the sequence

S

is equivalent to the Fibonacci sequence.

All solutions

(n_a, m_a)

are co-prime. We prove this as follows. Assume

n_a , m_a

have common factor z. Then for positive integers p, q, we have that

(zp)^2-(zp)(zq)-(zq)^2= \pm 1 \Rightarrow z^2(p^2-pq-q^2)= \pm 1

. Noticing the symmetry with the last problem, we deduce that,

z= \pm 1

. As [tez] z \not= -1 can be observed from substation, we must deduce that

z=1

and hence all solutions are co-prime.

As all solutions are co-prime, that means that we can using Euclidean's algorithm combined with the recurrence relation to show that all solutions imply a 'base' solution whereby one of the numbers is 1.

Assume there exists a separate base case of the form

(\lambda,1)

. This gives us that

(\lambda^2-\lambda-1)^2= 1

which gives us that

\lambda(\lambda-1)=0

or

(\lambda-2)(\lambda+1)=0

. Therefore the base cases we have are

(0,1), \ (-1,1), \ (2,1)

. The first case increases to be a part of

S

, the second cases forms a sequence equal to the negative values of

S

and the third case is itself a part of S. Hence all integer solutions are Fibonacci numbers or the negative of them. We can dismiss the negative values as the sum of two cubes of such numbers would be negative.

Therefore all candidate solutions are in the Fibonacci sequence. Continued adding gives three consecutive terms as 987, 1597 as 2584. As the sequence is increasing,

max(n^3+m^3)=987^3+1597^3=5034507976 \ \square

Solution 233 (3)

Applying the same restrictions to n and m and justifying that they do not decrease the generality of the solution, we get the quadratic equation

n^2-nm-(m^2 \pm 1)=0 \Rightarrow n=\frac{m+\sqrt{5m^2+4}}{2}

. From this we can see that, for n to be an integer, we require that

\sqrt{5m^2 \pm 4}

is an odd integer. If it is an integer, it is clearly odd, we we say, for

x \in N

(positivity being assumed without any loss of generality),

5m^2 \pm 4=x^2

where we now maximise

(AM(m,x))^3+m^3

. Using standard techniques for evaluating the Pell equation (etc...) gives us the values of m and x from which we obtain the desired result of

5034507976 \ \square

(edited 10 years ago)

Reply 1684

Original post by james22

Solution 239

Consider a circle of radius r, circumference c.

Enclose the circle by a regular n-gon in such a way that the distance between the center of each face=r (any issues about this not being exactly possible should go when we take the limit).

Each face form a triange with the cente, this triangle has base c/n and height r so it has area cr/(2n).

The total area of the polygon is then cr/2.

Let n->infinity so the polygon->the circle and area=cr/2=pi*2*r*r/2=pi*r^2.

-snip-

Ignore that, I've just realised that the dimension of the perimeter doesn't affect the area when it approaches that shape. That said, I would still rather an upper and lower bound for the sake of rigour :tongue:

Oh and remember that there is a second part to the problem! :wink:

Edit 2: This is actually really bothering me :frown:

Does the area of a shape that touches another shape in n places whereby all other points on the line are of a distance at most d from the other shape and has the property that

d \to 0

as

n \to \infty

approach the area of the other shape, (given that both shapes are not self intersecting of course)? :/ ARGHHHAHHFHHFdhsdfksdfkshd Is there a counterexample we can find from these definitions? :/ ARGHSHFSHFdsfkshdf

Edit 3 (sorry lol): Just noticed that you have assumed that the base of the triangle is

c/n

. This is only true on the limit and not the general case (hence a circular argument).

(edited 10 years ago)

Reply 1685

Original post by shamika

Spoiler

Yes, I did, but still thought the answer was kind of irritating. :tongue:

Spoiler

Reply 1686

Mladenov

1

Original post by Jkn

How is information of the two largest Fibonacci numbers below 2013 obvious? :lol:

Granted you don't have to show working but you should at least write them down bro :tongue:

And also, you haven't justified that the all solutions are Fibonacci which requires a fair bit of work and can certainly not be stated as a property of the identity you used. I can only assume an IMO examiner would have started at 7 and knocked off 1, 2 or 3 marks even if you did actually write the solution. Do you not agree?

You want me to write down all the Fibonacci numbers which are smaller than

2013

? We have

\begin{aligned} 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597 \end{aligned}

.

Actually, I have shown exactly this, by two ways.

I am going to write down my complete solution.

First proposition: All consecutive Fibonacci numbers satisfy

n^{2}-mn-m^{2}= \pm 1

. Denote their set by

T

.

Lemma: If

(m,n)

is a solution to

n^{2}-mn-m^{2}= \pm 1

, then so is

(n,m+n)

.

Clearly,

m^{2}+2mn+n^{2}-n^{2}-mn-n^{2} = m^{2}+mn-n^{2}=\pm 1

.

Notice that

(1,1)

is a solution, and

(1,1) \in T

. Suppose that all Fibonacci numbers up to

(F_{k-1},F_{k})

satisfy

n^{2}-mn-m^{2}= \pm 1

. From our lemma, it follows that

(F_{k},F_{k+1})

is a solution. Indeed,

(F_{k},F_{k-1}+F_{k})= (F_{k},F_{k+1})

.

Second proposition: All solutions to

n^{2}-mn-m^{2}= \pm 1

belong to the set

T

.

We note that

n=1

gives

m=1

, and this is in

T

.

Suppose the contrary. Let

(m,n)

be a solution, which does not belong to the set

T

, such that

m+n

is minimal. Next, we suppose

m \ge n>1

. We then see that

(n^{2}-mn-m^{2})^{2} = (m^{2}-n(n-m))^{2} > m^{4} > 1

- contradiction. Thus,

m < n

. Hence,

(n-m,m)

is a solution with smaller sum, implying that it is in

T

. Denote

n-m=F_{k}

and

m=F_{k+1}

, which gives

n=F_{k+2}

, so

(m,n) \in T

- contradiction.
Apropos, we can suppose that

(m,n)

is a solution, not in

T

, such that

m

is minimal. We get

(n-m,m)

is a solution. Then, if

n-m \ge m

, we have

n \ge 2m

and

n^{2}-mn-m^{2} = n(n-m)-m^{2} \ge m^{2} > 1

- contradiction. Hence

(n-m,m) \in T

....

To summarize: All solutions to

n^{2}-mn-m^{2}= \pm 1

consist of consecutive pairs of Fibonacci numbers.

I have already written all Fibonacci numbers, which are smaller than

2013

.

Conclusion: the maximum value of

m^{3}+n^{3}

is

987^{3}+1597^{3}

.

If it is yet not clear, I am to give up. :biggrin:

By the way, how do you find all solutions to the diophantine equation which you have obtained in your second solution?

Reply 1687

Why don't you move to a different problem? :tongue:

Problem 240 * / **

Find all

n \in \mathbb{N}

for which

\underbrace{ 2^{2^{2^{2^{{\cdot}^{\cdot 2}}}}} }_{n}\ -\ 3

is a perfect cube.

Reply 1688

Mladenov

1

Original post by jack.hadamard

Why don't you move to a different problem? :tongue:

Problem 240 * / **

Find all

n \in \mathbb{N}

for which

\underbrace{ 2^{2^{2^{2^{{\cdot}^{\cdot 2}}}}} }_{n}\ -\ 3

is a perfect cube.

I was just to write a solution. Give me 20 minutes. :tongue:

By the way, your first formulation was better.

Reply 1689

Original post by Mladenov

By the way, your first formulation was better.

How do you know what my first formulation was (I didn't edit)? :tongue:

Reply 1690

Mladenov

1

Original post by jack.hadamard

How do you know what my first formulation was (I didn't edit)? :tongue:

I mean, IMO 1981 problem 6, and more specifically, your modification. :tongue:

Reply 1691

Original post by Mladenov

I mean, IMO 1981 problem 6, and more specifically, your modification. :tongue:

Oh, I see. I was worried that my computer leaks. :biggrin:

Reply 1692

Original post by Mladenov

You want me to write down all the Fibonacci numbers which are smaller than

2013

? We have

\begin{aligned} 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597 \end{aligned}

.

Spoiler

Very clear, yes :biggrin:

(now all you need to do is write all your solutions like that! :wink:

)

I particularly like your elegant approach to proving that no non-Fibonacci solutions exist. :smile:

By the way, how do you find all solutions to the diophantine equation which you have obtained in your second solution?

I didn't think it was very interesting (don't only put that solution down as a what if, lmao). There's an algorithm, you might be interested in section 3 of this (it then goes on to solve the generalised form) :tongue:

It has, however, occurred to me that you could, for the variable m, show that if x and y are solutions, so too is x+y (hence deducing that m is fibonacci).

Reply 1693

james22

16

Original post by Jkn

-snip-

Ignore that, I've just realised that the dimension of the perimeter doesn't affect the area when it approaches that shape. That said, I would still rather an upper and lower bound for the sake of rigour :tongue:

Oh and remember that there is a second part to the problem! :wink:

Edit 2: This is actually really bothering me :frown:

Does the area of a shape that touches another shape in n places whereby all other points on the line are of a distance at most d from the other shape and has the property that

d \to 0

as

n \to \infty

approach the area of the other shape, (given that both shapes are not self intersecting of course)? :/ ARGHHHAHHFHHFdhsdfksdfkshd Is there a counterexample we can find from these definitions? :/ ARGHSHFSHFdsfkshdf

Edit 3 (sorry lol): Just noticed that you have assumed that the base of the triangle is

c/n

. This is only true on the limit and not the general case (hence a circular argument).

I haven't done it very rigorously. When i used c I actually meant it as the perimeter of the polygon, and asusmed that the perimeter aproached the circumference as n->infinity.

Reply 1694

Original post by jack.hadamard

Why don't you move to a different problem? :tongue:

Problem 240 * / **

Find all

n \in \mathbb{N}

for which

\underbrace{ 2^{2^{2^{2^{{\cdot}^{\cdot 2}}}}} }_{n}\ -\ 3

is a perfect cube.

Does this require a (decent) knowledge of modular arithmetic or anything like that? i.e. is the * solution reasonably findable?

Spoiler

Original post by james22

I haven't done it very rigorously. When i used c I actually meant it as the perimeter of the polygon, and asusmed that the perimeter aproached the circumference as n->infinity.

Oh right!

Well you're method is right, so if you polish it a little and then add in the lemma, I will be content :wink:

Reply 1695

Lord of the Flies

19

Solution 240

Define

s_{n+1}=2^{s_n}

with

s_0=1

. The claim is that

n>2:\;s_n\equiv 7\pod{9}

. Clearly holds for

n=3

, suppose true for some

k>2,\;s_k=7+9m

. Then

s_{k+1}\equiv 2^{9m+1}\pod{9}

. It is very easy to check that this is

7\pod{9}

when

m

is odd and

2\pod{9}

otherwise. Since

m

is clearly odd we are done. Given that

q^3\equiv 0,1,8\pod{9}

the only cubes are

s_1-3,s_2-3

.

Original post by Jkn

This is actually really bothering me :frown:

Does the area of a shape that touches another shape in n places whereby all other points on the line are of a distance at most d from the other shape and has the property that

d \to 0

as

n \to \infty

approach the area of the other shape, (given that both shapes are not self intersecting of course)?

If I have correctly understood what you mean, yes the limiting area is that of the other shape, but the limiting perimeter need not be.

The calculus version asks whether over some interval

(a,b)

and for two functions sequences of continuous functions the following is true:

\displaystyle d_n=\underset{a\leq x\leq b}{\text{max}}\big| |f_n(x)|-|g_n(x)|\big|\to 0\Rightarrow \displaystyle\int_a^b \big||f_n(x)|-|g_n(x)|\big|\,dx\to 0

as

n\to\infty

, which it clearly is:

\displaystyle 0\leq \int_a^b \big||f_n(x)|-|g_n(x)|\big|\,dx\leq \int_a^b \underset{a\leq x\leq b}{\text{max}}\big||f_n(x)|-|g_n(x)|\big|\,dx=(b-a)d_n\to 0

On the other hand, the arc-length of a function

f

is

\displaystyle \int_a^b \Big(f'^2(x)+1\Big)^{\frac{1}{2}}\,dx

Just because

\displaystyle \int_a^b |f_n|

and

\displaystyle \int_a^b |g_n|

tend to the same thing doesn't imply that

\displaystyle \int_a^b \Big(f'^2_n+1\Big)^{\frac{1}{2}}

and

\displaystyle \int_a^b \Big(g'^2_n+1\Big)^{\frac{1}{2}}

behave the same.

Take

f_n(x)=\frac{1}{n}(\cos n x+1)

and

g_n(x)=0

over

(0,\pi)

for instance. Here

d_n=2n^{-1}\to 0

, the areas tend to

0

, yet the length of the first curve

f_n

is

>\pi

even at the limit (I have chosen the function so that it mimics the "circle approximation paradox" you posted: the length of

f_n

is in fact constant).

(edited 10 years ago)

Reply 1696

Original post by Jkn

Does this require a (decent) knowledge of modular arithmetic or anything like that? i.e. is the * solution reasonably findable?

By writing one star, I don't claim the solution can be found easily, but that it exists. :tongue:

Original post by Lord of the Flies

Solution 240

Then

s_{k+1}\equiv 2^{9m+1}\pod{9}

. It is very easy to check that this is

7\pod{9}

when

m

is odd and

2\pod{9}

otherwise.

Very well! Alternatively, if

2^{2^{2n}} \equiv 7\ (9)

, then

2^{2^{2(n+1)}} \equiv (-2)^{2^2} \equiv 7\ (9)

.

Reply 1697