Is it possible to arrange the numbers 1, 2,...., 2009

[arpitm08]

Need help on proof!

Question:
Is it possible to arrange the numbers 1, 2,..., 2009 in a row so that each number, with the exception of the two end numbers, is either the sum or the absolute value of the difference of the two numbers to either side of it?

Attempt:
Let's assume that three numbers a,b,c are in order somewhere in the row of a possible combination. Then b=c-a or c+a. Then the next number could be d=c-b or c+b. For the two values of d we can substitute for b and get, c-(c+or-a)=a and c+(c+or-a)=2c+or-a, but since we can't repeat values, it can't be a. so we would have 2c+or-a as the next term. So far we have a,b,c,2c+or-a. Now to get the next term, we can do the same thing. We would get e (the fifth term)=c+or-a or 3c+or-a. This way is not getting any simple, and there are way too many terms to do this for.

Could someone help me out? Thank You in advance.

 

[dodo]

I don't know a solution, but I suspect that modular arithmetic can play a role. For example, no two consecutive numbers can be even, or the whole row would have to be even. (Similarly, you can't put together two multiples of 3, or two multiples of 4, ... otherwise the whole row would consist of multiples of that number.) You are allowed to place two odd numbers together, but only once: thereafter, to both sides of that pair, the parity will alternate.

 

[BWElbert]

haven't really tried yet, but what about letting a = (b-1) and c = (b+1)? I'll try that method, but know most of my doings in number theoretic result in the progression of digits corresponding to a core digit.

 

[BWElbert]

scratch that, yielded unfavorable results.

 

[Citan Uzuki]

New guy here, I just registered to answer this question. There can be no such arrangement. It is easy to show that if a, b, and c are consecutive terms in the sequence, that c ≡ a+b (mod 2), and so you can work out the residues mod 2 of all the terms just given the residues of the first two. When you do this (there are only four possibilities to check), you will find that either all the terms are even or that about two thirds of them are odd. Since about half of the numbers between 1 and 2009 are odd, so they cannot be arranged into such a sequence.

 

[dodo]

Welcome, Citan,

You are allowed to place two odd numbers together, but only once: thereafter, to both sides of that pair, the parity will alternate.

true, I made a mistake here. They would go even-odd-odd-even-odd-odd-...