The Weaver Android app $\rightarrow$ cute combinatorics problem

Solution 1:

This can be solved by the following greedy strategy (where we assume each ribbon has a unique color and hence a unique target, as all cases may be reduced to this one). The main body of the post proves it solves things in at most $n+m-1$ moves. The addendum proves that it is optimal:

Fill the grid from top to bottom (i.e. starting at the topmost cell, moving to the two cells below it, then the three in the next row, and so on) and make a twist* only when it will cause a ribbon to head directly for its output.

This works because, as we go down making moves from top to bottom, we will know that the outgoing path of any twist we make will be free of twists - that is, going top to bottom ensures that if we send a ribbon straight towards its output, it will not be diverted along the way, unless we make an additional twist later. However, we will never make an additional twist in the path of a ribbon heading towards its target in our strategy - that is, if we have a ribbon of color $A$ heading towards the target of color $A$ intersection with a ribbon of color $B$, then making the twist will send the ribbon of color $B$ to the target of color $A$ and the ribbon of color $A$ to the target of another color - which means our strategy would not make a twist. This situation is illustrated as follows:

where the dotted lines indicate what would happen if we did make a twist. This would be stupid, so we never do things like that. (The figure also illustrates the implicit hypothesis that there is a section free of twists, which we never violate so long as we move top down in our twisting). Thus, we use at most one twist per ribbon.

Knowing that if we send a ribbon towards its target, it will reach it, we just need to show that we will, at some point, send each ribbon towards its target. We can do this by induction. In particular, suppose we have an output $O$ on the left-bottom side (noting that symmetry carries the argument to the right-bottom side) such that all the outputs above it (i.e. to the left and up of $O$) will be connected to their proper inputs by using my strategy. One may consider the "row" of intersections above the output $O$. If the corresponding ribbon starts in this row, then it was always headed towards its proper output and we will never twist it in our strategy. Otherwise, consider that, if we think of the game as a graph with vertices at the intersections and edges where the ribbons are (with additional edges & vertices for where ribbons enter and exit), then we can note that removing the row above $O$ splits the graph into two connected segments - one "above" the row (i.e. the points from where $O$ could be reached by a descending ribbon) and one below. The ribbon going to $O$ must start in the segment above the row, since otherwise it could not possibly reach $O$ and the puzzle would unsolvable. However, it must end in the segment below the row because the only outputs in the upper segment would be those above $O$ - which would be connected to their appropriate ribbons and hence not to the one destined for $O$. Thus, the ribbon must head for an output not in the upper section - but to do this, it must at some point enter the row above $O$, at which point it will be diverted towards $O$ and therefore find its solution. To illustrate this, we have another pretty picture: where we can see that, no matter which possible input we choose to put the purple ribbon belonging to $O$ in, it must cross the row of $O$ since all the exits in the upper section are already filled. When it crosses the row of $O$, we divert it.

Thus, this strategy always works and uses at most one twist per ribbon. If we pause to consider the state after (at most) $n+m-1$ twists, all but one ribbon will be connected to its output. However, since all the other outputs would be taken, that last ribbon must too be connected. Thus, this strategy works on all puzzles and takes no more than $n+m-1$ moves.

Here's a picture of it applied to the puzzle you posted, where the numbers indicate what order the moves take place in. Since the colors are non-unique, I used the rule that I'd make a twist only if it would send a ribbon directly for its output and, given the rows above, no other ribbons could possibly go to that output:

*I think you may be calling what I call a "twist" an "untwists". I found that confusing, so I changed it.

Addendum:

Based on the insights in Calum Gilhooley's comments and answers, one can in fact prove that the above strategy is optimal. In particular, let $\pi$ be a permutation on the ribbons such that if $r$ is a ribbon, $\pi(r)$ is the ribbon that initially passes to the output that $r$ is supposed to. As is further explicated in Calum's answer, if we pass through the grid from top to bottom and write down the transpositions $T_i=(r_1 r_2)$ if the $i^{th}$ twist we encounter is the twisting of the ribbons $r_1$ and $r_2$, then $$\text{id} =T_nT_{n-1}\ldots T_2T_1\pi$$ since, for each twist, we essentially are swapping the identity of $r_1$ and $r_2$ for all further twists, and the idea is that at the end, we have undone the swapped identities at the start. It is a standard fact in group theory that a $c$-cycle is a product of at least $c-1$ transpositions, and it is not too difficult to additionally show that if $\pi$ is a permutation on $R$ elements with $C$ cycles, then it is the product of at least $R-C$ transpositions. In particular, we get the following characterization:

