{"id":1649,"date":"2016-12-18T22:06:37","date_gmt":"2016-12-19T04:06:37","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1649"},"modified":"2016-12-21T15:03:33","modified_gmt":"2016-12-21T21:03:33","slug":"tangled-wires","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/tangled-wires\/","title":{"rendered":"Tangled wires"},"content":{"rendered":"

This Riddler<\/a> puzzle is about tangled wires. Can you figure out how to untangle them?<\/p>\n

\nThere are N wires leading from the top of a bell tower down to the ground floor. But as wires tend to do, these have become hopelessly tangled. Good thing the wires on the top floor are all labeled, from 1 to N. The wires on the bottom, however, are not. (In retrospect, somebody probably should have anticipated a tangle or two.)<\/p>\n

You need to figure out which ground-floor wire\u2019s end corresponds to which top-floor wire\u2019s end. (The bulk of the wiring is hidden behind a wall, so you can\u2019t simply untangle them.) On the ground floor, you can tie two wire ends together, and you can tie as many of these pairs as you like. You can then walk to the top floor and use a circuit detector to check whether any two of the wires at the top of the tower are connected or not. What is the smallest number of trips to the top of the tower you need to take in order to correctly label all the wires on the bottom?\n<\/p><\/blockquote>\n

Here is my solution.
\n[Show Solution]<\/a><\/p>\n

\n

It’s impossible to untangle the wires when $N=2$ because the circuit detector can’t tell us whether the wires are crossed or not. So at first glance, it may seem like this puzzle is unsolvable. Surely it can’t get easier as we add more<\/em> wires, can it?<\/p>\n

It can! In fact, for any $N \\ge 3$, the wires can be untangled using exactly two trips. I will illustrate the solution via an example. Let’s assume $N$ is odd, and take the case $N=7$ with the wires tangled as shown below. Label the wires $\\{1,2,\\dots,7\\}$ at the top and $\\{A,B,\\dots,G\\}$ at the bottom.<\/p>\n

\"\"<\/a><\/p>\n

On our first trip, we connect the wires in pairs as shown in purple. On our second trip, we connect the wires in pairs again, but shifted by one, as shown in dark blue. Here are the lists of connected pairs observed at the top of the tower when we use the circuit detector.
\n\\begin{align}
\n\\text{First trip:}&\\quad\\{(A,B), (C,D), (E,F)\\}\\mapsto\\{(2,4),(1,6),(5,7)\\} \\\\
\n\\text{Second trip:}&\\quad\\{(B,C), (D,E), (F,G)\\}\\mapsto\\{(4,6),(1,5),(3,7)\\}
\n\\end{align}Of course, we don’t know which pairs correspond to which wires. Consider the results of the first trip, for example. We know that $(A,B)$ corresponds to $(2,4)$ or $(1,6)$ or $(5,7)$, but not which one. Even if we knew that $(A,B)$ corresponded to $(2,4)$, we wouldn’t know whether $A=2$ and $B=4$ or vice versa. Nevertheless, the information we learned is useful because if we knew for example that $E=6$, then we could deduce that $F=1$ because $E$ and $F$ are connected and $1$ and $6$ form a pair.<\/p>\n

In both trips combined, every wire was connected twice except $A$ and $G$, which were each connected once. Examining occurrences of numbers in both lists above, we see that $2$ and $3$ only appear once. These numbers therefore correspond to $A$ and $G$ in some order. We connected $A$ in our first trip, and this is the list where $2$ occurs, therefore $A = 2$. We can reconstruct the entire pattern by following the links:<\/p>\n

    \n
  1. $A=2$ and $(2,4)$ is in the first list, where we used $(A,B)$. So $B=4$.\n
  2. $B=4$ and $(4,6)$ is in the second list, where we used $(B,C)$. So $C=6$.\n
  3. $C=6$ and $(1,6)$ is in the first list, where we used $(C,D)$. So $D=1$.\n
  4. $D=1$ and $(1,5)$ is in the second list, where we used $(D,E)$. So $E=5$.\n
  5. $E=5$ and $(5,7)$ is in the first list, where we used $(E,F)$. So $F=7$.\n
  6. $F=7$ and $(3,7)$ is in the second list, where we used $(F,G)$. So $G=3$.\n<\/ol>\n

    This reconstruction works because the two endpoints $A$ and $G$ are visited on separate trips, and it’s clear how we would extend this to the case where $N$ is any odd number. If $N$ is even, the two endpoints will be visited on the same trip and we won’t be able to distinguish them. To remedy this situation, simply leave one wire unconnected and follow the procedure with the remaining wires. The wire that was never connected will then by elimination be associated with the number $\\{1,\\dots,N\\}$ that never occurred.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    This Riddler puzzle is about tangled wires. Can you figure out how to untangle them? There are N wires leading from the top of a bell tower down to the ground floor. But as wires tend to do, these have become hopelessly tangled. Good thing the wires on the top floor are all labeled, from … Continue reading “Tangled wires”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1655,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[23,2],"class_list":["post-1649","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-logic","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1649","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=1649"}],"version-history":[{"count":13,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1649\/revisions"}],"predecessor-version":[{"id":1667,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1649\/revisions\/1667"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1655"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1649"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1649"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1649"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}