10
$\begingroup$

Here's a noodle-scratcher (hopefully) for you math puzzlers.

The Stage

Let $n$ be an integer $\geq 2$. A grid is laid out as in Fig. 1, with $n$ source (S) nodes, $n$ drain (D) nodes, and a network of intermediate nodes laid out in a pattern of equilateral triangles. The nodes appear at the vertexes of the triangles. The edges of the triangles represent the connections between the nodes.

Each source is exactly $1$ unit below the source above it, and separated from the drain to its right by the length of $n$ edges.

             standard ballroom for an electron waltz
                             Fig. 1. Standard electron waltz ballrooms for $n = 2$ and $n = 4$.

The Dancers

On the grid are $n$ electrons, named $e_1\ldots e_n$, with $e_1$ initially at S1, $e_2$ at S2, etc. They can rest (stay where they are) for any length of time, or move to adjacent nodes along edges. Being nice, orderly electrons, they move independently, only one at a time, between rests.

Electron $e_1$ traverses exactly $1$ edges between rests. $e_2$ traverses exactly $2$ edges between rests, etc. Hence the number of an electron is called its speed.

There are some simple rules to follow, even for electrons:

  • Being fermions, no two electrons may occupy the same node at the same time, whether at rest or in transit.

  • While in transit between rests, an electron may not visit any node more than once, including the node it departs from. Once the electron is at rest again, the restriction is reset.

The Waltz

Due to legitimate quantum mechanicish reasons, there are also two more complicated rules to follow.

Two electrons at rest are called covalent if and only if the squared (Euclidean) distance between them is an integer. So for instance, all electron pairs are initially covalent since the squared distance between any two of them is $d^2$ for some integer $1 \leq d < n$.

The additional rules are:

  • if an electron at rest is covalent with one or more other electrons, it may only move if it is speedier than all these electrons

  • an electron cannot make any move that would cause it to become covalent with one or more speeder electron(s) when it comes to rest

Note that these rules apply only to electrons at rest and not to any intermediary edge traversals.

The Challenge

Like all self-respecting charge carriers, the goal of each electron is to reach a drain node. It doesn't matter which electron reaches which drain, so long as all $n$ electrons occupy all $n$ drains simultaneously.

It turns out this goal is always possible, even with the dancing restrictions.

Proving this is trivial for $n = 2$. A bit more challenging for $n = 3$. Quite challenging for $n = 4$. But what about any $n$?

This is your objective. Prove that for any $n$, there is always a way for the electrons to collectively reach the drains by waltzing around the grid.

(Bonus props for determining the significance of the puzzle title.)


Hint 1

Covalence is an equivalence relation. The Law of cosines may prove useful in determining its equivalence classes.

$\endgroup$
3
$\begingroup$

Two points connected by one edge or by two edges with same direction are not covalent. Then all the starting points are not covalent to any of the points directly in front or two edges in front of the starting points.

In my strategy, the electrons will now rest only on points of the row they are originally on. So electron $e_k$ will move to drain $D_k$.

With the exception of $e_1$, all electrons can make moves that bring them exactly one or two edges backward or forward on the grid. In these moves, the electrons will only use points one row above or below their row. To be able to move electron $e_1$ one step forward, all other electrons cannot be at their starting position nor at one point in front of it. So all others have to be two positions forward. But in order to move $e_2$ two positions forward, the other electrons have to be one position forward, etc. This reminds of the restrictions in the game 'Tower of Hanoi'.

Let me proof that it is possible to move a group of electrons $e_n \dots e_{n-k}$ one position forward or backward for all $k\ge0$. For $k=0$ this is easy: $e_n$ has no movement restrictions. Now assume that it is possible to move $e_n \dots e_{n-k}$ one position forward or backward for some $k\ge0$. We need to prove that it is then possible to move $e_n \dots e_{n-k-1}$ one position forward. First move the group $e_n \dots e_{n-k}$ two positions forward (or one position backward). Move $e_{n-k-1}$ one position forward. Move the other electrons to the same column as $e_{n-k-1}$. Done.

Here is, how this plays out. Dots represent positions on the starting rows of the electrons. Positions, where the difference of column number is divisible by 3, are covalent. Numbers indicate electrons.

 4...  ..4.  ..4.  .4..  .4..  4...  4...  ..4.
 3...  3...  .3..  .3..  .3..  .3..  ..3.  ..3.
 2...  2...  2...  2...  ..2.  ..2.  ..2.  ..2.
 1...  1...  1...  1...  1...  1...  1...  1...
 

..4. .4.. .4.. 4... 4... ..4. ..4. .4.. ..3. ..3. 3... 3... 3... 3... .3.. .3.. ..2. ..2. ..2. ..2. .2.. .2.. .2.. .2.. .1.. .1.. .1.. .1.. .1.. .1.. .1.. .1..

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You're extremely close. And your having recognized the similarity to the other game you mention is indeed the key to solving the puzzle. However, your proposed solution doesn't appear to be honouring the rule that no move may render a lower-speed electron covalent with a higher-speed electron. For instance, your first two moves are legal but your third move renders $e_2$ covalent with $e_4$ which is illegal. Remember that the equivalence classes in the game you mention each act like a LIFO stack with strict ordering. Fix this oversight and you get the golden check. :) $\endgroup$ – COTO Feb 28 at 1:52
  • 1
    $\begingroup$ Edited. I wondered why this solution was less than 16 moves :) $\endgroup$ – daw Feb 28 at 10:39

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.