Any starting position can be solved in $R-C$ moves and no fewer.

To prove the optimality of my strategy, one simply notes that ribbons $r_1$ and $r_2$ will only interact if they are in the same cycle of $\pi$. In particular, the following truth is never changed by my strategy:

Each ribbon is, at all times, heading towards an output corresponding to a ribbon in the same cycle.

This is because if $r_1$ and $r_2$ are twisted in a state satisfying the above, where we send $r_1$ towards its target, then $r_2$ was, beforehand, pointing at the target of $r_1$ and by the above hypothesis, it follows that $r_1$ and $r_2$ are of the same cycle. Moreover, if $r_1$ was initially headed for the output for $r_3$, then $r_1$ and $r_3$ are in the same cycle - and thus, by transitivity, $r_2$ and $r_3$ are in the same cycle, and hence $r_2$ will be afterwards headed for the target of a ribbon in its cycle ($r_3$).

Then, given this and the fact that the strategy functions and assigns no more than one twist each ribbon, it is clear that it solves a cycle in $C-1$ steps. Thus it solves the game in $R-C$ steps and is thus optimal. The only question remaining is how to optimally assign inputs to outputs when the colors are non-distinct.

Solution 2:

Let $m$ and $n$ be positive integers. Denote the set $\{0, 1, \ldots, m - 1\}$ by $M.$ Let $p = m + n - 1,$ and denote the set $\{m, m + 1, \ldots, p\}$ by $N$. Let $\pi$ be any permutation of the set $P = M \cup N = \{0, 1, \ldots, p\}$ that satisfies the conditions: \begin{align*} i < m & \implies \pi(i) \leqslant i \text{ or } \pi(i) \geqslant m, \\ i \geqslant m & \implies \pi(i) \geqslant i \text{ or } \pi(i) < m. \end{align*}

Create a $(2m + 1) \times (2n + 1)$ table, with columns numbered from left to right, and rows numbered from top to bottom, both starting at $0$. Its top row has the number $h$ written in position $2h + 1$ ($h = 0, 1, \ldots, m - 1$). Its right-hand column has the number $k$ written in position $2k - 2m + 1$ ($k = m, m + 1, \ldots, p$). The remaining $2m \times 2n$ subtable is to be regarded as an $m \times n$ table of $2 \times 2$ tables, called cells, numbered from $0$ to $m - 1$ horizontally from left to right, and from $m$ to $p$ vertically from top to bottom (as already labelled by the numbers written in the top row and rightmost column of the $(2m + 1) \times (2n + 1)$ table).

$$ \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline & & & & 2 \\ & & & & \\ \hline & & & & 3 \\ & & & & \\ \hline & & & & 4 \\ & & & & \\ \hline \end{array} \\ \text{Layout for } m = 2, n = 3\ (p = 4). $$

The set $Q = M \times N$ is partially ordered by the relation: $$ (h, k) \leqslant (h', k') \iff h \leqslant h' \text{ and } k \geqslant k'. $$ An ideal (downward-closed subset) of this partially ordered set corresponds to a zig-zag line drawn through the $2m \times 2n$ subtable, from its top left-hand corner to its bottom right-hand corner, enclosing all the cells below and to the left of it. Such a line can be represented uniquely by a sequence of $m$ rightward-pointing arrows and $n$ downward-pointing arrows, in an arbitrary order; thus $Q$ has $(m + n)!/(m!n!)$ ideals. The empty ideal $\emptyset$ is represented by the sequence $\downarrow\cdots\downarrow\rightarrow\cdots\rightarrow$, and $Q$ itself by the sequence $\rightarrow\cdots\rightarrow\downarrow\cdots\downarrow$. In a Hasse diagram of the ideals of $Q$, an ideal is covered by all the ideals whose sequences are obtained from its sequence by replacing a subsequence $\downarrow\rightarrow$ with $\rightarrow\downarrow.$ These four arrows represent the edges of a single $2 \times 2$ cell.

We define a nondeterministic computational procedure - in effect a kind of game - as follows.

Computation starts with an (almost) empty table. The state of the computation, at any time, consists of a table whose filled-in cells constitute an ideal of $Q.$ Computation terminates when all of the $m \times n$ cells have been filled in.

