@@MrSonny6155 math is definitely one of the greatest inventions (or maybe "discoveries" is the right word) of all time! Allowed for so much stuff we would never be able to have otherwise. Like that phone you carry around in your pocket ;)
Not only does this generalise to _n_ hooks, it also answers the question "How long is a piece of string?" Turns out, very long if you use more than 2 hooks.
In this solution, if you increase number of hooks by 1, the string length needed is more than double of what was being used. String length grows exponentially with number of hooks. But there could be a better solution for which string length required is polynomial in n. Harder problem would be to find such a solution or to prove that no such solution exists.
Interestingly, the multiple isn't super tiny. It's an interesting problem to find the closed form solution of f(1) = 1, f(n+1) = 2*f(n) + 2, which produces the sequence {1, 4, 10, 22, 46, 94, ...}. Answer: f(n) = 3/2 * 2^n - 2
The optimal solution for 4 hooks: ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅ (16 loops). Not hard to work out and can be generalised. The generalised formula is: solution = x₁x₂⁻x₁⁻x₂ such that ⁻xᵤ cancels out xᵤ when concatenated (xᵤ⁻xᵤ = null). That is solved by writing xᵤ in reverse and inverting each letter. 1 hook: A 2 hooks: ABA̅B̅ (straightforward substitution for x₁x₂⁻x₁⁻x₂ where x₁=A, x₂=B) 3 hooks: ABA̅B̅CBAB̅A̅C̅ (x₁ = ABA̅B̅ and x₂ = C. ⁻x₁ must cancel out x₁, so is = BAB̅A̅ which is x₁ written backwards with each letter negated). 4 hooks: ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅ (x₁ = ABA̅B̅ and x₂ = CDC̅D̅. This is the shortest solution another solution is x₁ = ABA̅B̅CBAB̅A̅C̅, x₂ = D) 5 hooks: ABA̅B̅CDC̅D̅EDCD̅C̅E̅BAB̅A̅ECDC̅D̅E̅DCD̅C̅ (x₁ = ABA̅B̅, x₂ = CDC̅D̅EDCD̅C̅E̅. Again this is the shortest solution, another solution is x₁ = ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅, x₂ = E) And so on.
@@sofakartoffel1392 I honestly don't understand why Matt didn't find the optimal solution, typical Parker solution it's half-baked! Matt's solution for 4 hooks was as I mentioned x₁ = ABA̅B̅CBAB̅A̅C̅ (or the equivalent thereof), x₂ = D but with the generalised solution of x₁x₂⁻x₁⁻x₂ it's easy to see that there's a more optimal substitution to solve the equation using the solution found for 2 hooks as the the substitution. You can use the 5 hook solution to generate a 112 loop solution for 10 hooks, you can also substitute the solutions for 4 hooks and 6 hooks into x₁x₂⁻x₁⁻x₂ to get a 112 loop solution as well and either is optimal.
so the smallest solution in number of loops with 10 hooks would be made of 2 solutions of 5 hooks, meaning 4 lots of 28 loops. This naively looks like the first step in order to optimize for smallest rope length, but I suppose there's probably at least some extra step in how we order the loops themselves, they don't intuitively seem to all use the same amount of rope due to potential distant jumps... the way we position the hooks among themselves probably also makes a difference.
0:00 Now you got me curious so i went on a spree to see if Steve ever makes contact to those pipes. and HAH I found it! On the video named "Why November is the most dangerous month for trains" at 2:32 he touches the red pipe, so it does exists!
Abstract: a commutator-based approach reduces the cost of the n-hook problem to quadratic, instead of exponential. Also, numerical investigation rules out non-commutator-based solutions for 3 hooks. This is further evidence against the possibility of non-commutator-based approaches. In this post, a "sequence" is a sequence of elements of the form "loop around a specific hook, clockwise (or counter-)". Letters (a, b, ...) indicate such elements. The order of a sequence is the number of hooks in the problem. The length of a sequence is the number of its elements. The inverse of an element "loop around hook x, with this orientation" is "loop around the same hook x, with opposite orientation". The inverse of a sequence is the sequence of the inverses of its elements, in inverse order. For example: "a b c" has inverse " (inverse c) (inverse b) (inverse a)". Notice that in this way a sequence cancels out with its inverse. A commutator, indicated as [a, b], is the sequence "a b (inverse a) (inverse b)". Notice that a commutator's length is 2*(length of a + length of b). Notice that erasing any element from a commutator makes everything else cancel out. This way it is possible to prove that any sequence constructed entirely of commutators will solve the hanging picture problem. Further notice: [[[a, b], c], d] has cost 22, while [[a, b], [c, d]] has cost 16. Nesting commutators is costly: a better result is achieved "flattening" the commutators. This improves enormously over Parker's method. For sequences of order 6: [[[[[a, b], c], d], e], f] costs 94. In general, for n elements, this costs 2^n + 2^(n-1) - 2. [ [[a, b], c] , [[d, e], f] ] costs 40. For 10 elements, as they want to do: Parker's method costs 1534, while [ [ [[a, b], c], [d, e] ] , [ [[f, g], h], [i, j] ] ] costs only 112. Nesting commutators this way is easy of you have a power of 2 amount of hooks. In this case, the cost for n=2^k hooks satisfies: Cost(k) = 4*Cost(k-1) This is because if n hooks produce a pattern, 2n hooks produce [pattern, pattern] i.e. the commutator of two distinct copies of the original pattern, with cost 4 times the original cost. This recurrence relation reduces to: Cost(k) = 4^k, and since n=2^k, k=log2(n): Cost = 4^(log2(n)) = n^2. This applies only for power-of-2 integers, but non-power-of-2 integers are easily bounded above by their next bigger power of 2. Credits to user mstmar for the idea of nesting commutators. For three hooks, the 10-long sequence found in the video is of minimal length - I checked all combinations via a script. (I can provide the ugly unoptimized python code upon request). This leads me to suspect that the commutator-based approach cannot be improved upon, except by rearranging the commutators. While there are many optimizations to be made, I think doing a search for n=4 is unfeasible without industrial-size compute, and unlikely to yield significant improvement. The size of any pattern of order power-of-2 is directly proportional to the size of the pattern of order 4 that underlies it, but the current order 4 pattern has length 16 and no significant improvement appears likely. Finally, for the real-life version of the problem that takes into account the real-world distance between hooks, further work may be required. Thank you for your attention.
You're basically solving the 2-hook problem many times and nesting the solutions in a binary tree. And I think the strategy is the most efficient if all you've got it the same 2-hook solution. I wonder though if there are other ways. Eg, are there any 3-hook solutions that don't look like [[a,b],c]?
On the other hand, optimizing the commutator based approach is quite easy: If (N) is the minimal cost for a commutator based approach on N hooks, then (N)=min{2*(k)+2*(N-k)|1=2*(k)+2*(N-k) (since A and B must in total contain at least N letters). On the other hand, for A and B as optimal commutators for k and N-k, we get equality here, hence 2*(k)+2*(N-k) is a minimum for A containing the fixed number of k letters. Finding k such that this term gets minimal thus yields the minimum cost for N. Using dynamic programming we can find these values efficiently.
Ok, I implemented it and it looks like this: If the biggest power of two smaller or equal to N is P, then the/an optimal split is P/2, N-(P/2). e.g. N=10: [10]=[4,6]=[[2,2],[2,4]]=[[[1,1],[1,1]],[[1,1],[2,2]]]=[[[1,1],[1,1]],[[1,1],[[1,1],[1,1]]]] has cost 112. written down: a^{-1}=A [4]=abABcdCDbaBAdcDC [6]=efEFghGHijIJhgHGjiJIfeFEijIJghGHjiJIhgHG [10]=abABcdCDbaBAdcDCefEFghGHijIJhgHGjiJIfeFEijIJghGHjiJIhgHGcdCDabABdcDCbaBAghGHijIJhgHGjiJIefEFijIJghGHjiJIhgHGfeFE
@Neel Shukla Actually, as I read some other comments, I saw that any split in the range (n/2-p/2,n/2+p/2) is optimal, my cut just happened to be the smallest optimal cut.
You just need to arrange hooks from the middle to sides, like 9, 7, 5, 3, 1, 2, 4, 6, 8, 10 to have final string shorter. Just because first hooks are being meet in algorithm more frequently. Also I think that the most suitable thread for this purpose is one of those used for fishing. They have some cords which flex not much and they designed to reduce friction
@@NoobLord98 Glow in the dark fishing line? What's the point of that? Definitely not fishing. The point of fishing is that the fish DOESN'T see anything suspicious.
13:49 maybe a 6th method. (gold plated goof did a 5th method (same principle as matt, different generalization)) He did A B A' B' C D C' D' B A B' A' D C D' C' (16 moves compared to Matt and Steve's 22) Where A' = A inverse
Interestingly, there's a lovely acronym that explains exactly Matt's algorithm. DRII: Duplicate, Reflect / Reverse (makes abAB -> BAba), Inverse (makes abAB -> ABab), and Inject (makes abAB + baBA -> abABcbaBAC). DRII can be expanded to the nth integer term, which I think is really interesting.
16:49 "So the challenge is for some large number of hooks, what's a really short way of doing it." Challenge accepted: My suggestion to extend from n to n+1 hooks would be that: 0) Use solution for n hooks 1) search first least used character x (y is the successor of x in natural order == A < B < C...) 2) Shift every bigger character (in natural order) by 1 3) Replace first letter used least with solution for two hooks x and y From 2 to 3 hooks: 0) use: A B A̅ B̅ 1) x = A, y = B 2) shift => A C A̅ C̅ 3) replace A with A B A̅ B̅ and A̅ with B A B̅ A̅ => A B A̅ B̅ C B A B̅ A̅ C̅ length: 10 cord length: 10 From 3 to 4 hooks: 0) use: A B A̅ B̅ C B A B̅ A̅ C̅ 1) x = C, y = D 2) shift => A C A̅ C̅ 3) replace C with C D C̅ D̅ and C̅ with D C D̅ C̅ => A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ length: 16 cord length: 18 From 4 to 5 hooks: 0) use: A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ 1) x = A, y = B 2) shift => A C A̅ C̅ D E D̅ E̅ C A C̅ A̅ E D E̅ D̅ 3) replace A with A B A̅ B̅ and A̅ with B A B̅ A̅ => A B A̅ B̅ C B A B̅ A̅ C̅ D E D̅ E̅ C A B A̅ B̅ C̅ B A B̅ A̅ E D E̅ D̅ length: 28 cord length: 33 Similar from 5 to 10 hooks (use solution for 5 hooks and insert solution for 2 hooks; imlicit shifting using appropriate letters) use: A B A̅ B̅ C B A B̅ A̅ C̅ D E D̅ E̅ C A B A̅ B̅ C̅ B A B̅ A̅ E D E̅ D̅ replace E with I J I̅ J̅ and E̅ with J I J̅ I̅ => A B A̅ B̅ C B A B̅ A̅ C̅ D I J I̅ J̅ D̅ J I J̅ I̅ C A B A̅ B̅ C̅ B A B̅ A̅ I J I̅ J̅ D J I J̅ I̅ D̅ replace D with G H G̅ H̅ and D̅ with H G H̅ G̅ => A B A̅ B̅ C B A B̅ A̅ C̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ C A B A̅ B̅ C̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅ replace C with E F E̅ F̅ and C̅ with F E F̅ E̅ => A B A̅ B̅ E F E̅ F̅ B A B̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A B A̅ B̅ F E F̅ E̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅ replace B with C D C̅ D̅ and B̅ with D C D̅ C̅ => A C D C̅ D̅ A̅ D C D̅ C̅ E F E̅ F̅ C D C̅ D̅ A D C D̅ C̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A C D C̅ D̅ A̅ D C D̅ C̅ F E F̅ E̅ C D C̅ D̅ A D C D̅ C̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅ replace A with A B A̅ B̅ and A̅ with B A B̅ A̅ => A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ E F E̅ F̅ C D C̅ D̅ A B A̅ B̅ D C D̅ C̅ B A B̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ F E F̅ E̅ C D C̅ D̅ A B A̅ B̅ D C D̅ C̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅ length: 112 (= 28 * 4) cord length: 154 I hope, there are no flaws... Edit: just noticed, i posted the length of the rule (in letters) instead that of the cord, so i added the cord length too. Hopefully that's not irritating.
I found a way to get shorter sequences. I'm sure it's not optimal, but at least better than the one presented. My approach does xyXY where x and y are solutions for smaller problems and capitals are inverses. your approach is a special case of mine where x contains all hooks but one and y is the last hook. my approach checks all combinations of x and y to find the best partition of hooks that gives the lowest length. an example for n = 4 can split its hooks 1/3 or 2/2. The 1/3 case gives your solution to n = 4 and the 2/2 case is abAB cdCD baBA dcDC, length 16 vs 22, so 2/2 split is chosen. I'm pretty sure that having balanced hooks (or 1 off for odd n's) gives the smallest length (for this approach anyways). however, for n=6 you can get a length of 40 in 2 ways (3/3 split or 2/4 split). so for big n's, there might be a better split than even. an other advantage of this approach is that you stay localized the same half of hooks for each 1/4, most likely saving even more rope (in addition to needing less loops), compared to jumping to the end and back every 4 loops. this approach lowers the n=10 that you wanted to attempt from 1534 loops to 112, a much more manageable feat. oddly, n = 10 also has 2 ways of getting to 112 loops: 5/5 or 4/6. It also would have saved the 5 people on the stage a little trouble too, as it would only have taken 28 loops instead of the 46. Could have even added a 6th person with a similar tangle (40 loops).
After studying it for some time, I can prove by induction that taking balanced splits (1 off for odd n) is always best. It is also relatively easy to show by induction that if we call f(n) the number of steps needed (with this method) is always at least n^2, with equality if and only if n is a power of 2. What is much more surprising is that we can always spread a split until we reach a power of 2, for example f(12) = 2(f(6) + f(6)) = 2(f(5) + f(7)) = 2(f(4) + f(8)) This explains why we often have several solutions, especially for large n (but remember, we can't be better than an even split). Still, as it only grows as n^2, this is much more efficient than their solution, which grows as 2^n. You can easily show f(n) < 4n^2 (take the smallest k such that 2^k ≥ n, and check that f is strictly growing, then we have f(n) < f(2^k) = (2^k)^2 < (2n)^2 = 4n^2), and with some work f(n) < 5/2n^2 (first prove that f(3*2^k) = 10/9(3*2^k)^2, then use the same argument as before). It even seems like f(n) < 1.3n^2, which would be really close to n^2.
This reasoned approach is much better than my first thought: brute force. With a solution length that is at most approximately 2^n we get a search space of only about a 1000 long for n=10, so that should be feasible, right? Nope. That ignores the fact that with a pure brute force method (n hooks and k loops for your shortest solution) you actually have a search space of (2n)^k (both directions for each hook, repeat pick k times). For n=10, k=112, and t_check=50ms, a pure brute force would finish after about 8e135 years, which is well after we expect supermassive black holes to have evaporated into Hawking radiation (1e100 years). Turns out a pencil can still beat a CPU.
@@swerasnym That paper gives the algorithm but does not establish optimality, it only conjectures it. This paper also establishes its optimality and counts the number of different minimal-length solutions: eudml.org/doc/282667 . The provenly optimal lengths of solutions for n nails are also given by the OEIS sequence A073121. Namely, for n = 2^m + k with k < 2^m the optimal solution length is 2^m*(2^m + 3k) which grows asymptotically quadratically in n, as O(n^2). For n = 10 this gives that a solution of length 112 is indeed optimal. Intriguingly, all of this applies only to the case when the string is only allowed to loop aroud the nails, but not around itself (giving a "simple Brunnian link" for solutions of the puzzle, in the parlance of the paper). If loops of the string around itself are allowed (i.e. "knotting"/linking the string with itself) then only a linear number (O(n)) of crossings of the string are required (see Fig. 8 in your cited arXiv paper), not the quadratic number (O(n^2)) if these aren't allowed. Your cited arXiv paper gives 8*n as a candidate solution in this case but does not claim it is optimal. I don't know if it is an open question or not as to what the lowest number of string crossings required is, but it does seem interesting to consider. :)
There's a nice topological way to view this. You're looking at the fundamental group of the plane with n-many holes and discussing what elements of the group, when projected onto the plane with (n-1)-many holes, return the trivial element of the group. To be more precise, the fundamental group of the plane (or, homotopically equivalent, the n-petal graph), is the free group generated by n-many variables. Consider then the projection map, say, called P_i, from F(x_1, x_2, ..., x_n) to F(x_1, x_2, ..., x_(i-1), x_(i+1), ..., x_n). This is a group homomorphism, and its kernel is the subgroup generated by g^m * x_i^n * g^(-m), for g in F(x_1, x_2, ..., x_(i-1), x_(i+1), ..., x_n). The problem you're asking about in the video, or just the general problem, is finding elements of the intersection of the kernels of all the project maps P_i. I gave this a shot and came up with the same answer found in the video, i.e. a middle element serving as a barrier between a string of mirrored inverses on each side.
I've got a solution to the scaling problem which leads to fewer symbols (e.g., less rope) for longer sequences. Conceptually, rather than focusing on adding new pegs at the end, I imagine that the pegs we already have are getting duplicated: so the rope that used to go around one peg is now going around two pegs together. The question then becomes how to ensure that the picture falls if either of those two pegs is removed. We can consider going from the trivial one-peg case to the two-peg case to be exactly this problem, and so can adapt the two-peg solution. To be specific, any time we have a clockwise turn which we want to turn into turns around two pegs, we replace it with AbaB (where A is the first peg, B is the second, and capital letters mean clockwise turns while lower-case mean counterclockwise). Likewise, we replace any counterclockwise turns with bABa. This will quadruple the total number of symbols, but in the long run, quadrupling the number of symbols whenever we double the number of pegs is better than (more than) doubling the number of symbols when we add a single peg. To give an example of how effective this is, here's my four-peg solution, as before with capital letters being clockwise turns and lower-case being counterclockwise: AbaBcDCdbABaDcdC If you remove any of the pegs (e.g., remove any of Aa, Bb, Cc, or Dd from that sequence), the rest will collapse. This 16-symbol sequence is shorter than the 22-symbol sequence presented in the video, already demonstrating the effectiveness of this approach. The savings would be even more evident if going to higher numbers of pegs.
Funny, that solution looks a lot like commutators in rubik's cube The notation for them is [A; B] and that means ABA'B' So the solutions with 3 hooks can be noted [[A; B] ; C] I wonder how you could add conjugates, another tool in rubik's cube ([A: B] = ABA') in the picture frame story...
I wanna look at [[[A;B];C];D] vs [[A;B];[C;D]]. [[[A;B];C];D] = ABA'B'CBAB'A'C'DCABA'B'C'BAB'A' [[A;B];[C;D]] = ABA'B'CDC'D'BAB'A'DCD'C' hmmmmmm... dat one's shorter...
@@JNCressey We want a nested commutator involving every variable (i.e., every hook) and that is as "shallow" as possible (to minimize the expanded length). That's how [[[A;B];[C;D]];[[[E;F];[G;H]];[I;J]]] gives us a solution with only 112 loops for 10 hooks
@@VaradMahashabde if you check Steve Mould's newest video about levitating water, the picture is featured in the background. At 6:37, he edited it to say "Humble Tau" for a bit, being a refference to a Numberphile video where Matt and Steve debated for which is better. (Steve stating Tau is better abd Matt stating it depends on 2Pi or half Tau)
Now, I occasionally make a habit of constructing a fractal called a dragon curve. It's made with a series of clockwise and anticlockwise 90 degree turns. Each increasing step adds a clockwise turn, then mirrors every previous step in reversing order, inversed the same way as done in this video when demonstrating the addition of D. That's fascinating to me.
One can get smaller solutions by using different groupings. Instead of going from 1) A*B*C to (A*B*C)*D treat (A*B) and (C*D) as one hook and calculate the solution 2) (A*B)*(C*D). The number of steps for approach 1) is a(n)=3*2^(n-1)-2 (n is the number of hooks). This follows from the recurrence a(n+1)=2*a(n)+2, a(1)=1 For the second approach one gets the recursion b(2m)=4*b(m) b(2m+1)=2*b(2m)+2=8b(m)+2 yielding b(2^m) = 2^(2m) = 4^m (this is actually only quadratic in the number of hooks). Finding a solution for three hooks that is shorter than 10 steps would make the bound for an uneven number of hooks even better.
That's interesting. So is the solution for ABC·D the same as AB·CD? In other words, if you make a four-hook solution by combining a three-hook solution with an extra hook, do you get the same as combining two two-hook solutions together?
I'm surprised that you guys didn't point out the nice expandable.. almost fractal-like pattern that you're doing; You're even wearing a recursive T-Shirt! ( AB A'B' ) Just becomes the new A, and B is the next pin, and you can expand that out forever. It's the same for ( AB' A'B )
because you guys seemed to be coming across stuff in real time, this watches almost like a visual podcast - was a really cool video style! hope to see more similar stuff in the future, keep it up guys!
I really love this kind of thing where it's a real solution, multiple methods, all the same results. In algebra and all the maths up from there, I have always struggled with that kind of thing, (i know rearranging a problem doesn't fundamentally change it, but messy hand writing and a tendency to misread characters really interferes with that) so seeing the same solution, solved with three different trains of thought is just awesome. It's why I really like Those videos where Pi is hiding everywhere, and why it would be. Great content! Just hit the part of the video with the N dimensional cubes and I am losing it.
@15:15, you suggest the shortest path through all vertices also generates a solution. If you label that path as A B' A' C A B A' C', then you'll notice that if the A's are removed, the resulting loop B' C B C' does not degenerate. That's because the path you've traced out, when projected onto 2 of the planes, degenerates. But when projected onto the third plane (BC), the path is a loop around a circle.
when you ask a man of physics and a man of mathematics to solve a question...you find different answers...then things comlicate when you add a compurer programmer to the mix...SCOTT SOLVE THIS QUESTION!(by scott i mean tom scott)
The ending bit reminded me a LOT of a solitaire card game called "Accordion", where similar sandwich/removal occurs. I'm wondering if some of the thought process of playing that game would come into play here.
WARNING: long comment ahead, but I believe there is an efficient algorithm for *doubling* the number of hooks at each step, rather than adding 1 at a time. I've tried to explain it as coherently as possible over text, and I'd greatly appreciate anyone who could verify this method or point out any mistakes. *ALGORITHM EXPLANATION* Steps of the algorithm: Step 1: Start with the 2 hook solution: A B A' B', where A stands for a clockwise string turn around hook A, and A' is anticlockwise (counterclockwise for us 'muricans) Step 2: Consider an entirely separate 2 hook solution, with hooks C and D. of course, the solution is still the same: C D C' D' Step 3: Consider both separate two hook systems as two individual hooks, let's call them X and Y. Step 4: Naturally, the solution for the XY system is: X Y X' Y' Step 5: Substitute our original hooks, ABCD, into the new solution. BUT WAIT: we know X and Y, but what does X' and Y' look like? that's simple: X' is just everything in X, but in reverse order. So if X = A B A' B', then X' = B' A' B A. this ensures that X and X' will fully cancel each other out when they "collide" Final result: X Y X' Y' becomes: A B A' B' C D C' D' B' A' B A D' C' D C You can test out yourself: remove any one of the hooks, and the others will collapse and cancel each other out. *COMPARING THIS ALGORITHM WITH MATT AND STEVE'S ALGORITHM* Now, the interesting thing to note is how many "turns" of string we have: the final solution ends up with ONLY 16 turns, whereas Matt and Steve's algorithm resulted in 22 turns for 4 hooks. The equations for # of turns vs. number of hooks for each algorithm are as follows: Matt/Steve algorithm: t(n) = 2 * t(n-1) + 2 (where: n > 1) (in layman's terms: adding 1 hook causes the number of turns to double, plus 2) My doubling algorithm: t(n) = 4 * t(n/2) (where n >= 4, and MUST be a power of 2) (in layman's terms: doubling the number of hooks quadruples the number of turns) *TACKLING THE CHALLENGE OF 10 HOOKS* Of course, you can use this algorithm to continue doubling the number of hooks as much as you want. For example: if you want 8 hooks, simply take the solution for 4 hooks above (X Y X' Y') and name it as a single hook, lets say W. Then, let's also define V, which is another system of 4 hooks. Then, a system of 8 hooks has the solution W V W' V', with a total of 16 * 4 = 64 turns. Regarding Matt and Steve's challenge of 10 hooks: Using my algorithm, you can solve an 8 hook system with 64 turns of string, but unfortunately, the efficient doubling method can't add the last 2 hooks. For those, we need to use the algorithm in the video. So, using the formula t(n) = 2 * t(n-1) + 2, we can see that: t(9) = 2 * t(8) + 2 = 2 * 64 + 2 = 130 t(10) = 2 * t(9) + 2 = 2 * 130 + 2 = 262 So I predict that a 10 hook system can be solved with at least 262 turns of string, but there may be a more efficient way to add those last 2 hooks to the system. I'll leave that to someone smarter to figure out ;)
After some thinking, I realized this can be generalized to not just doubling the # of hooks, but adding any amount of hooks (m) to an existing system of n hooks. Let X = existing system of n hooks, represented as a single hook. Let Y = new system of m hooks being added, represented as a single hook. Solution for X + Y is X Y X' Y' The new number of "turns" of string needed for this solution is: t(n+m) = 2 * t(n) + 2 * t(m) *(Generalized solution)* We can show that both Matt and Steve's algorithm, and my algorithm above, are special cases of this general solution: Matt and Steve's algorithm is where m = 1, so: t(n+m) = 2 * t(n) + 2 * t(m) = 2 * t(n) + 2 * t(1) = 2 * t(n) + 2 (since we know that the solution for n = 1 is trivial: just 1 turn of string) The doubling algorithm: t(n+m) = 2 * t(n) + 2 * t(m) = 2 * t(n) + 2 * t(n) = 4 * t(n) (since m = n) Given this, we can compute the minimum (theoretically) # of turns for 10 hooks: t(10) = 2 * t(8) + 2 * t(2) = 2 * 64 + 2 * 4 = 128 + 8 = *136* So we should expect 10 hooks to be solved with at least 136 turns of string
Small mistake in step 5. X' isn't just X reversed, but also each term inverted. So if X = A B A' B', then X' = B A B' A' so that in XX' you get B'B, A'A... which cancel and not B'B', A'A'... which don't. Also as an addition to what Zaheen Ahmed said, t(10) can also be split other ways than 8/2. if we split it 5/5, we get t(10) = 4*t(5) = 4*(2*t(3)+2*t(2)) = 8*(10+4) = 112. Even more savings!
@@zaheenahmed304 I was thinking about the same strategy, and wrote the sequences down. You are right. This is the 4 hook sequence (length 16), broken up in its four components: ABA'B' CDC'D' BAB'A' DCD'C'. And this is the 8 hook sequence (length 64), split up in fours as well: ABA'B'CDC'D'BAB'A'DCD'C' EFE'F'GHG'H'FEF'E'HGH'G' CDC'D'ABA'B'DCD'C'BAB'A' GHG'H'EFE'F'HGH'G'FEF'E'. We can use this to create the 10 hook sequence (length 136): ABA'B'CDC'D'BAB'A'DCD'C'EFE'F'GHG'H'FEF'E'HGH'G'CDC'D'ABA'B'DCD'C'BAB'A'GHG'H'EFE'F'HGH'G'FEF'E' KLK'L' EFE'F'GHG'H'FEF'E'HGH'G'ABA'B'CDC'D'BAB'A'DCD'C'GHG'H'EFE'F'HGH'G'FEF'E'CDC'D'ABA'B'DCD'C'BAB'A' LKL'K' You can clearly see the structure. First comes the 8-hook sequence, followed the 2-hook sequence, followed by the reverse 8-hook sequence, and the reverse 2-hook sequence seals the deal.
@@verfmeer Yep, that should be the sequence. I salute you for actually writing it out, I didn't have the patience for it haha (Now, we patiently await Matt and Steve attempting to do this with actual hooks and string...)
honestly seeing Matt’s method and being able to compare it with what Steve and Jade have done, I’m quite amazed by how a flexible thing this naughty knotty problems actually are. I mean steve’s method is something I would never think off knowing myself but what Matt has done is like a „method to madness” kind of approach. God i love how with those carts you completely forgot about the physical situation by just knowing those two clowiseness-hook axioms God i just had to write this down somehow cause it is kind of a illumination type a moment for me
You Don't need to double each time, for four you can go aba/b/cdc/d/bab/a/dcd/c/ You put in the new letter as a commutator with a previous letter. for replace a clockwise it goes in the form aba/b/ where a is the old letter and b is the new letter, and when replacing anticlockwise you go bab/a/. So starting from 1 hook 1 hook solution: a 2 hook solution: aba/b/ 3 hook solution: aca/c/bcac/a/b/ 4 hook solution: aca/c/bdb/d/cac/a/dbd/b/ 5 hook solution: aea/e/ceae/a/c/bdb/d/caea/e/c/eae/a/dbd/b/ however when moving from 2 hooks to three hooks it is more efficient to use your doubling method since adding the commutator adds more than double the letters. this changes the solutions to 1 hook: a 2 hook: aba/b/ 3 hook: aba/b/cbab/a/c/ 4 hook: aba/b/cdc/d/bab/a/dcd/c/ 5 hook: aea/e/beae/a/b/cdc/d/baea/e/b/eae/a/dcd/c/ doubling each odd number of hooks is also less efficient due to the fact that when using this commutator extension method you add three per letter you are commutating with whereas with the doubling method you multiply the terms by 2 and add 2.
There's a solution that's precisely doubling (marking clockwise rotation with a,b,c,d and counterclockwise with A,B,C,D): for two pins A and B we have the same solution as before: abAB, but now let's assign this combination of steps the letter x and give the letter X its inverse: baBA. The letter y will be the equivalent thing for pins C and D - cdCD, and for Y we have dcDC so if we combine X and Y in the same way (xyXY) and expand we now have: abABcdCDbaBAdcDC, which is 6 steps shorter than the solution you presented in the video for 4 pins.
I found simpler solutions than what your method gives for a bigger number of hooks (>3). You just have to encapsulate a group of hook into a single abstract hook with an algorithm that represent the clockwise an anti-clockwise turn. If one of the hook in the group is removed, the whole abstract hook is removed. And if a clockwise turn is followed by an anti-clockwise turn (or vice versa), everything is undone just like how a real hook would behave. Here an example with 4 hooks : - Your method in 22 steps : ABabCBAbacD CABabcBAbad - This method in 16 steps : ABab CDcd BAba DCdc I grouped the hooks A and B (respectively C and D) into an abstract hook with the abstract clockwise turn ABab (respectively CDcd). Here's the best results I get with the 10 first hooks : Note: the x operator means I combine two previous solutions and the +1 operator means I use your method to use the previous solution Hooks: Steps -> Combinations of Hooks 1: 1 2: 4 3: 10 4: 16 = 4*4 -> 2x2 5: 34 = 2*16+2 -> 2x2+1 6: 40 = 4*10 -> 2x3 7: 82 = 2*40+2 -> 2x3+1 8: 64 = 16*4 -> 2x4 9: 100 = 10*10 -> 3x3 10: 136 = 4*34 -> 2x5 We might add this sequence to the OEIS eventually ...
I pictured a number of long parallel rods fairly close together and imagined each pass of the rope getting placed down a little farther along the rods. For a large number of rods-needing a very large number of passes-the rope would end up covering a significant area. It would look a bit like woven cloth, particularly if the rope was thread or yarn. Then it struck me, what if the rods were also thread or yarn? You would actually have a cloth that would completely fall apart (friction ignored) if one of those warp threads was cut. Unraveling cartoon sweater, eat your heart out.
5:40 it looks like connecting all of them same way AND adding anchorage. And that is propably how to run it. a way to stop it from doubling each node is in self-undooing knots, but combining correct one with rest of the algorithm is not easy.
You can make them shorter by substituting your last expression into both a and b, not just one of them (i.e. doubling the amount of nails each time). This way you get around n^2 turns for n nails, not 2^n+2^(n-1)-2 like you get.
Couldn't you say that the only solution is the one for two hooks? If you have any more hooks you would group them together until you have only two. Your method seems to group all the hooks except the last one together so for three hooks it would be (AB),C,(AB)',C' and for four hooks it would be (ABC),D,(ABC)',D'.
Here's a question: is there a way to do this so the weight of an object hung from the string is as evenly distributed as possible across the N points? My thinking is that this could have some sort of practical application where something is being suspended evenly and could be quick released. In the examples, the Nth point would have a significantly less amount of string around it than the earlier points. Maybe the points could even be extended into a second dimension to suspend 3-dimensional objects (or just orthogonal 2-dimensional objects).That bit would be wholly impractical but it's fun to ponder.
You could group them, correct? If you need 10 hooks, simplify to 5 groups of 2, because it's effectively the same. Treat each group as a single hook, since removing one part of the group would remove the group as a whole. Since you've shown it possible to be done with 3 as well, you should be able to do any number, I would think.
Wow, cool, I think you are right! But although this makes the number of logical steps smaller, the actual dependencies of which hooks the string pass over do not get simpler.
@@youtubeuniversity3638 Not really, that would only be true if we had to divide them evenly. Take 7 for example, it can be done by making three groups, with 3, 2 and 2.
You can save a bit of string by going with a divide-and-conquer method: So instead of taking a solution s for n hooks and a solution t for 1 hook and combining them as stST (where capitalization denotes reversing the order and the direction around each hook) to get a solution for n + 1 hooks, you can take two solutions s and t for half the hooks and combine them as stST. For example, instead of abABcbaBACdcabABCbaBAD (of length 22) you get abABcdCDbaBAdcDC (of length 16) for four hooks.
God, I love Matt's theme song. One of my absolute favorites and it lives in my brain permanently. I would say "rent-free", but it's probably a drag on my productivity to be humming it so often.
When I watched Jane's original I tried to correlate it to graph theory and got close to your cube solution using the chinese mailman problem, you guys should look into it for a possible smaller solution.
+standupmaths You could get a shorter card sequence (16 vs 22 cards) if you: 1) Split the original sequence just before the C card 2) Add D and D̅ respectively to the ends of the second partial card sequence 3) Take the reverse conjugate of the CD end pairs 4) Add those end pairs respectively to the ends of the first partial card sequence Thus, the new sequence would be: C̅DAB̅A̅BD̅CDC̅B̅ABA̅CD̅
16:08 My brother walked in with a gerbil and asks "why are you watching a video on how to hang a picture, why is it 18 minutes long and why are you 16 minutes in?" What am I supposed to say?
Let him know that it relates to hanging the picture in space, and that the Gerbil Space Program is conditioning the gerbils to understand that hooks and loops will allow zero-G environments to sustain a hanging picture, on as many or as few hooks as needed, provided it is not hung with any of the methods mentioned in the video. Also, explain that 18 minutes is roughly the total attention span in minutes of a gerbil, and that you are 16 minutes in, but only by appearances, because it was paused a few times and you would have been done by now if you didn't have to explain the previous information.
Maths at its finest! When there's multiple different methods of approaching a problem, using diverse areas of mathematics, and they all provide equally valid solutions! Love it!
Gotta admit, that looks like a superpermutation with how horrific the sequence is. That being said, the superpermutation for n is still much, much more horrifying...
Engineer: How can I design this system without a single point of failure... Mathematician: That's too easy, theoretically speaking, How about designing a system with only single points of catastrophically failure?
Expanding on Matt Parker pointing out that the solutions to the puzzle can be represented as a path through vertices on the cube, we can generalize to N dimensions by considering an n-dimensional cube with volume of 1 and a corner fixed at the origin and the axes defined by all the edges at that vertex. We have now the following observations: a) Any solution must pass through all the vertices that are distance 1 from the origin. b) No solutions can contain path segments that backtrack (ie, in the 3-dimensional case, (0,0,1) -> (0,1,1) -> (0,0,1) and the like would be backtracking). c) The distance between each vertex in the path must be 1. Axiom a) ensures all hooks are utilised, axiom b) removes isomorphic solutions, and axiom c) comes from the clockwise/anticlockwise turns around a hook translating to positive/negative direction of travel along the axis defined by the coordinate of the hook. The minimal solutions (shortest amount of string), are paths such that the magnitude of the vector from the origin is minimized at each step.* There is an algorithm to do compute this efficiently (O(n) in both space and time), but the youtube comments section are not large enough to contain it.
The cube is not equivelant. A,-B,-A,C,A,B,-A,-C goes through all vertices on a cube but does not follow the hanging of the painting pattern since the removal of A does not drop the painting
Here is a paper formalizing this kind of things: erikdemaine.org/papers/PictureHanging_TOCS/paper.pdf I've had good use for it in a programming contest once. :)
Their solution iteratively builds up from 2 hooks adding one each time. multiplying the number of hooks by 2 each time gives a significantly smaller number of turns 2^n vs n^2. Their solution treats the previously solved hook as a single hook. They than add the simple clockwise and counter-clockwise for the second hook. > first second first* second* > aba*b* c bab*a* c* However you could consider a previously solved hook to both be the first and second hook which would double the number of hooks solved and only multiply the number of turns by 4. > first second first* second* > aba*b* cdc*d* bab*a* dcd*c* The recurrence relation for their solution is t(n) = 2*t(n-1)+2 > 2^n where n is the number of hooks and t(n) is the number of turns. Some terms in that sequence starting from n = 2 are 4,10,22,46,94,190,382,... My solution is t(n) = 4*t(n/2) = n^2. For n = 8, their solution takes 382 turns while mine takes 64. At n = 16 mine still takes less at 256 turns.
Nice! Good to know I'm not talking complete gibberish, I explained the exact same idea in my comment: ruclips.net/video/x5h3yTxeCew/видео.html&lc=Ugzaw6rERFQ1Qr4sxCt4AaABAg (insert something about great minds think alike, etc etc)
Matt saying "Maths!" with his hands in the air after noting that three people came up with the same solution different ways made me laugh so hard. 11:49 - 11:55
I wonder what the solutions look like if the frame should fall when exactly any k out of n hooks are removed. The k=n case is what 'normal' people are aiming for and is just clockwise around all hooks; The k=n-1 case is trivial: clockwise around all hooks then counterclockwise around all hooks; And the k=1 case has the easy solution you showed and at least a nice shorter solution. But are the solutions for other 1 < k < n-1 easily generated?
To add yet another way of thinking about this problem, consider the free group on 3 generators, , and the natural homomorphisms to the groups generated by , , and which correspond with "pulling out" the a, b or c "hooks" respectively. The problem is then to find a non-trivial element which is in the kernel of all three homomorphisms. The element a b a^-1 b^-1 c b a b^-1 a^-1 c^-1 is in all three kernels.
Looking at the cube traversing problem, a more efficient induction from n to n+1 dimensions is: 1) remove final step (so no longer go back to start) 2) add a move in new dimension 3) perform old algorithm in reverse removing final step (ie the thing from 1) but backwards), 4) undo move in new dimension. Applying this to your algorithms for 2 pegs seems to give a successful algorithm for 3 pegs. I imagine that commutator theory would be really helpful in these kind of problems.
I've seen the puzzle a bunch of times so I wasn't that excited, but when Matt then showed it was analogous to pathing around n-cubes it suddenly became extremely exciting.
Should be able to make an arbitrarily large number of hooks solution, right? I.E. 3 hooks = AB'A'BCAB'ABA'C'. LET X = AB'A'B and X' = B'ABA'. We then substitute to: XCX'C' which is in the form of the 2 hook solution Using the symbols to make a 3 hook solution: XC'X'CDC'XCX'D'. Substituting the Xs back should give a 4 hook solution: AB'A'BC'B'ABA'CDC'AB'A'BCB'ABA'D'. I think this could be done in a script fairly efficiently, in case you want to make one that's 200 long or whatever.
itchykami yes, this is the algorithm (more or less) that they presented in this video. Their question is if there are solutions that produce shorter patterns than this algorithm does.
It can be done really efficiently in the sense that writing a program that runs in time linear to the size of the solution is fairly easy. It cannot be done really efficiently in the sense that the final solution is exponential on the amount of hooks. Maybe a different family with a linear or quadratic (or, generally, polynomial) amount of turns exists, but we don't know it. Now THAT would be a lot more efficient. By the way, generating the solution for 200 hooks using this family of solutions would give something like 2^201 = 2*2^200 = 2*(2^20)^10 turns, which is about 2*(10^6)^10 or 2*10^60. Assuming you can process a billion (10^9) turns per second (reasonable estimate for a modern x64 CPU), and that your algorithms instantly finds the sequence and all it has to do is put it in memory, finding the solution for 200 hooks takes at least 2*10^60/10^9 s = 2*10^51s =~ 10^46 years (very rough approximation on this last step, i did all calculations in my head)
Tbh: This video perfectly describes why I love maths. You can do as many different creative ways for solving something as you want, as long as you do them properly you'll get the right solution.
Well i think i have a great solution that works for any number of hooks but it requires one extra item sadly, a pair of scissors, now you might call that cheating but i tend to think its just a creative way of solving the problem :P
My approach (having sat and thought about it for a little bit and having put in not a lot of effort) you only need to cancel out passes over the hooks as passes under the hooks would simply fall to the ground regardless, so if you pair off hooks into groups of 2 (when working with an odd number do a group of 3 as shown in the video for as few iterations as possible) as if you start each pair with a pass over the first hook them you are simply doing the same 2 hook or 3 hook problem again
![Recursive PowerPoint Presentations [Gone Fractal!]](http://i.ytimg.com/vi/b-Fa6HtvGtQ/mqdefault.jpg)
![Recursive PowerPoint Presentations [Gone Fractal!]](/img/tr.png)
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Q: "Why do I need to study math?"
A: "Well, if you ever want to maximize points of failure..."
Some people just like to watch the world burn, so that's why we invented maths.
But by understanding something new, which you would not otherwise, you are reducing points of failure! D:
This effort is hopeless!
This comment proves that engineering & mathematics are the exact opposite of eachother.
@@MrSonny6155 math is definitely one of the greatest inventions (or maybe "discoveries" is the right word) of all time! Allowed for so much stuff we would never be able to have otherwise. Like that phone you carry around in your pocket ;)
@@MrSonny6155 It takes science to make an atom bomb. :)
Not only does this generalise to _n_ hooks, it also answers the question "How long is a piece of string?"
Turns out, very long if you use more than 2 hooks.
In this solution, if you increase number of hooks by 1, the string length needed is more than double of what was being used. String length grows exponentially with number of hooks. But there could be a better solution for which string length required is polynomial in n. Harder problem would be to find such a solution or to prove that no such solution exists.
It takes much less string if your hooks are infinitely close together and your string is thinner than the gaps
@@nicholasgunter3838 that would just be multiplying 2^x by a tiny tiny scalar, but it still blows up exponentially :P
Interestingly, the multiple isn't super tiny. It's an interesting problem to find the closed form solution of f(1) = 1, f(n+1) = 2*f(n) + 2, which produces the sequence {1, 4, 10, 22, 46, 94, ...}. Answer:
f(n) = 3/2 * 2^n - 2
hi again :)
"We should thank Tom Scott eventhough he has done literally nothing" well. Thanks for nothing also is a phrase that exists.
@@monikafiori that's the joke.
Aw, I was looking for a comment from the real Tom Scott somewhere under this video.
Lol i was literally reading ur comment while he was saying the exact same words cool
First take I guess
Everyone go on random Tom Scott videos and comment "Thanks for nothing"
The optimal solution for 4 hooks: ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅ (16 loops). Not hard to work out and can be generalised.
The generalised formula is: solution = x₁x₂⁻x₁⁻x₂ such that ⁻xᵤ cancels out xᵤ when concatenated (xᵤ⁻xᵤ = null). That is solved by writing xᵤ in reverse and inverting each letter.
1 hook: A
2 hooks: ABA̅B̅ (straightforward substitution for x₁x₂⁻x₁⁻x₂ where x₁=A, x₂=B)
3 hooks: ABA̅B̅CBAB̅A̅C̅ (x₁ = ABA̅B̅ and x₂ = C. ⁻x₁ must cancel out x₁, so is = BAB̅A̅ which is x₁ written backwards with each letter negated).
4 hooks: ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅ (x₁ = ABA̅B̅ and x₂ = CDC̅D̅. This is the shortest solution another solution is x₁ = ABA̅B̅CBAB̅A̅C̅, x₂ = D)
5 hooks: ABA̅B̅CDC̅D̅EDCD̅C̅E̅BAB̅A̅ECDC̅D̅E̅DCD̅C̅ (x₁ = ABA̅B̅, x₂ = CDC̅D̅EDCD̅C̅E̅. Again this is the shortest solution, another solution is x₁ = ABA̅B̅CDC̅D̅BAB̅A̅DCD̅C̅, x₂ = E)
And so on.
your comment deserves to be pinned (or up there)
Legend
That's an awesome generalisation of their generalisation =D
@@sofakartoffel1392 I honestly don't understand why Matt didn't find the optimal solution, typical Parker solution it's half-baked! Matt's solution for 4 hooks was as I mentioned x₁ = ABA̅B̅CBAB̅A̅C̅ (or the equivalent thereof), x₂ = D but with the generalised solution of x₁x₂⁻x₁⁻x₂ it's easy to see that there's a more optimal substitution to solve the equation using the solution found for 2 hooks as the the substitution. You can use the 5 hook solution to generate a 112 loop solution for 10 hooks, you can also substitute the solutions for 4 hooks and 6 hooks into x₁x₂⁻x₁⁻x₂ to get a 112 loop solution as well and either is optimal.
so the smallest solution in number of loops with 10 hooks would be made of 2 solutions of 5 hooks, meaning 4 lots of 28 loops. This naively looks like the first step in order to optimize for smallest rope length, but I suppose there's probably at least some extra step in how we order the loops themselves, they don't intuitively seem to all use the same amount of rope due to potential distant jumps... the way we position the hooks among themselves probably also makes a difference.
Only when the standupmaths theme started playing I realized which channel I was watching.
Steve's apartment and/or pipe is very distinctive, it's true
Same lol
wie we daar hebben
0:00 Now you got me curious so i went on a spree to see if Steve ever makes contact to those pipes. and HAH I found it! On the video named "Why November is the most dangerous month for trains" at 2:32 he touches the red pipe, so it does exists!
No, it was expected
The power of determination
I checked the video and he does
I needed to know this in my life. Thank you for this.
Why didn't you link the video?
4:17 me when doing a group project but don’t want to do actual work
lol
lol
hahaha
: "I have generalized this problem mathematically "
: *Draws a minion.*
Lol
Can we let the minion work the rest of it out?
Lol, I think Steve's n=1 solution can be counted as Stuart
Amogus
Abstract: a commutator-based approach reduces the cost of the n-hook problem to quadratic, instead of exponential.
Also, numerical investigation rules out non-commutator-based solutions for 3 hooks. This is further evidence against the possibility of non-commutator-based approaches.
In this post, a "sequence" is a sequence of elements of the form "loop around a specific hook, clockwise (or counter-)". Letters (a, b, ...) indicate such elements.
The order of a sequence is the number of hooks in the problem. The length of a sequence is the number of its elements.
The inverse of an element "loop around hook x, with this orientation" is "loop around the same hook x, with opposite orientation".
The inverse of a sequence is the sequence of the inverses of its elements, in inverse order. For example:
"a b c" has inverse
" (inverse c) (inverse b) (inverse a)".
Notice that in this way a sequence cancels out with its inverse.
A commutator, indicated as [a, b], is the sequence "a b (inverse a) (inverse b)". Notice that a commutator's length is 2*(length of a + length of b).
Notice that erasing any element from a commutator makes everything else cancel out. This way it is possible to prove that any sequence constructed entirely of commutators will solve the hanging picture problem.
Further notice:
[[[a, b], c], d] has cost 22, while
[[a, b], [c, d]] has cost 16.
Nesting commutators is costly: a better result is achieved "flattening" the commutators.
This improves enormously over Parker's method. For sequences of order 6:
[[[[[a, b], c], d], e], f] costs 94. In general, for n elements, this costs 2^n + 2^(n-1) - 2.
[ [[a, b], c] , [[d, e], f] ] costs 40.
For 10 elements, as they want to do:
Parker's method costs 1534, while
[ [ [[a, b], c], [d, e] ] , [ [[f, g], h], [i, j] ] ] costs only 112.
Nesting commutators this way is easy of you have a power of 2 amount of hooks. In this case, the cost for n=2^k hooks satisfies:
Cost(k) = 4*Cost(k-1)
This is because if n hooks produce a pattern, 2n hooks produce [pattern, pattern] i.e. the commutator of two distinct copies of the original pattern, with cost 4 times the original cost.
This recurrence relation reduces to:
Cost(k) = 4^k, and since n=2^k, k=log2(n):
Cost = 4^(log2(n)) = n^2.
This applies only for power-of-2 integers, but non-power-of-2 integers are easily bounded above by their next bigger power of 2.
Credits to user mstmar for the idea of nesting commutators.
For three hooks, the 10-long sequence found in the video is of minimal length - I checked all combinations via a script. (I can provide the ugly unoptimized python code upon request).
This leads me to suspect that the commutator-based approach cannot be improved upon, except by rearranging the commutators.
While there are many optimizations to be made, I think doing a search for n=4 is unfeasible without industrial-size compute, and unlikely to yield significant improvement. The size of any pattern of order power-of-2 is directly proportional to the size of the pattern of order 4 that underlies it, but the current order 4 pattern has length 16 and no significant improvement appears likely.
Finally, for the real-life version of the problem that takes into account the real-world distance between hooks, further work may be required.
Thank you for your attention.
🤔
You're basically solving the 2-hook problem many times and nesting the solutions in a binary tree. And I think the strategy is the most efficient if all you've got it the same 2-hook solution. I wonder though if there are other ways. Eg, are there any 3-hook solutions that don't look like [[a,b],c]?
On the other hand, optimizing the commutator based approach is quite easy:
If (N) is the minimal cost for a commutator based approach on N hooks, then (N)=min{2*(k)+2*(N-k)|1=2*(k)+2*(N-k) (since A and B must in total contain at least N letters). On the other hand, for A and B as optimal commutators for k and N-k, we get equality here, hence 2*(k)+2*(N-k) is a minimum for A containing the fixed number of k letters. Finding k such that this term gets minimal thus yields the minimum cost for N.
Using dynamic programming we can find these values efficiently.
Ok, I implemented it and it looks like this:
If the biggest power of two smaller or equal to N is P, then the/an optimal split is P/2, N-(P/2).
e.g. N=10:
[10]=[4,6]=[[2,2],[2,4]]=[[[1,1],[1,1]],[[1,1],[2,2]]]=[[[1,1],[1,1]],[[1,1],[[1,1],[1,1]]]] has cost 112.
written down:
a^{-1}=A
[4]=abABcdCDbaBAdcDC
[6]=efEFghGHijIJhgHGjiJIfeFEijIJghGHjiJIhgHG
[10]=abABcdCDbaBAdcDCefEFghGHijIJhgHGjiJIfeFEijIJghGHjiJIhgHGcdCDabABdcDCbaBAghGHijIJhgHGjiJIefEFijIJghGHjiJIhgHGfeFE
@Neel Shukla Actually, as I read some other comments, I saw that any split in the range (n/2-p/2,n/2+p/2) is optimal, my cut just happened to be the smallest optimal cut.
You just need to arrange hooks from the middle to sides, like 9, 7, 5, 3, 1, 2, 4, 6, 8, 10 to have final string shorter. Just because first hooks are being meet in algorithm more frequently.
Also I think that the most suitable thread for this purpose is one of those used for fishing. They have some cords which flex not much and they designed to reduce friction
Cool
Seems pretty obvious in hind-sight.
Fishing line would be terrible for visual representation.
@@xaytana Glow in the dark fishing line. turn of the lighs and you might see something.
@@NoobLord98 Glow in the dark fishing line? What's the point of that? Definitely not fishing. The point of fishing is that the fish DOESN'T see anything suspicious.
Steve was incredibly whelmed by that gift. It was hilarious. Thanks guys. You're always great together.
He's got the humble tau poster already
@@filipsperl Pretty sure the Tau is just this gift but modded since it has the same signature and note from Matt.
Just whelmed. Not overwhelmed or underwhelmed. Just whelmed.
So, you can just be whelmed in Europe.
Now ask James Grime if he can come up with a 4th different method!
13:49 maybe a 6th method. (gold plated goof did a 5th method (same principle as matt, different generalization))
He did A B A' B' C D C' D' B A B' A' D C D' C' (16 moves compared to Matt and Steve's 22)
Where A' = A inverse
I thought the name James Grime was a play on Steve Mould at first hahahaha
Now we need a guy called Adam Filth or something
@@aceman0000099 😆
Interestingly, there's a lovely acronym that explains exactly Matt's algorithm. DRII: Duplicate, Reflect / Reverse (makes abAB -> BAba), Inverse (makes abAB -> ABab), and Inject (makes abAB + baBA -> abABcbaBAC). DRII can be expanded to the nth integer term, which I think is really interesting.
You don't actually have a face?
No I add it in post every time
*Face disappears*
"It's very convincing"
0:15
Steve: It's good to have you.
Matt: I KNOW!!!
16:49 "So the challenge is for some large number of hooks, what's a really short way of doing it."
Challenge accepted:
My suggestion to extend from n to n+1 hooks would be that:
0) Use solution for n hooks
1) search first least used character x (y is the successor of x in natural order == A < B < C...)
2) Shift every bigger character (in natural order) by 1
3) Replace first letter used least with solution for two hooks x and y
From 2 to 3 hooks:
0) use: A B A̅ B̅
1) x = A, y = B
2) shift => A C A̅ C̅
3) replace A with A B A̅ B̅ and A̅ with B A B̅ A̅
=> A B A̅ B̅ C B A B̅ A̅ C̅
length: 10
cord length: 10
From 3 to 4 hooks:
0) use: A B A̅ B̅ C B A B̅ A̅ C̅
1) x = C, y = D
2) shift => A C A̅ C̅
3) replace C with C D C̅ D̅ and C̅ with D C D̅ C̅
=> A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅
length: 16
cord length: 18
From 4 to 5 hooks:
0) use: A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅
1) x = A, y = B
2) shift => A C A̅ C̅ D E D̅ E̅ C A C̅ A̅ E D E̅ D̅
3) replace A with A B A̅ B̅ and A̅ with B A B̅ A̅
=> A B A̅ B̅ C B A B̅ A̅ C̅ D E D̅ E̅ C A B A̅ B̅ C̅ B A B̅ A̅ E D E̅ D̅
length: 28
cord length: 33
Similar from 5 to 10 hooks (use solution for 5 hooks and insert solution for 2 hooks; imlicit shifting using appropriate letters)
use: A B A̅ B̅ C B A B̅ A̅ C̅ D E D̅ E̅ C A B A̅ B̅ C̅ B A B̅ A̅ E D E̅ D̅
replace E with I J I̅ J̅ and E̅ with J I J̅ I̅
=> A B A̅ B̅ C B A B̅ A̅ C̅ D I J I̅ J̅ D̅ J I J̅ I̅ C A B A̅ B̅ C̅ B A B̅ A̅ I J I̅ J̅ D J I J̅ I̅ D̅
replace D with G H G̅ H̅ and D̅ with H G H̅ G̅
=> A B A̅ B̅ C B A B̅ A̅ C̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ C A B A̅ B̅ C̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅
replace C with E F E̅ F̅ and C̅ with F E F̅ E̅
=> A B A̅ B̅ E F E̅ F̅ B A B̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A B A̅ B̅ F E F̅ E̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅
replace B with C D C̅ D̅ and B̅ with D C D̅ C̅
=> A C D C̅ D̅ A̅ D C D̅ C̅ E F E̅ F̅ C D C̅ D̅ A D C D̅ C̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A C D C̅ D̅ A̅ D C D̅ C̅ F E F̅ E̅ C D C̅ D̅ A D C D̅ C̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅
replace A with A B A̅ B̅ and A̅ with B A B̅ A̅
=> A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ E F E̅ F̅ C D C̅ D̅ A B A̅ B̅ D C D̅ C̅ B A B̅ A̅ F E F̅ E̅ G H G̅ H̅ I J I̅ J̅ H G H̅ G̅ J I J̅ I̅ E F E̅ F̅ A B A̅ B̅ C D C̅ D̅ B A B̅ A̅ D C D̅ C̅ F E F̅ E̅ C D C̅ D̅ A B A̅ B̅ D C D̅ C̅ B A B̅ A̅ I J I̅ J̅ G H G̅ H̅ J I J̅ I̅ H G H̅ G̅
length: 112 (= 28 * 4)
cord length: 154
I hope, there are no flaws...
Edit: just noticed, i posted the length of the rule (in letters) instead that of the cord, so i added the cord length too. Hopefully that's not irritating.
Neat! There are no flaws that I can find. But what is step 2 "Shifting", I didn't understand what do you do in it.
I love it when RUclipsrs I watch reference other RUclipsrs I watch guest starring on a RUclips channel I watch
I found a way to get shorter sequences. I'm sure it's not optimal, but at least better than the one presented. My approach does xyXY where x and y are solutions for smaller problems and capitals are inverses. your approach is a special case of mine where x contains all hooks but one and y is the last hook. my approach checks all combinations of x and y to find the best partition of hooks that gives the lowest length. an example for n = 4 can split its hooks 1/3 or 2/2. The 1/3 case gives your solution to n = 4 and the 2/2 case is abAB cdCD baBA dcDC, length 16 vs 22, so 2/2 split is chosen. I'm pretty sure that having balanced hooks (or 1 off for odd n's) gives the smallest length (for this approach anyways). however, for n=6 you can get a length of 40 in 2 ways (3/3 split or 2/4 split). so for big n's, there might be a better split than even. an other advantage of this approach is that you stay localized the same half of hooks for each 1/4, most likely saving even more rope (in addition to needing less loops), compared to jumping to the end and back every 4 loops.
this approach lowers the n=10 that you wanted to attempt from 1534 loops to 112, a much more manageable feat. oddly, n = 10 also has 2 ways of getting to 112 loops: 5/5 or 4/6.
It also would have saved the 5 people on the stage a little trouble too, as it would only have taken 28 loops instead of the 46. Could have even added a 6th person with a similar tangle (40 loops).
After studying it for some time, I can prove by induction that taking balanced splits (1 off for odd n) is always best. It is also relatively easy to show by induction that if we call f(n) the number of steps needed (with this method) is always at least n^2, with equality if and only if n is a power of 2. What is much more surprising is that we can always spread a split until we reach a power of 2, for example f(12) = 2(f(6) + f(6)) = 2(f(5) + f(7)) = 2(f(4) + f(8))
This explains why we often have several solutions, especially for large n (but remember, we can't be better than an even split). Still, as it only grows as n^2, this is much more efficient than their solution, which grows as 2^n. You can easily show f(n) < 4n^2 (take the smallest k such that 2^k ≥ n, and check that f is strictly growing, then we have f(n) < f(2^k) = (2^k)^2 < (2n)^2 = 4n^2), and with some work f(n) < 5/2n^2 (first prove that f(3*2^k) = 10/9(3*2^k)^2, then use the same argument as before). It even seems like f(n) < 1.3n^2, which would be really close to n^2.
This reasoned approach is much better than my first thought: brute force.
With a solution length that is at most approximately 2^n we get a search space of only about a 1000 long for n=10, so that should be feasible, right?
Nope. That ignores the fact that with a pure brute force method (n hooks and k loops for your shortest solution) you actually have a search space of (2n)^k (both directions for each hook, repeat pick k times). For n=10, k=112, and t_check=50ms, a pure brute force would finish after about 8e135 years, which is well after we expect supermassive black holes to have evaporated into Hawking radiation (1e100 years).
Turns out a pencil can still beat a CPU.
Following this thread
This is also the solution given in this paper: arxiv.org/pdf/1203.3602.pdf
@@swerasnym That paper gives the algorithm but does not establish optimality, it only conjectures it. This paper also establishes its optimality and counts the number of different minimal-length solutions: eudml.org/doc/282667 . The provenly optimal lengths of solutions for n nails are also given by the OEIS sequence A073121. Namely, for n = 2^m + k with k < 2^m the optimal solution length is 2^m*(2^m + 3k) which grows asymptotically quadratically in n, as O(n^2). For n = 10 this gives that a solution of length 112 is indeed optimal.
Intriguingly, all of this applies only to the case when the string is only allowed to loop aroud the nails, but not around itself (giving a "simple Brunnian link" for solutions of the puzzle, in the parlance of the paper). If loops of the string around itself are allowed (i.e. "knotting"/linking the string with itself) then only a linear number (O(n)) of crossings of the string are required (see Fig. 8 in your cited arXiv paper), not the quadratic number (O(n^2)) if these aren't allowed. Your cited arXiv paper gives 8*n as a candidate solution in this case but does not claim it is optimal. I don't know if it is an open question or not as to what the lowest number of string crossings required is, but it does seem interesting to consider. :)
I'll dare to post a non-mathematical comment: Is this really the largest table in Steve's house?
There's a nice topological way to view this. You're looking at the fundamental group of the plane with n-many holes and discussing what elements of the group, when projected onto the plane with (n-1)-many holes, return the trivial element of the group.
To be more precise, the fundamental group of the plane (or, homotopically equivalent, the n-petal graph), is the free group generated by n-many variables. Consider then the projection map, say, called P_i, from F(x_1, x_2, ..., x_n) to F(x_1, x_2, ..., x_(i-1), x_(i+1), ..., x_n). This is a group homomorphism, and its kernel is the subgroup generated by g^m * x_i^n * g^(-m), for g in F(x_1, x_2, ..., x_(i-1), x_(i+1), ..., x_n). The problem you're asking about in the video, or just the general problem, is finding elements of the intersection of the kernels of all the project maps P_i.
I gave this a shot and came up with the same answer found in the video, i.e. a middle element serving as a barrier between a string of mirrored inverses on each side.
I've got a solution to the scaling problem which leads to fewer symbols (e.g., less rope) for longer sequences. Conceptually, rather than focusing on adding new pegs at the end, I imagine that the pegs we already have are getting duplicated: so the rope that used to go around one peg is now going around two pegs together. The question then becomes how to ensure that the picture falls if either of those two pegs is removed. We can consider going from the trivial one-peg case to the two-peg case to be exactly this problem, and so can adapt the two-peg solution. To be specific, any time we have a clockwise turn which we want to turn into turns around two pegs, we replace it with AbaB (where A is the first peg, B is the second, and capital letters mean clockwise turns while lower-case mean counterclockwise). Likewise, we replace any counterclockwise turns with bABa. This will quadruple the total number of symbols, but in the long run, quadrupling the number of symbols whenever we double the number of pegs is better than (more than) doubling the number of symbols when we add a single peg.
To give an example of how effective this is, here's my four-peg solution, as before with capital letters being clockwise turns and lower-case being counterclockwise:
AbaBcDCdbABaDcdC
If you remove any of the pegs (e.g., remove any of Aa, Bb, Cc, or Dd from that sequence), the rest will collapse. This 16-symbol sequence is shorter than the 22-symbol sequence presented in the video, already demonstrating the effectiveness of this approach. The savings would be even more evident if going to higher numbers of pegs.
I just love the fact that these two are such great friends and can geek out together about some maths problem and enjoy every minute of it. 😊
Funny, that solution looks a lot like commutators in rubik's cube
The notation for them is [A; B] and that means ABA'B'
So the solutions with 3 hooks can be noted [[A; B] ; C]
I wonder how you could add conjugates, another tool in rubik's cube ([A: B] = ABA') in the picture frame story...
That's because they are commutators! I'm not sure how to add conjugates to the story either.
I wanna look at [[[A;B];C];D] vs [[A;B];[C;D]].
[[[A;B];C];D] = ABA'B'CBAB'A'C'DCABA'B'C'BAB'A'
[[A;B];[C;D]] = ABA'B'CDC'D'BAB'A'DCD'C'
hmmmmmm... dat one's shorter...
There is another video that explains that this is exactly the case. ruclips.net/video/n-v6pmZzxL0/видео.html
@@JNCressey We want a nested commutator involving every variable (i.e., every hook) and that is as "shallow" as possible (to minimize the expanded length). That's how [[[A;B];[C;D]];[[[E;F];[G;H]];[I;J]]] gives us a solution with only 112 loops for 10 hooks
fellow cubers
8:35 In Parker notation, Steve is actually putting a C at the beginning, not the end here because he grabbed the other string.
It's not meant to be exact, it's a Parker notation
fake fan... that’s actually an anti-C... smh
Now Humble Tau in Steve's light video makes sense
It's humble pi btw 😂😂😂
@@VaradMahashabde if you check Steve Mould's newest video about levitating water, the picture is featured in the background. At 6:37, he edited it to say "Humble Tau" for a bit, being a refference to a Numberphile video where Matt and Steve debated for which is better. (Steve stating Tau is better abd Matt stating it depends on 2Pi or half Tau)
"great to have you." "I know!"
0:14
Now, I occasionally make a habit of constructing a fractal called a dragon curve. It's made with a series of clockwise and anticlockwise 90 degree turns. Each increasing step adds a clockwise turn, then mirrors every previous step in reversing order, inversed the same way as done in this video when demonstrating the addition of D. That's fascinating to me.
Everyone talking about commutators, yet here you are bringing in fractals to the show.
I love it.
One can get smaller solutions by using different groupings. Instead of going from
1) A*B*C to (A*B*C)*D
treat (A*B) and (C*D) as one hook and calculate the solution
2) (A*B)*(C*D).
The number of steps for approach 1) is
a(n)=3*2^(n-1)-2 (n is the number of hooks).
This follows from the recurrence
a(n+1)=2*a(n)+2, a(1)=1
For the second approach one gets the recursion
b(2m)=4*b(m)
b(2m+1)=2*b(2m)+2=8b(m)+2
yielding
b(2^m) = 2^(2m) = 4^m (this is actually only quadratic in the number of hooks).
Finding a solution for three hooks that is shorter than 10 steps would make the bound for an uneven number of hooks even better.
The red pipe is going to keep me in suspense for a long time
Same
When the pipe vanishes at the beginning, you can see a little bit of the pipe that he wasn't able to crop out
@@KartheekTammana123 Ah, there he got you: he wasn't able to crop out a piece of pipe that he added in before. The pipe still isn't there.
@@Jkirek_ Touché
What about the framed Humble Tau by Patt Marker?
When you step up to 3 all you are doing is treating the A and B hooks as 1 hook and treat it like 2 hooks again: AB and C
Is this true?
omegadan Should be, and the „reading it in reverse and negativ“ is simply the result of winding counterclockwise around a combined hook.
That's interesting. So is the solution for ABC·D the same as AB·CD?
In other words, if you make a four-hook solution by combining a three-hook solution with an extra hook, do you get the same as combining two two-hook solutions together?
That's my thought as well, by grouping like that, you should be able to get any number of hooks by treating A•B•C•D as A•B hook and C•D hook .
@@PhilBoswell YES! THAT WORKS!!
The AB•BC solution only has 16 rather than Matt's 22
You both are brilliant, thanks for showing all the details of your thought process. learned how to think in terms of maths
The fricking clockwise and anti-clockwise cards blew my MIND!
I'm surprised that you guys didn't point out the nice expandable.. almost fractal-like pattern that you're doing; You're even wearing a recursive T-Shirt!
( AB A'B' ) Just becomes the new A, and B is the next pin, and you can expand that out forever. It's the same for ( AB' A'B )
L system!
@@georgesmith4768 I'll be honest, I didn't know there was a name for that. Thank you!
Watching a new Standupmaths video just makes my day every time!
It's not worse than doubling, because as the number of hooks goes to oo, it _basically_ becomes doubling. So it's still O(2^n).
Big O Notation
Asymptotically it may be no worse than doubling. Here we are talking about no more than 10 hooks
I have no idea what you are saying and I believe everything you said
It's doubling and adding 2
because you guys seemed to be coming across stuff in real time, this watches almost like a visual podcast - was a really cool video style! hope to see more similar stuff in the future, keep it up guys!
I love that these two and Tom Scott are all aware of each other. That would be the most epic collab ever, right?
I really love this kind of thing where it's a real solution, multiple methods, all the same results.
In algebra and all the maths up from there, I have always struggled with that kind of thing, (i know rearranging a problem doesn't fundamentally change it, but messy hand writing and a tendency to misread characters really interferes with that) so seeing the same solution, solved with three different trains of thought is just awesome.
It's why I really like Those videos where Pi is hiding everywhere, and why it would be. Great content!
Just hit the part of the video with the N dimensional cubes and I am losing it.
I deeply hope that Steve's follow up video features your lovely framed picture. But with Pi scribbled out and replaced with Tau.
He already did that in the background if his most recent video.
@15:15, you suggest the shortest path through all vertices also generates a solution. If you label that path as A B' A' C A B A' C', then you'll notice that if the A's are removed, the resulting loop B' C B C' does not degenerate.
That's because the path you've traced out, when projected onto 2 of the planes, degenerates. But when projected onto the third plane (BC), the path is a loop around a circle.
"Shout out to Tom Scott for doing nothing."
when you ask a man of physics and a man of mathematics to solve a question...you find different answers...then things comlicate when you add a compurer programmer to the mix...SCOTT SOLVE THIS QUESTION!(by scott i mean tom scott)
Tom solves the question using linguistics.
The ending bit reminded me a LOT of a solitaire card game called "Accordion", where similar sandwich/removal occurs. I'm wondering if some of the thought process of playing that game would come into play here.
The frame we spotted in last video haha!
?
WARNING: long comment ahead, but I believe there is an efficient algorithm for *doubling* the number of hooks at each step, rather than adding 1 at a time. I've tried to explain it as coherently as possible over text, and I'd greatly appreciate anyone who could verify this method or point out any mistakes.
*ALGORITHM EXPLANATION*
Steps of the algorithm:
Step 1: Start with the 2 hook solution: A B A' B', where A stands for a clockwise string turn around hook A, and A' is anticlockwise (counterclockwise for us 'muricans)
Step 2: Consider an entirely separate 2 hook solution, with hooks C and D. of course, the solution is still the same: C D C' D'
Step 3: Consider both separate two hook systems as two individual hooks, let's call them X and Y.
Step 4: Naturally, the solution for the XY system is: X Y X' Y'
Step 5: Substitute our original hooks, ABCD, into the new solution. BUT WAIT: we know X and Y, but what does X' and Y' look like?
that's simple: X' is just everything in X, but in reverse order. So if X = A B A' B', then X' = B' A' B A.
this ensures that X and X' will fully cancel each other out when they "collide"
Final result: X Y X' Y' becomes: A B A' B' C D C' D' B' A' B A D' C' D C
You can test out yourself: remove any one of the hooks, and the others will collapse and cancel each other out.
*COMPARING THIS ALGORITHM WITH MATT AND STEVE'S ALGORITHM*
Now, the interesting thing to note is how many "turns" of string we have: the final solution ends up with ONLY 16 turns, whereas Matt and Steve's algorithm resulted in 22 turns for 4 hooks. The equations for # of turns vs. number of hooks for each algorithm are as follows:
Matt/Steve algorithm:
t(n) = 2 * t(n-1) + 2 (where: n > 1) (in layman's terms: adding 1 hook causes the number of turns to double, plus 2)
My doubling algorithm:
t(n) = 4 * t(n/2) (where n >= 4, and MUST be a power of 2) (in layman's terms: doubling the number of hooks quadruples the number of turns)
*TACKLING THE CHALLENGE OF 10 HOOKS*
Of course, you can use this algorithm to continue doubling the number of hooks as much as you want. For example:
if you want 8 hooks, simply take the solution for 4 hooks above (X Y X' Y') and name it as a single hook, lets say W. Then, let's also define V, which is another system of 4 hooks. Then, a system of 8 hooks has the solution W V W' V', with a total of 16 * 4 = 64 turns.
Regarding Matt and Steve's challenge of 10 hooks:
Using my algorithm, you can solve an 8 hook system with 64 turns of string, but unfortunately, the efficient doubling method can't add the last 2 hooks. For those, we need to use the algorithm in the video. So, using the formula t(n) = 2 * t(n-1) + 2, we can see that:
t(9) = 2 * t(8) + 2 = 2 * 64 + 2 = 130
t(10) = 2 * t(9) + 2 = 2 * 130 + 2 = 262
So I predict that a 10 hook system can be solved with at least 262 turns of string, but there may be a more efficient way to add those last 2 hooks to the system. I'll leave that to someone smarter to figure out ;)
After some thinking, I realized this can be generalized to not just doubling the # of hooks, but adding any amount of hooks (m) to an existing system of n hooks.
Let X = existing system of n hooks, represented as a single hook.
Let Y = new system of m hooks being added, represented as a single hook.
Solution for X + Y is X Y X' Y'
The new number of "turns" of string needed for this solution is:
t(n+m) = 2 * t(n) + 2 * t(m) *(Generalized solution)*
We can show that both Matt and Steve's algorithm, and my algorithm above, are special cases of this general solution:
Matt and Steve's algorithm is where m = 1, so:
t(n+m) = 2 * t(n) + 2 * t(m) = 2 * t(n) + 2 * t(1) = 2 * t(n) + 2 (since we know that the solution for n = 1 is trivial: just 1 turn of string)
The doubling algorithm:
t(n+m) = 2 * t(n) + 2 * t(m) = 2 * t(n) + 2 * t(n) = 4 * t(n) (since m = n)
Given this, we can compute the minimum (theoretically) # of turns for 10 hooks:
t(10) = 2 * t(8) + 2 * t(2) = 2 * 64 + 2 * 4 = 128 + 8 = *136*
So we should expect 10 hooks to be solved with at least 136 turns of string
Small mistake in step 5. X' isn't just X reversed, but also each term inverted. So if X = A B A' B', then X' = B A B' A' so that in XX' you get B'B, A'A... which cancel and not B'B', A'A'... which don't.
Also as an addition to what Zaheen Ahmed said, t(10) can also be split other ways than 8/2. if we split it 5/5, we get
t(10) = 4*t(5) = 4*(2*t(3)+2*t(2)) = 8*(10+4) = 112.
Even more savings!
@@zaheenahmed304 I was thinking about the same strategy, and wrote the sequences down. You are right.
This is the 4 hook sequence (length 16), broken up in its four components:
ABA'B' CDC'D' BAB'A' DCD'C'.
And this is the 8 hook sequence (length 64), split up in fours as well:
ABA'B'CDC'D'BAB'A'DCD'C' EFE'F'GHG'H'FEF'E'HGH'G'
CDC'D'ABA'B'DCD'C'BAB'A'
GHG'H'EFE'F'HGH'G'FEF'E'.
We can use this to create the 10 hook sequence (length 136):
ABA'B'CDC'D'BAB'A'DCD'C'EFE'F'GHG'H'FEF'E'HGH'G'CDC'D'ABA'B'DCD'C'BAB'A'GHG'H'EFE'F'HGH'G'FEF'E' KLK'L' EFE'F'GHG'H'FEF'E'HGH'G'ABA'B'CDC'D'BAB'A'DCD'C'GHG'H'EFE'F'HGH'G'FEF'E'CDC'D'ABA'B'DCD'C'BAB'A' LKL'K'
You can clearly see the structure. First comes the 8-hook sequence, followed the 2-hook sequence, followed by the reverse 8-hook sequence, and the reverse 2-hook sequence seals the deal.
@@mstmar Thanks for catching that!
@@verfmeer Yep, that should be the sequence. I salute you for actually writing it out, I didn't have the patience for it haha
(Now, we patiently await Matt and Steve attempting to do this with actual hooks and string...)
i love the way you guys understand each other yet have completely different approaches.
honestly seeing Matt’s method and being able to compare it with what Steve and Jade have done, I’m quite amazed by how a flexible thing this naughty knotty problems actually are. I mean steve’s method is something I would never think off knowing myself but what Matt has done is like a „method to madness” kind of approach. God i love how with those carts you completely forgot about the physical situation by just knowing those two clowiseness-hook axioms
God i just had to write this down somehow cause it is kind of a illumination type a moment for me
You Don't need to double each time, for four you can go aba/b/cdc/d/bab/a/dcd/c/
You put in the new letter as a commutator with a previous letter.
for replace a clockwise it goes in the form aba/b/ where a is the old letter and b is the new letter, and when replacing anticlockwise you go bab/a/.
So starting from 1 hook
1 hook solution: a
2 hook solution: aba/b/
3 hook solution: aca/c/bcac/a/b/
4 hook solution: aca/c/bdb/d/cac/a/dbd/b/
5 hook solution: aea/e/ceae/a/c/bdb/d/caea/e/c/eae/a/dbd/b/
however when moving from 2 hooks to three hooks it is more efficient to use your doubling method since adding the commutator adds more than double the letters.
this changes the solutions to
1 hook: a
2 hook: aba/b/
3 hook: aba/b/cbab/a/c/
4 hook: aba/b/cdc/d/bab/a/dcd/c/
5 hook: aea/e/beae/a/b/cdc/d/baea/e/b/eae/a/dcd/c/
doubling each odd number of hooks is also less efficient due to the fact that when using this commutator extension method you add three per letter you are commutating with whereas with the doubling method you multiply the terms by 2 and add 2.
I love when the time lapses start cause I get to listen to a great song everytime
There's a solution that's precisely doubling (marking clockwise rotation with a,b,c,d and counterclockwise with A,B,C,D):
for two pins A and B we have the same solution as before: abAB, but now let's assign this combination of steps the letter x and give the letter X its inverse: baBA. The letter y will be the equivalent thing for pins C and D - cdCD, and for Y we have dcDC
so if we combine X and Y in the same way (xyXY) and expand we now have: abABcdCDbaBAdcDC, which is 6 steps shorter than the solution you presented in the video for 4 pins.
I found simpler solutions than what your method gives for a bigger number of hooks (>3).
You just have to encapsulate a group of hook into a single abstract hook with an algorithm that represent the clockwise an anti-clockwise turn. If one of the hook in the group is removed, the whole abstract hook is removed. And if a clockwise turn is followed by an anti-clockwise turn (or vice versa), everything is undone just like how a real hook would behave.
Here an example with 4 hooks :
- Your method in 22 steps : ABabCBAbacD CABabcBAbad
- This method in 16 steps : ABab CDcd BAba DCdc
I grouped the hooks A and B (respectively C and D) into an abstract hook with the abstract clockwise turn ABab (respectively CDcd).
Here's the best results I get with the 10 first hooks :
Note: the x operator means I combine two previous solutions and the +1 operator means I use your method to use the previous solution
Hooks: Steps -> Combinations of Hooks
1: 1
2: 4
3: 10
4: 16 = 4*4 -> 2x2
5: 34 = 2*16+2 -> 2x2+1
6: 40 = 4*10 -> 2x3
7: 82 = 2*40+2 -> 2x3+1
8: 64 = 16*4 -> 2x4
9: 100 = 10*10 -> 3x3
10: 136 = 4*34 -> 2x5
We might add this sequence to the OEIS eventually ...
You can do 5 in 28, and therefore 10 in 112: ABab CDcdEDCdce BAba ECDcdeDCdc
Check out sequence A073121 in OEIS
And you can do 9 in 88 because 4+5=9 and 2(16+28)=88
@@DS-xh9fd Yeah, it"s a solved problem A073121, A254575
I pictured a number of long parallel rods fairly close together and imagined each pass of the rope getting placed down a little farther along the rods. For a large number of rods-needing a very large number of passes-the rope would end up covering a significant area. It would look a bit like woven cloth, particularly if the rope was thread or yarn. Then it struck me, what if the rods were also thread or yarn? You would actually have a cloth that would completely fall apart (friction ignored) if one of those warp threads was cut. Unraveling cartoon sweater, eat your heart out.
Now we have a new pattern for completing multiple-choice tests!
5:40 it looks like connecting all of them same way AND adding anchorage. And that is propably how to run it.
a way to stop it from doubling each node is in self-undooing knots, but combining correct one with rest of the algorithm is not easy.
11:54 could someone please make a GIF out of this?!
Sorry about green dots (have no idea what's up with that) and late response.
You can make them shorter by substituting your last expression into both a and b, not just one of them (i.e. doubling the amount of nails each time). This way you get around n^2 turns for n nails, not 2^n+2^(n-1)-2 like you get.
7:40 "How to draw angry robots with Matt and Steve"
Or how to draw bikini tops
I was thinking of Dr. Zoidberg
I thought it looked like squidward with glasses
Couldn't you say that the only solution is the one for two hooks? If you have any more hooks you would group them together until you have only two. Your method seems to group all the hooks except the last one together so for three hooks it would be (AB),C,(AB)',C' and for four hooks it would be (ABC),D,(ABC)',D'.
Here's a question: is there a way to do this so the weight of an object hung from the string is as evenly distributed as possible across the N points? My thinking is that this could have some sort of practical application where something is being suspended evenly and could be quick released. In the examples, the Nth point would have a significantly less amount of string around it than the earlier points.
Maybe the points could even be extended into a second dimension to suspend 3-dimensional objects (or just orthogonal 2-dimensional objects).That bit would be wholly impractical but it's fun to ponder.
"good to have you" ,"i know" loool
What does loool stand for?
@@theunpopularcuber9554 laughing out oridinary loud
You could group them, correct? If you need 10 hooks, simplify to 5 groups of 2, because it's effectively the same. Treat each group as a single hook, since removing one part of the group would remove the group as a whole. Since you've shown it possible to be done with 3 as well, you should be able to do any number, I would think.
Wow, cool, I think you are right!
But although this makes the number of logical steps smaller, the actual dependencies of which hooks the string pass over do not get simpler.
So you'd only have to prove prime numbers!
Well yes, but since there is an algorithm, it should be possible for any number anyways, shouldn't it?
@@youtubeuniversity3638 Not really, that would only be true if we had to divide them evenly.
Take 7 for example, it can be done by making three groups, with 3, 2 and 2.
@@JBergmansson Good point! Guess I looked too hard at the example given!
You can save a bit of string by going with a divide-and-conquer method: So instead of taking a solution s for n hooks and a solution t for 1 hook and combining them as stST (where capitalization denotes reversing the order and the direction around each hook) to get a solution for n + 1 hooks, you can take two solutions s and t for half the hooks and combine them as stST. For example, instead of abABcbaBACdcabABCbaBAD (of length 22) you get abABcdCDbaBAdcDC (of length 16) for four hooks.
As you were laying out the cards I was also thinking of the Towers of Hanoi. 🤣
God, I love Matt's theme song. One of my absolute favorites and it lives in my brain permanently. I would say "rent-free", but it's probably a drag on my productivity to be humming it so often.
Yo dawg, I heard you like commutators!
What ever happened to GoldPlatedGoof?
No idea, the latest thing I can see is a tweet from October 2018 :-(
0:40 if I had to guess it’s a equation related to leveling the frame that approaches infinity but never actually reaches it.
When I watched Jane's original I tried to correlate it to graph theory and got close to your cube solution using the chinese mailman problem, you guys should look into it for a possible smaller solution.
+standupmaths You could get a shorter card sequence (16 vs 22 cards) if you:
1) Split the original sequence just before the C card
2) Add D and D̅ respectively to the ends of the second partial card sequence
3) Take the reverse conjugate of the CD end pairs
4) Add those end pairs respectively to the ends of the first partial card sequence
Thus, the new sequence would be: C̅DAB̅A̅BD̅CDC̅B̅ABA̅CD̅
16:08 My brother walked in with a gerbil and asks
"why are you watching a video on how to hang a picture, why is it 18 minutes long and why are you 16 minutes in?"
What am I supposed to say?
Let him know that it relates to hanging the picture in space, and that the Gerbil Space Program is conditioning the gerbils to understand that hooks and loops will allow zero-G environments to sustain a hanging picture, on as many or as few hooks as needed, provided it is not hung with any of the methods mentioned in the video. Also, explain that 18 minutes is roughly the total attention span in minutes of a gerbil, and that you are 16 minutes in, but only by appearances, because it was paused a few times and you would have been done by now if you didn't have to explain the previous information.
Maths at its finest! When there's multiple different methods of approaching a problem, using diverse areas of mathematics, and they all provide equally valid solutions! Love it!
It's the magicians knot yall.
Gotta admit, that looks like a superpermutation with how horrific the sequence is. That being said, the superpermutation for n is still much, much more horrifying...
Man you’re really paying that steve mould premium
Engineer: How can I design this system without a single point of failure...
Mathematician: That's too easy, theoretically speaking, How about designing a system with only single points of catastrophically failure?
isn't that book Humble Tau? was on Steve's recent video
Go away Tauist! No one wants you here!
@@hammerth1421 it's a joke? Steve had it in his video and made it say Humble Tau for a second or two
@@fanq_ Their comment was also a joke
☯
@@krissp8712 Oh come on, we don't need a Humble Tao here
Expanding on Matt Parker pointing out that the solutions to the puzzle can be represented as a path through vertices on the cube, we can generalize to N dimensions by considering an n-dimensional cube with volume of 1 and a corner fixed at the origin and the axes defined by all the edges at that vertex.
We have now the following observations:
a) Any solution must pass through all the vertices that are distance 1 from the origin.
b) No solutions can contain path segments that backtrack (ie, in the 3-dimensional case, (0,0,1) -> (0,1,1) -> (0,0,1) and the like would be backtracking).
c) The distance between each vertex in the path must be 1.
Axiom a) ensures all hooks are utilised, axiom b) removes isomorphic solutions, and axiom c) comes from the clockwise/anticlockwise turns around a hook translating to positive/negative direction of travel along the axis defined by the coordinate of the hook.
The minimal solutions (shortest amount of string), are paths such that the magnitude of the vector from the origin is minimized at each step.*
There is an algorithm to do compute this efficiently (O(n) in both space and time), but the youtube comments section are not large enough to contain it.
Still the only channel I'll turn notifications on for.
The cube is not equivelant. A,-B,-A,C,A,B,-A,-C goes through all vertices on a cube but does not follow the hanging of the painting pattern since the removal of A does not drop the painting
Here is a paper formalizing this kind of things: erikdemaine.org/papers/PictureHanging_TOCS/paper.pdf
I've had good use for it in a programming contest once. :)
Erik Demaine is awesome, I watched his MIT Origami class and was blown away.
Their solution iteratively builds up from 2 hooks adding one each time. multiplying the number of hooks by 2 each time gives a significantly smaller number of turns 2^n vs n^2.
Their solution treats the previously solved hook as a single hook. They than add the simple clockwise and counter-clockwise for the second hook.
> first second first* second*
> aba*b* c bab*a* c*
However you could consider a previously solved hook to both be the first and second hook which would double the number of hooks solved and only multiply the number of turns by 4.
> first second first* second*
> aba*b* cdc*d* bab*a* dcd*c*
The recurrence relation for their solution is t(n) = 2*t(n-1)+2 > 2^n where n is the number of hooks and t(n) is the number of turns. Some terms in that sequence starting from n = 2 are 4,10,22,46,94,190,382,...
My solution is t(n) = 4*t(n/2) = n^2.
For n = 8, their solution takes 382 turns while mine takes 64. At n = 16 mine still takes less at 256 turns.
Nice! Good to know I'm not talking complete gibberish, I explained the exact same idea in my comment: ruclips.net/video/x5h3yTxeCew/видео.html&lc=Ugzaw6rERFQ1Qr4sxCt4AaABAg
(insert something about great minds think alike, etc etc)
@@zaheenahmed304 I looked it up. This is also the solution found by Erik D. Demaine (arxiv.org/abs/1203.3602)
Matt saying "Maths!" with his hands in the air after noting that three people came up with the same solution different ways made me laugh so hard. 11:49 - 11:55
It has been N months. I can't find the follow-up video mentioned at ~ 17:17 on Steve's channel. Was it ever made?
Sadly not possible to find it. :-(
Am I the only one that thinks Matt’s solution looks an awful lot like a commutator?
I wonder what the solutions look like if the frame should fall when exactly any k out of n hooks are removed.
The k=n case is what 'normal' people are aiming for and is just clockwise around all hooks;
The k=n-1 case is trivial: clockwise around all hooks then counterclockwise around all hooks;
And the k=1 case has the easy solution you showed and at least a nice shorter solution.
But are the solutions for other 1 < k < n-1 easily generated?
ABABCBABAC is like a Parker Thue-Morse sequence.
@@iykury So it's even worse then. It's like a Parker Parker Thue-Morse sequence. A Parker squared Thue-Morse sequence.
You mean the Thue-Morse-Morse-Thue sequence.
Looking for this followup video after N months where N = 39
Hi everyone! I hope you all are having a wonderful and blessed day. 🖤
To add yet another way of thinking about this problem, consider the free group on 3 generators, , and the natural homomorphisms to the groups generated by , , and which correspond with "pulling out" the a, b or c "hooks" respectively. The problem is then to find a non-trivial element which is in the kernel of all three homomorphisms. The element a b a^-1 b^-1 c b a b^-1 a^-1 c^-1 is in all three kernels.
How to do this from an engineer's perspective: make the strings weak enough to fail under any stress such as removing a hook.
Or make the hooks weak enough that all N are needed to support the load, so that removing one causes a cascading failure of the other N-1 hooks.
When he pulled the Ds out of his pocket that got me laughing
Haha funny, I saw Tom Scotts Video of this topic 👌🏼
Looking at the cube traversing problem, a more efficient induction from n to n+1 dimensions is: 1) remove final step (so no longer go back to start) 2) add a move in new dimension 3) perform old algorithm in reverse removing final step (ie the thing from 1) but backwards), 4) undo move in new dimension. Applying this to your algorithms for 2 pegs seems to give a successful algorithm for 3 pegs. I imagine that commutator theory would be really helpful in these kind of problems.
I like how Steve Mold does all sorts of collabs. Not to mention his solo videos are peng.
I've seen the puzzle a bunch of times so I wasn't that excited, but when Matt then showed it was analogous to pathing around n-cubes it suddenly became extremely exciting.
Should be able to make an arbitrarily large number of hooks solution, right? I.E. 3 hooks = AB'A'BCAB'ABA'C'.
LET X = AB'A'B and X' = B'ABA'.
We then substitute to: XCX'C' which is in the form of the 2 hook solution Using the symbols to make a 3 hook solution: XC'X'CDC'XCX'D'.
Substituting the Xs back should give a 4 hook solution: AB'A'BC'B'ABA'CDC'AB'A'BCB'ABA'D'. I think this could be done in a script fairly efficiently, in case you want to make one that's 200 long or whatever.
itchykami yes, this is the algorithm (more or less) that they presented in this video. Their question is if there are solutions that produce shorter patterns than this algorithm does.
It can be done really efficiently in the sense that writing a program that runs in time linear to the size of the solution is fairly easy.
It cannot be done really efficiently in the sense that the final solution is exponential on the amount of hooks.
Maybe a different family with a linear or quadratic (or, generally, polynomial) amount of turns exists, but we don't know it. Now THAT would be a lot more efficient.
By the way, generating the solution for 200 hooks using this family of solutions would give something like 2^201 = 2*2^200 = 2*(2^20)^10 turns, which is about 2*(10^6)^10 or 2*10^60.
Assuming you can process a billion (10^9) turns per second (reasonable estimate for a modern x64 CPU), and that your algorithms instantly finds the sequence and all it has to do is put it in memory, finding the solution for 200 hooks takes at least 2*10^60/10^9 s = 2*10^51s =~ 10^46 years (very rough approximation on this last step, i did all calculations in my head)
11:00 that card presentation is actually very clever. About 5 minutes earlier I was about to write that Mould method makes way more sense for me.
Only in Matths can you talk about the same thing as if its 2 different things and convince all other Matthsers to go along with you~
Tbh: This video perfectly describes why I love maths. You can do as many different creative ways for solving something as you want, as long as you do them properly you'll get the right solution.
Well i think i have a great solution that works for any number of hooks but it requires one extra item sadly, a pair of scissors, now you might call that cheating but i tend to think its just a creative way of solving the problem :P
How will pulling a hook make the picture fall down just because you have a pair of scissors lying around?
My approach (having sat and thought about it for a little bit and having put in not a lot of effort) you only need to cancel out passes over the hooks as passes under the hooks would simply fall to the ground regardless, so if you pair off hooks into groups of 2 (when working with an odd number do a group of 3 as shown in the video for as few iterations as possible) as if you start each pair with a pass over the first hook them you are simply doing the same 2 hook or 3 hook problem again