Rings

Return

I was on my Youtube recommended and this video by Wrath of Math came up, explaining a maths puzzle and the process of its solution.
The solution that I found to the puzzle involves one of my favourite functions. And so I wanted to share a functional problem and how it involves the Lambert W function

Before I start the video, I recommend that you watch the Wrath of Math video. And I personally challenge you to pause it and try to solve the puzzle before moving on to the explanation. This video aims to be an extension of that video in which I show my solution to the puzzle and how to extend upon its ideas.

However for the people who are (in a coma), I will present the basic idea of the puzzle.
We are given rings that are joined together in a continuous chain. Being allowed to cut the chain, we can split the chain into several parts. The puzzle is solved when you can combine the sections to make specifically sized groups of rings for each day. The group must start with 1 ring on day 1 and then increase to 2 rings on day 2 all the way until every ring is included in the group. If we use a chain of 5 rings as an example. We can solve the puzzle by cutting the third ring. This splits the ring into 3 sections. $$2+1+2=5$$ On the first day our group only includes the middle section. 1. 1 The second day can include either the first or the third section 2. 2 On the third day be have to include either the first or third section along with the second section 3. 2+1 4. 2+2 5. 2+2+1 This continues until day 5 when all the rings are included. Obviously you can solve every puzzle with cuts on every ring and so the question becomes what is the smallest amount of $n$ cuts needed for and chain of $r$ rings.

In the Math of Wrath video they first ask what is the smallest amount of cuts needed for a chain of 7 rings. I managed to get the answer by pure chance, completely skipping the intended combinatorics answer. By cutting the third ring, the puzzle can be solved. Cutting the third ring splits the chain into three sections a link of 2 chains, a loose chain and a section of 4 chains.
$$2+1+4=7$$ Shown of days
6. $1$
7. $2$
8. $2+1$ 9. $4$ 10. $4+1$ 11. $4+2$ 12. $4+2+1$

The thing that I noticed about this sequence is how the groups repeat. We can split the days into three different parts 13. $1$

1. $2$

2. $2+1$

3. $4$

4. $4+1$
5. $4+2$
6. $4+2+1$ As you can see, the days can be split into groups. With every new group replacing and then recycling the sequence up to that point. It starts with the one cut ring, being by itself we cant go any further without involving a new link. And so we replace it with the need group, a link of two rings. This time we can move along further by recycling the previous group of one ring. These two groups together make 3 rings. But again with our current rings we are unable to reach day 4. However by replacing the previous days rings with a new link of 4 we can reach day 4 and recycle the previous sequence to get all the way to day 7.

Using this idea we can predict the most amount of rings we could use if we have a limited number of cuts. We can try out this method on a chain that we can cut 2 times. One more than before

In out previous sequence. The maximum number we could make is 7. So with an extra link in our disposal, the thought might become that to get a maximal number of valid rings, this link would contain 8 rings for a total of 15 days. However this fails to account for the extra cut ring.

We can lay the rings out like we did for before to get an idea of this. $$L_1+1+L_2+1+L_3=Total$$ We can start by counting the 2 loose rings as a single group, able to get us to day 2. Or day $n$ with $n$ cuts. In accordance with the pattern established previously our next group will need to replace the previous one for day 3. This can be achieved with a link of 3 rings. Without need for another link, we can recycle the loose chains to get to $3+2=5$, day 5. The next link will then have to logically contain 6 chains. You may notice this new link is double that of previous one. This is not a coincidence. If we think of the group of loose rings as $l_0$ and consecutive groups as $l_n$ we can define the relationship as such where the next group can replaces the previous one day after the previous reaches its maximum: $$l_0+1=l_1$$$$l_1+l_0+1=l_2$$$$l_1+l_1=l_2$$$$2l_1=l_2$$ And this relationship doesn't just stop here. For our next link the same rule can continue$$l_2+l_1+l_0+1=l_3$$$$l_2+l_2=l_3$$$$2l_2=l_3$$ Each time, the number of rings in a link doubles. So even without thinking about it. We can conclude that the last link is a a link of 6 rings. Putting this into form is $$3+1+6+1+12=Total$$ $$3+1+6+1+12=23$$ Testing this value shows that 23 is in fact the largest valid link of rings that create consecutive numbers up to day 23.

Using this doubling principle we can start making an equation that finds the largest chain that is valid with only $n$ cuts. By definition we need $n$ loose rings. The first link then will include one more ring than $n$ so that it can replace it for the previous day. Then the doubling starts. We can write the equation like this: $$n+(n+1)+2(n+1)+2(2(n+1)$$$$2+(2+1)+2(2+1)+2(2(2+1))=23$$This would be the equation for chain valid with 2 cuts as there are 3 links. However if we wanted a equation for any $n$ links, we can observe the property that by doubling amount of rings in a link, it can be described using powers of 2. $$n+2^0(n+1)+2^1(n+1)+...+2^n(n+1)$$ All of the powers of 2 share $n+1$ and so we can group it together like this. $$n+(n+1)(2^0+2^1+...+2^n)$$ This equation is great an all, I even saw a few people in the comments of the Wrath of Math video that had got this far. But the ugly repeated addition will never make this the end in my book. But how can we remove it? The answer comes down to principles with binary numbers. Binary blah blah blah
$$n+(n+1)(2^{n+1}-1)$$
$$n+(n+1)(2^{n+1})-(n+1)$$
$$(n+1)(2^{n+1})-1$$
$$(n+1)2^{(n+1)}-1$$
$$(n+1)2^{(n+1)}-1=r$$
Looking up the sequence that comes from this equation on OEIS shows that these are called Woodall (or Riesel) numbersalthough they come in a different form.
$$n2^n - 1$$
Our $n+1$'s have been substituted by $n$. And so this equation represents the maximum amount rings if you can only cut the chain $n-1$ times. Otherwise the principle of the equation remains the same.
What I find interesting is that 22 years earlier someone on OEIS described the connection between the puzzle solutions and this equation.
\"Sequence corresponds also to the maximum chain length of the classic puzzle whereby, under agreed commercial terms, an asset of unringed golden chain, when judiciously fragmented into as few as n pieces and n-1 opened links (through n-1 cuts), might be used to settle debt sequentially, with a golden link covering for unit cost. Here beside the n-1 opened links, the n fragmented pieces have lengths n, 2n, 4n, ..., 2^(n-1)n. For instance, the chain of original length a(5)=159, if segregated by 4 cuts into 5+1+10+1+20+1+40+1+80, may be used to pay sequentially, i.e., a link-cost at a time, for an equivalent cost up to 159 links, to the same creditor.\"
- Lekraj Beedassy, Feb 06 2003

Lambert W Function
$$(n+1)e^{\ln(2)^{(n+1)}}-1=r$$
$$(n+1)e^{\ln(2)(n+1)}=r+1$$
$$\ln(2)(n+1)e^{\ln(2)(n+1)}=\ln(2)(r+1)$$
$$W(\ln(2)(n+1)e^{\ln(2)(n+1)})=W(\ln(2)(r+1))$$
$$\ln(2)(n+1)=W(\ln(2)(r+1))$$
$$(n+1)=\frac{W(\ln(2)(r+1))}{\ln(2)}$$
$$n=\frac{W(\ln(2)(r+1))}{\ln(2)}-1$$ However if we test the expression for $2$ rings, it requires $0.2560590525972657$ cuts. What does this even mean? Evidently some rounding will have to take place. The options are rounding (the nearest digit), floor (down to the nearest digit), ceiling (up to the nearest digit). Rounding and what if we use the min instead of the max