We may move at any time to a state whose ideal covers the previous one. The two ideals differ by a single cell, whose location in the $m \times n$ table of cells is denoted in what follows by $(h, k).$ The empty ideal is covered only by the ideal $\{(0, p)\},$ therefore initially $h = 0$ and $k = p.$

Computation proceeds in such a way that every cell $(h, k)$ eventually has a number written in its lower right corner, denoted by $i$, and a number written in its upper left corner, denoted by $j:$ $$ \begin{array}{|ccc|c|} \hline & h & & \\ \hline & \vdots & & \\ \cdots & \boxed{\begin{array}{cc} j & \\ & i \end{array}} & \cdots & k \\ & \vdots & & \\ \hline \end{array} \\ \text{A partially filled cell.} $$

When this happens, we always have: \begin{gather*} h \leqslant i \leqslant k, \\ h \leqslant j \leqslant k. \end{gather*} This is because the two "ribbons" that pass through cell $(h, k)$ have originated in locations $i$ and $j$ at the top or rightmost edge of the table. The purpose of the computation is to trace these two ribbons, by working backward, one step at a time, to the two cells they have most recently passed through. The algorithm maintains these inequality relations between $h, i, j, k,$ as an invariant condition; and in fact, they determine pretty much everything it does. The given inequality conditions on the permutation $\pi$ are sufficient to ensure that the computation can always proceed.

A second invariant condition of the algorithm is that $\pi$ is always equal to the composite of the sequence of transpositions generated so far (initially empty) followed by a permutation $\theta$ that permutes only those elements of $P$ that are arranged, in some sequence, along that part of the upper right edge of the "zig-zag" line (representing the current ideal of processed cells) that has not yet reached the top or rightmost edge of the array. (This convoluted description will become clearer when we follow the record of an actual computation.) Thus: $$ \pi = \tau_1 \cdots \tau_q\theta, $$ where concatenation of functions denotes the opposite of the composition operator, $\circ$ (i.e. $\varphi\psi = \psi\circ\varphi$). At the end of the computation, $\theta$ is the identity map on $P$, and $\pi$ is therefore equal to the composite of all the transpositions generated by the algorithm, in the sequence of their generation. (The algorithm is nondeterministic, therefore the sequence is indeterminate, reflecting the fact that disjoint transpositions commute.) At the beginning of the computation, of course, $\theta = \pi.$

This discussion has brought us to the matter of the initial "almost empty" state of the game. Just enough numbers are filled in to ensure a sufficient supply of values of $i$ and $j$ to keep the computation going to the end. The initial configuration is determined by the permutation $\pi,$ as follows.

For $h = 0, 1, \ldots, m - 1,$ write the number $\pi^{-1}(h)$ into the lower right corner of the cell in position $(h, p)$ of the $m \times n$ array of cells. For $k = m, m + 1, \ldots, p,$ write the number $\pi^{-1}(k)$ into the upper left corner of the cell in position $(0, k).$

$$ \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & & & & \\ \hline 3 & & & & 4 \\ & 2 & & 4 & \\ \hline \end{array} \\ \text{Layout for the permutation } (0\,3\,4\,1\,2). $$

If programming this on a computer, one might as well represent the 'blank' value of the unfilled locations in the remaining cells by the unused integer value $m + n.$ Note, however, that the upper right corners of cells are not to be filled with numbers, but rather with transpositions or identity maps, or representations of these. Lower left corners of cells are not used at all; they do not exist, mathematically speaking; but it is hard to devise a readable pencil-and-paper representation of the computation in which no space is wasted. (Pen-and-paper, rather, because there is never any need to erase values that have been written.) I did design a sort of diamond-shaped graph paper for this purpose, but it was very hard to see what was going on, so I reverted to using normal-looking tables.

In considering the processing of a cell $(h, k),$ containing information $(i, j),$ we will ultimately need to distinguish all possible combinations of the 6 exceptional cases of equality in the following non-strict inequalities: \begin{align*} h & \leqslant m - 1, \\ k & \geqslant m, \\ h & \leqslant i \leqslant k, \\ h & \leqslant j \leqslant k. \end{align*} Without some guiding intuition, this is obviously liable to become complicated, so it is time to look at a particular example. We have already set up the initial position for the case $m = 2$, $n = 3$, $\pi = (0\,3\,4\,1\,2),$ so let us see how it develops.

