63-gon and the sum

  1. 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.
     
  2. jcsd
  3. This wouldn't have been an IMO question.
     
  4. 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].
     
    Last edited: Nov 5, 2013
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted