{"id":1846,"date":"2017-02-21T20:40:17","date_gmt":"2017-02-22T02:40:17","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1846"},"modified":"2017-02-23T02:57:34","modified_gmt":"2017-02-23T08:57:34","slug":"rope-timing","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/rope-timing\/","title":{"rendered":"Rope timing"},"content":{"rendered":"<p>This <a href=\"https:\/\/fivethirtyeight.com\/features\/a-riddle-how-many-crooked-politicians-are-there\/\">Riddler problem<\/a> is all about timing:<\/p>\n<blockquote><p>\nSuppose you have four ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end as you see fit. If you\u2019re strategic in how you burn the ropes, how many specific lengths of time can you measure? (For example, if you had one rope, you could measure two lengths of time: one hour, by simply burning the entire rope from one end, and half an hour, by burning the rope from both ends and marking when the flames meet.)<\/p>\n<p>Extra credit: What if you had N ropes?\n<\/p><\/blockquote>\n<p>Here is my solution:<br \/>\n<a href=\"javascript:Solution('soln_baby_poker_revisited','toggle_baby_poker_revisited')\" id=\"toggle_baby_poker_revisited\">[Show Solution]<\/a><\/p>\n<div id=\"soln_baby_poker_revisited\" style=\"display: none\">\n<p><!--In order to measure a specific length of time, we need to have well-defined events that determine the start and end of the time interval. We can't use an event such as \"when the rope is half-burnt\" since the ropes don't burn uniformly so we have no way of identifying the half-point.--><\/p>\n<p>My solution uses a recursive approach: adding one rope at a time and seeing how the set of measurable time intervals increases. Let&#8217;s start by answering simple question that will give us the key insight needed to solve the problem:<\/p>\n<p>Suppose we the ability to measure a time interval $\\tau$ and nothing else. We can imagine this as two beeps that occur exactly $\\tau$ apart. Using a single rope, what new intervals of time can we now measure? There are several things we can do:<\/p>\n<ul>\n<li> Measure the time elapsed between both beeps (don&#8217;t use the rope at all). This allows us to measure $\\tau$.\n<li> Starting at the first beep, light one side (or both sides) of the rope and measure the time elapsed between when the rope is fully burnt and the second beep. This measures $|\\tau-1|$ or $|\\tau-\\tfrac{1}{2}|$ depending on how many sides were lit.\n<li> Starting at the second beep, light one side (or both sides) of the rope and measure the time elapsed between the first beep and when the rope is fully burnt. This measures $\\tau+1$ or $\\tau+\\tfrac{1}{2}$ depending on how many sides were lit.\n<li> If $\\tau < 1$, we can also do the following thing: light one side at the first beep and light the second side at the second beep. The rope will be fully burnt at $\\tfrac{1+\\tau}{2}$, which means we can measure either $\\tfrac{1+\\tau}{2}$ or $\\tfrac{1-\\tau}{2}$ depending on whether we start counting at the first beep or the second beep.\n<\/ul>\n<p>Let&#8217;s call $f:\\mathbb{R}\\to2^{\\mathbb{R}}$ the map from $\\tau$ to the set of times you can measure when you add one rope. Based on the above, we have, for example: $f(0.6) = \\{0.1, 0.2, 0.4, 0.6, 0.8, 1.1, 1.6\\}$. Now let&#8217;s generalize to multiple measurements. If the set of times we can measure is $\\{\\tau_1,\\dots,\\tau_m\\}$, then adding one rope will allow us to measure:<br \/>\n\\[<br \/>\nf(\\tau_1) \\cup f(\\tau_2) \\cup \\dots \\cup f(\\tau_m)<br \/>\n\\]Note that in order for this to be true, the list $\\{\\tau_1,\\dots,\\tau_m\\}$ must include <em>all<\/em> the times that can be measured without needing the rope. For example, if we can independently measure $0.5$ and $0.7$, then we can also measure $0.2$ and $1.2$, so these should also be included in the original list!<\/p>\n<p>If we call $S_k$ the set of times we can measure using $k$ ropes, we can compute $S_{k+1}$ by applying $f$ to every element of $S_k$ and taking the union of the resulting sets. The result for the first few values of $k$ is:<br \/>\n\\begin{align}<br \/>\nS_1 &#038;= \\left\\{\\frac{1}{2},1\\right\\} \\\\<br \/>\nS_2 &#038;= \\left\\{\\frac{1}{4},\\frac{1}{2},\\frac{3}{4},1,\\frac{3}{2},2\\right\\} \\\\<br \/>\nS_3 &#038;= \\left\\{\\frac{1}{8},\\frac{1}{4},\\frac{3}{8},\\frac{1}{2},\\frac{5}{8},\\frac{3}{4},\\frac{7}{8},1,\\frac{5}{4},\\frac{3}{2},\\frac{7}{4},2,\\frac{5}{2},3\\right\\} \\\\<br \/>\nS_4 &#038;= \\left\\{\\frac{1}{16},\\frac{1}{8},\\frac{3}{16},\\frac{1}{4},\\frac{5}{16},\\frac{3}{8},\\frac{7}{16},\\frac{1}{2},\\frac{9}{16},\\frac{5}{8},\\frac{11}{16},\\frac{3}{4},\\frac{13}{16},\\frac{7}{8},\\frac{15}{16},1,\\dots\\right.\\\\<br \/>\n&#038;\\qquad\\qquad\\left.\\frac{9}{8},\\frac{5}{4},\\frac{11}{8},\\frac{3}{2},\\frac{13}{8},\\frac{7}{4},\\frac{15}{8},2,\\frac{9}{4},\\frac{5}{2},\\frac{11}{4},3,\\frac{7}{2},4\\right\\}<br \/>\n\\end{align}The pattern that emerges is quite interesting. The set $S_N$ consists of:<\/p>\n<ul>\n<li> $\\tfrac{1}{2^N},\\tfrac{2}{2^N},\\tfrac{3}{2^N},\\dots,1$. (a total of $2^N$ numbers)\n<li> $1+\\tfrac{1}{2^{N-1}},1+\\tfrac{2}{2^{N-1}},1+\\tfrac{3}{2^{N-1}},\\dots,2$. (a total of $2^{N-1}$ numbers)\n<li> $2+\\tfrac{1}{2^{N-2}},2+\\tfrac{2}{2^{N-2}},2+\\tfrac{3}{2^{N-2}},\\dots,3$. (a total of $2^{N-2}$ numbers)\n<li> $\\dots$\n<li> $(N-2)+\\tfrac{1}{2^2},(N-2)+\\tfrac{2}{2^2},\\dots,(N-1)$. (a total of $2^2$ numbers)\n<li> $(N-1)+\\tfrac{1}{2},N$. (a total of $2$ numbers)\n<\/ul>\n<p>In total, we can measure $2^N+2^{N-1}+\\dots+2^2+2$ different times, which sums to $2^{N+1}-2$. This is therefore the total number of times that we can measure using $N$ ropes. In the case $N=4$, we can measure $30$ different times.<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\n\\text{With }N\\text{ ropes, we can measure }\\,2^{N+1}-2\\,\\text{ different times.}<br \/>\n$<\/span><\/p>\n<p>The intuition behind the structure of the sets $S_k$ is that the numbers less than $1$ get divided in half when we add a rope, and the numbers greater than $1$ get shifted up or down by $1$ or $\\tfrac{1}{2}$. This affords us more resolution for times closer to zero. The largest time we can measure with $N$ ropes is simply $N$ hours, obtained by burning the ropes sequentially. The shortest time we can measure is $\\tfrac{1}{2^N}$ hours, obtained by simultaneously burning one rope on both ends and the remaining ropes on one end. Each time a rope burns out, light the other end of one of the remaining ropes. When there is only one rope left, it will burn for $\\tfrac{1}{2^N}$ hours.<\/p>\n<\/div>\n<p>Note: my solution is incomplete (see comments below!)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler problem is all about timing: Suppose you have four ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/rope-timing\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Rope timing&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"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":[15,2],"class_list":["post-1846","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1846","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=1846"}],"version-history":[{"count":11,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1846\/revisions"}],"predecessor-version":[{"id":1858,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1846\/revisions\/1858"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1846"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1846"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1846"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}