In these diagrams: a red bullet denotes a compulsory transposition; a black bullet denotes a place where it is impossible to create a transposition; and a green bullet denotes a voluntary decision not to transpose, with the (apparently successful) intention of minimising the resulting total number of transpositions. \begin{gather*} \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & 2 & & & \\ \hline 3 & \color{green}{\bullet} & 3 & & 4 \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 1 & & & & 2 \\ & & & & \\ \hline 0 & & & & 3 \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & & & & 2 \\ & 0 & & & \\ \hline 0 & \color{red}{\bullet} & 2 & & 3 \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \\ \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & & & & 2 \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 1 & \bullet & 1 & & 2 \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & \color{red}{1} & \\ \hline \hline 1 & \bullet & 1 & \color{red}{\bullet} & \color{red}{2} \\ & 0 & & 2 & \\ \hline 0 & \color{red}{\bullet} & 2 & \color{red}{\bullet} & \color{red}{3} \\ & 2 & & 3 & \\ \hline 3 & \color{green}{\bullet} & 3 & \color{red}{\bullet} & \color{red}{4} \\ & 2 & & 4 & \\ \hline \end{array} \end{gather*}

The following table provides more information, especially the shape of the "zig-zag line", which ideally I would have liked to draw in blue as part of the above diagrams. The "unsorted" column shows the list of numbers that were described above, rather unhelpfully, as "those elements of $P$ that are arranged, in some sequence, along that part of the upper right edge of the zig-zag line (representing the current ideal of processed cells) that has not yet reached the top or rightmost edge of the array." $$ \begin{array}{|c|c|cccc|c|c|c|} \hline \text{ideal} & \text{unsorted} & h & i & j & k & \text{action} & \text{reason} & \text{factor} \\ \hline \hline \downarrow\downarrow\downarrow\rightarrow\rightarrow & 01234 & 0 & 2 & 3 & 4 & \text{refrained} & \text{trying to minimise} & \text{id} \\ \hline \downarrow\downarrow\rightarrow\downarrow\rightarrow & 01234 & 1 & 4 & 3 & 4 & \text{obliged} & i = k = 4 & \color{red}{(3\,4)} \\ \hline \downarrow\downarrow\rightarrow\rightarrow\downarrow & 0123 & 0 & 2 & 0 & 3 & \text{obliged} & j = h = 0 & \color{red}{(0\,2)} \\ \hline \downarrow\rightarrow\downarrow\rightarrow\downarrow & 0123 & 1 & 3 & 2 & 3 & \text{obliged} & i = k = 3 & \color{red}{(2\,3)} \\ \hline \downarrow\rightarrow\rightarrow\downarrow\downarrow & 012 & 0 & 0 & 1 & 2 & \text{forbidden} & i = h = 0 & \text{id} \\ \hline \rightarrow\downarrow\rightarrow\downarrow\downarrow & 12 & 1 & 2 & 1 & 2 & \text{obliged} & i = k = 2; j = h = 1 & \color{red}{(1\,2)} \\ \hline \rightarrow\rightarrow\downarrow\downarrow\downarrow & \text{none} & \bot & \bot & \bot & \bot & \text{finished} & \text{n/a} & \text{n/a} \\ \hline \end{array} $$

The conclusion is: $(0\,3\,4\,1\,2) = (3\,4)(0\,2)(2\,3)(1\,2),$ which is correct.

In the general case, what is at least intuitively clear is that (a) one can only be compelled to introduce a transposition once for each of the $m + n$ numbers in the set $P$, and (b) if one is compelled to transpose in the top right corner cell $(m - 1, m),$ then one cannot previously have been compelled to transpose for either $m - 1$ or $m$; therefore, at most $m + n - 1$ transpositions are needed.

Meelo's example

In Meelo's answer, there is an image of an initial game position, with numbers $1$ to $5$ written over it, to show where Meelo's strategy places the $5$ 'twists' needed, and the order in which they are placed.

Although I have some difficulty in understanding Meelo's description of his strategy (just as people seem to be having some difficulty in understanding this description of my strategy!), it seems increasingly clear that our strategies are essentially identical, differing only in how they are described. (That's a good thing - the more different ways the same idea is described, the more likely it is that a reader will find some description that makes sense to them.)

To help in showing the isomorphism of our two approaches, I have prepared a series of four snapshots of my algorithm in action, on the same initial game position, producing $5$ twists in the same places, and in the same order.

