Corners of a shape - prove equal number up/down

A shape has 2012 sides. This shapes corners are all labeled with a number 1-2012 in some order (however all are only used once). A corner is called an up if it is a larger number than its adjacent corners. A number is called a down if it is smaller than its adjacent numbers. How do you prove the number of ups equals the number of downs?

I am finding much difficulty in this question. I'm not quite sure how to work it seeing as numbers are randomly placed. I have looked at other polygons but they have told me nothing as to a pattern. Any help would be useful, I'm not sure how to attack the question

Re: Corners of a shape - prove equal number up/down

These 2012 numbers will make a sequence of increasing and decreasing numbers. If you disregard the vertices which are neither up/down, you will find that you have an alternating sequence of up/down/up/down etc. The 2012 numbers form a cycle (think of it as a continuous zigzag) and you will see that the number of ups equals the number of downs.

Sorry if my solution isn't rigorous enough...there's probably a similar solution that is better explained, or involves some other monovariant.

Re: Corners of a shape - prove equal number up/down

If I draw out a random series of numbers... 18,19,243,1961,10,14,16,201,791,808,496 then I don't see any pattern. It must be something to do with for each and every low number there is a higher number paired and vice versa. Still not quite sure

Re: Corners of a shape - prove equal number up/down

Quote:

Originally Posted by

**Idiotinabox** If I draw out a random series of numbers... 18,19,243,1961,10,14,16,201,791,808,496 then I don't see any pattern. It must be something to do with for each and every low number there is a higher number paired and vice versa. Still not quite sure

This example doesn't have all of the numbers from 1 up to the largest. Since you have 11 numbers there, look at, say 9, 7, 3, 6, 4, 2, 11, 10, 8, 1, 5. The numbers that are "up" are 9, 6, 11. The numbers that are "down" are 3, 2, 1- exactly the same number. Do you see that between any two "up" numbers there must be exactly one "down" number, and vice-versa?

Re: Corners of a shape - prove equal number up/down

Wow I'm so stupid. I forgot that a 'neither' number could exist. Thanks for that. Where's the thanks button btw?

Re: Corners of a shape - prove equal number up/down

Yes, that's why I stated "disregard the numbers that are neither up/down." Hence the up/down pattern.

Re: Corners of a shape - prove equal number up/down

I would've thought that observation through patterns wouldn't be a sufficient solution. How would I go about showing it for the whole shape, specifically 2012 sides

Re: Corners of a shape - prove equal number up/down

Quote:

Originally Posted by

**Idiotinabox** I would've thought that observation through patterns wouldn't be a sufficient solution. How would I go about showing it for the whole shape, specifically 2012 sides

Get a VERY VERY large sheet of paper...

Re: Corners of a shape - prove equal number up/down

Quote:

Originally Posted by

**Idiotinabox** I would've thought that observation through patterns wouldn't be a sufficient solution. How would I go about showing it for the whole shape, specifically 2012 sides

Induct?

Re: Corners of a shape - prove equal number up/down

That's just trying to prove that the next case will work where n=x, x+1 etc... So if I did do that isn't that just saying that because this case works and this case works then this case works. Is there a stronger induction?

Re: Corners of a shape - prove equal number up/down

I think the proof relies on the fact that if you just remove all the vertices that are neither ups nor downs (since these don't amount to anything) you will obtain down/up/down/up/.../up, QED.

Re: Corners of a shape - prove equal number up/down

Do I just have to say that? Is that sufficient proof?

Re: Corners of a shape - prove equal number up/down

It's probably sufficient, but I don't know if it's rigorous enough. Maybe...

Re: Corners of a shape - prove equal number up/down

So basically I've said that through observation, there is an up/down pattern. Then i look at two different example cases and conclude that if we take out the neithers then we have that pattern. Correct?