🔗 Jiu Lian Huan 九连环

How many steps needed to solve Jiu Lian Huan?

Let me represent a ring when locked as 1 and when unlocked as 0. Starting out all 9 rings are locked as "111 111 111", the goal is to get them all unlocked as "000 000 000". The spaces between every 3 binary levels are just for readability. 

Starting out: 111 111 111

1. 111 111 110
   
   

2. 111 111 010

3. 111 111 011

4. 111 111 001

5. 111 111 000
   
   

6. 111 101 000

7. 111 101 001

8. 111 101 011

9. 111 101 010

10. 111 101 110

11. 111 101 111

12. 111 101 101

13. 111 101 100

14. 111 100 100

15. 111 100 101

16. 111 100 111

17. 111 100 110

18. 111 100 010

19. 111 100 011

20. 111 100 001

21. 111 100 000

• To get 1 ring out, need 1 step.

• To get 3 rings out, need 1 + 4 = 5 steps.

• To get 5 rings out, need 1 + 4 + 16 = 21 steps.

Notice the pattern?

• 4^0 = 1

• 4^1 = 4

• 4^2 = 16

• 4^3 = 64

• 4^4 = 256

So, to get 7 rings out, need 1 + 4 + 16 + 64 = 85 steps. To get all 9 rings out, need 1 + 4 + 16 + 64 + 256 = 341 steps! What an exponential increase in its number of steps for every 2 more rings.

How many steps needed to solve n Lian Huan with n odd number of rings?

n = 1, 3, 5, 7, 9, 11, 13, 15...

Sum of steps for n rings = 1 + 4 + 16 + 64 + 256 + ... can be written as a geometric series:

• First term 'a' = 1

• Common ratio r = 4

But, we still need a linear function to map n rings to the number of terms in the geometric series. For instance:

• 1 ring -> 1 term

• 3 rings -> 2 terms

• 5 rings -> 3 terms

• 7 rings -> 4 terms

• n rings -> k terms

• n rings -> (n+1) / 2 terms

So, k = (n+1) / 2

Using formula of geometric progression, steps needed for n odd rings, or sum of terms up to k term:
a * (r^k - 1) / (r - 1)
1 * (4^k - 1) / (4 - 1)
(4^k - 1) / 3
(4^((n+1) / 2) - 1) / 3

Using this formula, theoretical steps needed for 11 rings = (4^((11+1) / 2) - 1) / 3 = 1365. We can see it quickly become unrealistically unmanageable playing it by hands given this ridiculous amount of steps.