It may help if you visualise the tables below as being rotated through a clockwise angle of $\frac{3\pi}{4}$, and superimposed on the screenshot in Meelo's illustration, with the numerical column labels $0$ and $1$, and row labels $2$ to $7$, superimposed on the eight little coloured squares on the screen, and serving also to label the eight ribbons entering the opposite edges of the rectangular game grid.

Meelo and I agree that the permutation representing the mapping of ribbons to little coloured squares is then: $(0\,6\,4\,3\,2)(1\,5).$ This is the inverse of the permutation $\pi = (0\,2\,3\,4\,6)(1\,5)$ used to set up the initial configuration for my algorithm, which is shown in the first of the four tables below.

The last of the four tables, of course, shows the final configuration, and it is clear that the red bullets, representing transpositions, align with the numbers $1$ to $5$ in Meelo's illustration.

It is clear from his positioning of the numbers $2$ and $3$, in particular, that Meelo's strategy processes the intersection positions of the ribbons from left to right at each level. Accordingly, I have processed the cells of my tables in order from bottom right to top left, after each move outward by one more level from the bottom left hand corner of the table (which corresponds to moving downward from the top of the game grid in the screenshot).

In between the initial and final configurations, I have shown two successive snapshots, taken respectively before and after the processing of the cell in location $(1, 4)$ of the table. In each entry in the 'ideal' column, I have inserted a box to show which cell is currently being processed: after cell $(1, 4)$ has been processed, the algorithm moves on to process cell $(0, 3)$.

\begin{gather*} \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & & & & \\ \hline 3 & & & & 4 \\ & & & & \\ \hline 1 & & & & 5 \\ & & & & \\ \hline 4 & & & & 6 \\ & & & & \\ \hline 7 & & \phantom{7} & & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & 3 & & & \\ \hline 3 & \color{red}{\bullet} & 4 & & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & 0 & & 1 & \\ \hline \hline 0 & & & & 2 \\ & & & & \\ \hline 2 & & & & 3 \\ & 3 & & 1 & \\ \hline 3 & \color{red}{\bullet} & 4 & \bullet & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \ \, \begin{array}{|cc|cc||c|} \hline & \color{red}{0} & & 1 & \\ \hline \hline 0 & \color{red}{\bullet} & 2 & \bullet & \color{red}{2} \\ & 2 & & 1 & \\ \hline 2 & \color{red}{\bullet} & 3 & \bullet & \color{red}{3} \\ & 3 & & 1 & \\ \hline 3 & \color{red}{\bullet} & 4 & \bullet & \color{red}{4} \\ & 4 & & 1 & \\ \hline 1 & \color{green}{\bullet} & 1 & \color{red}{\bullet} & \color{red}{5} \\ & 4 & & 5 & \\ \hline 4 & \color{red}{\bullet} & 6 & \bullet & \color{red}{6} \\ & 6 & & 5 & \\ \hline 7 & \bullet & 7 & \bullet & 7 \\ & 6 & & 5 & \\ \hline \end{array} \end{gather*}

$$ \begin{array}{|c|c|cccc|c|c|c|} \hline \text{ideal} & \text{unsorted} & h & i & j & k & \text{action} & \text{reason} & \text{factor} \\ \hline \hline \downarrow\downarrow\downarrow\downarrow\downarrow \boxed{\downarrow\rightarrow} \rightarrow & 01234567 & 0 & 6 & 7 & 7 & \text{forbidden} & j = k = 7 & \text{id} \\ \hline \downarrow\downarrow\rightarrow \boxed{\downarrow\rightarrow} \downarrow\downarrow\downarrow & 01234 & 1 & 1 & 4 & 4 & \text{forbidden} & i = h = 1;\ j = k = 4 & \text{id} \\ \hline \downarrow \boxed{\downarrow\rightarrow} \rightarrow\downarrow\downarrow\downarrow\downarrow & 0123 & 0 & 3 & 2 & 3 & \text{obliged} & i = k = 3 & (2\,3) \\ \hline \rightarrow\rightarrow \downarrow\downarrow\downarrow\downarrow\downarrow\downarrow & \text{none} & \bot & \bot & \bot & \bot & \text{finished} & \text{n/a} & \text{n/a} \\ \hline \end{array} \ \, \ \, $$

The algorithm correctly concludes that $\pi = (4\,6)(1\,5)(3\,4)(2\,3)(0\,2).$