2
$\begingroup$

Place different integers on the vertices of an octagon so that the sum of the integers in any two vertices joined by one of its edges is a power of 2. Do so in such a way that the largest integer used is as small as possible.

Do likewise on the vertices of a decagon.

$\endgroup$
0
3
$\begingroup$

Here is one possible arrangement:

6, -4, 5, -1, 2, 0, 4, -2

Proof of optimality:

Here is the graph for integers $\leq 5$:
enter image description here
Note that integers $\leq -4$ do not occur, as each one can connect to at most one integer $\leq 5$.
The graph is so simple that an exhaustive analysis can be done to show that there is no simple loop of length $8$.

Slightly better proof:

We look at the edge connecting 0 and 4. If this edge is used in the loop, then at least one of 1, 2 cannot present in the loop, and at least one of -2, -3 cannot present in the loop. This results in at most $7$ numbers in the loop.

Now assume that the edge connecting 0 and 4 is not used in the loop. We may thus delete that edge from the graph.

Since the loop is of length $8$, one number does not belong to the loop. However, in the current graph, removing any number will result in one of its neighbors having at most $1$ edge. Hence that neighbor cannot occur in the loop either. This leads to at most $7$ numbers in the loop.

In view of the answer by loopy walt, this also proves optimality for the case of decagon.

$\endgroup$
2
$\begingroup$

My best shot:


          5
      3      -3

   -2           4

      6       0
          2

 

And for 10:


        6  -4
    -2         5

   3            -3

    -1         4
        2   0

 

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.