There's an Android puzzle app called "The Weaver". My question is why every level seems to be solvable in far fewer moves than one might naively think.
Here's a link for people who want to play along on their Android devices, but this is not necessary to understand the question. (NB I am nothing to do with promoting this game in any way; I am an end user who just got interested in the mathematics behind the game).
It's very easy to explain the objective of this puzzle game. A level looks like this when you start it:
and it looks like this when you've finished it:
The ribbons "flow" from top to bottom and you can twist or untwist two ribbons by tapping on where they meet. You can't change the order of the ribbons going "in" (from the top) or their colours. The object is to twist the ribbons around within the rectangular grid so that the "output" of the grid matches the small coloured squares. For example, in the game above, initially only one output square is matched — the green square which is enabling a green ribbon to "escape" from the rectangular grid. All other squares don't match and so some ribbon-twisting is needed. A move on a level consists of twisting or untwisting two ribbons (by tapping on them). It's very cute.
There is also a "star" system, and to get 3 stars in a level you must solve it using the minimum number of "twists". As you can see I've done a very bad job at solving level 2.4; I've got no stars at all. There are solutions to this level with fewer twists — in fact this is obvious, because in my solution here the bottom "switch" is switched but it doesn't need to be — those two orange ribbons could just pass over each other.
The question.
I worked through the levels of this game, and I was quite surprised to find that even on big boards (the biggest is 6×6) one always seemed to be able to solve them in far fewer moves than I expected. Although the the game's board size never gets bigger than $6\times 6$ and there are also only 6 colours in the app, one can of course just dream about arbitrarily large boards involving arbitrarily many colours.
Conjecture On an $a$ by $b$ board, if the level is solvable at all, then it is solvable in at most $a+b-1$ moves (i.e. with at most $a+b-1$ "untwists").
In particular I am conjecturing that the largest number of twists you need to make is $O(a+b)$ rather then $O(ab)$.
Here is what I know about this conjecture.
Lemma The conjecture is true if $a=1$.
Proof: trivial (there are only $b=a+b-1$ switches on the board).
Lemma the conjecture is true if $a=b=2$
Proof: the only counterexample would be a board for which the only solution would be with all four switches switched. But unswitching the top and the bottom switch leads to the same order of ribbon outputs.
Lemma The conjecture is true if $ab\leq 20$.
Proof: brute force computer search.
Note that in this latter case I will allow an arbitrary number of colours (not just 6 as in the app).
Lemma The conjecture is true for all 150 levels that come with the game.
Proof: brute force check.
Lemma For given $a,b\geq1$ there exists a level whose only solution involves $a+b-1$ twists (and in particular my conjecture is best possible).
Proof: One checks that the level with $a+b$ distinct input ribbons and which is solved by switching the $a+b-1$ switches comprising the top right and bottom right sides of the grid of switches, has this property (NB the check is rather easier to do once you have played a few levels and got the hang of the combinatorics).
I think that's everything I know. Can anyone finish the job by proving my conjecture?
[Added two days later] Here is my interpretation of some discussions (now deleted) with Calum Gilhooley — a group-theoretic interpretation of the conjecture (but it's a slightly strange group-theoretic question).
We fix positive integers $a$ and $b$, and define a set $S=\{r_1,r_2,\ldots,r_a,s_1,s_2,\ldots,s_b\}$ of $a+b$ symbols (thought of as the ribbons). Each "switch" can be thought of as a transposition, and it's important to note that with the model I'm about to describe, the initial state of the switch is that the ribbons cross so the transposition is actually a transposition (i.e. it can be switched off rather than on). The following picture shows why the convention is sensible — when all the switches are switched we have something that looks like the identity as you can see from the picture below.
We read the transpositions from top to bottom in the picture; if the $r_i$ and $s_j$ are also numbered from top to bottom then the first transposition is $(r_1\ s_1)$, the next two (which commute so can be made in either order) are $(r_1\ s_2)$ and $(r_2\ s_1)$ and so on; at the $n$th step we consider $(r_i\ s_j)$ for $i+j=n+1$ and this goes down to the final transposition $(r_a\ s_b)$. Multiplying all of these $ab$ transpositions together gives us an element $X=(r_1\ s_1)(r_1\ s_2)(r_2\ s_1)\cdots(r_a\ s_b)$. This is the initial state of the board.
Now for $S$ a subset of $\{1,2,\ldots,a\}\times\{1,2,\ldots,b\}$ we can consider the element $X_S$ obtained by taking the product representation of $X$ and then removing the transpositions $(r_i\ s_j)$ for $(i,j)\in S$ (and multiplying those that we didn't remove together in the same order as we did to get $X$).
Reformulation of the question Is it true that for $S\subseteq\{1,2,,\ldots,a\}\times\{1,2,\ldots,b\}$ the permutation $X_S$ is equal to $X_T$ for some $T$ of size at most $a+b-1$?
Here is a special case: is it true that the identity can be written as $X_T$ for some $T$ of size at most $a+b-1$? That's probably a relatively easy question. It's true for $a=b$, that's not hard to check.
Best Answer
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:
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:
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:
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.