Register to reply

63-gon and the sum

by Numeriprimi
Tags: 63gon, geometry, product, side, smallest value, vertex
Share this thread:
Numeriprimi
#1
Nov5-13, 02:04 PM
P: 138
Hello.
When I was in Mathematical Olympiad in our district, I got a example which I can not solve :-(
Now, I am very interested in, how to do it. I don't know, my brother - teacher don't know, my friends don't know. I think you can solve it :-) Can you help me? It isn't my homework and I really don't know how to do it easily (don't draw a 63-gon :-D)

To each of vertexes of regular 63-gon assign one of the numbers 1 or -1.
To each of his sides ascribe the product of numbers of her boundaring vertexes. Then add all numbers at sides. What is the smallest possible non.negative value of this sum?

Thank you very much and sorry for my bad English.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
economicsnerd
#2
Nov5-13, 02:31 PM
P: 229
This wouldn't have been an IMO question.
economicsnerd
#3
Nov5-13, 02:42 PM
P: 229
You have [itex]d[/itex] edges with different numbers on the vertices (product =-1) and [itex]s[/itex] edges with the same number on each vertex (product =1), and you're constrained to have
- [itex]s+d=63[/itex];
- [itex]d[/itex] an even number (because of the cyclical arrangement);
- [itex]d\leq s[/itex].
You want to make [itex]s-d[/itex] as small as possible, subject to the above constraints, i.e. [tex]\min_{d\in\{0,...,63\}} [(63-d) - d] \text{ subject to } d \text{ even}, \enspace d\leq 63 -d.[/tex] It's straightforward to check that the solution to the above problem is 3.

Indeed, the constraints require that [itex]d[/itex] be an even number which is [itex]\leq 31.5[/itex], the largest such number being [itex]30[/itex]. Since minimizing [itex]63-2d[/itex] just amounts to maximizing [itex]d[/itex], the above problem is solved by [itex]d=30[/itex], which yields [itex]s-d=33-30=3[/itex].

If you want an example of a labeling that attains this, try labeling the vertices [itex]((1,1,-1,-1)^{15},1,1,1)[/itex].


Register to reply