Sociopath Community

1.1 The Tower of Hanoi

The Tower of Hanoi consists of a platform with three pegs. On one of the pegs there is a tower of disks of varying sizes, the largest disk sits at the bottom while the smallest disk sits at the top.
The goal of tower of Hanoi is to transfer all of the disks from the peg they are sitting on at the start to one of the other pegs.

Rules:
You can only move one disk at a time.
You can never have a larger disk sitting on top of a smaller disk.
All pegs can be utilized.
Game is over when the tower has been reconstructed at a new peg.

We are interested in the minimum number of moves necessary to complete the game.

The process of Generalization is a useful technique in finding the answer to our question. Generalization allows us to explore a problem in a multitude of its possible cases, in doing so we hope to find a pattern whose behavior is describable via some mathematical object.
In generalizing we can scale our problem to the very small or very large to test its behavior.

We are interested in the minimum number of moves necessary to complete the game.

Let the minimum number of moves be denoted as Tₙ where n is the number disks.

n = 0, T₀ = 0
n = 1, T₁ = 1
n = 2, T₂ = 3

T₀ is obvious, o disks implies 0 moves.

T₁ is obvious because to move one disk from one peg to another will only require a single move.

T₂ requires 3 moves because we move disk one (smallest) to another peg and then disk two (largest) to the peg where disk one is not at ,because disk one is smaller than disk two, and then we move disk one on top of disk two. 3 moves total.

Generalization for n disks,

(1) Moving the smallest disks :

We first transfer the n-1 disks to a different peg, that is if there was n = 8 disks we have transferred 7 to a new peg.
Transferring n-1 disks requires Tₙ₋₁ moves, that is if n = 8 the number of moves it took to transfer n = 7 is Tₙ₋₁.

(2) Moving the largest disk :
We move the largest disk to a different peg, this is effectively n = 1 which requires T₁ = 1 moves.

(3) Move the smallest disks back onto the largest disk (reconstruct tower on new peg)
This again requires moving n - 1 disks which takes Tₙ₋₁ moves

By this point we have reconstructed the tower on a new peg and we can see the basic arithmetic required in approximating Tₙ moves for n disks.

We had to move Tₙ₋₁ twice, that is 2*Tₙ₋₁.
We had to move n = 1 once that is an additional single move.

Hence,
Tₙ >= 2Tₙ₋₁ + 1 for n > 0

Note the conditional n > 0, this is the case because our relation for Tₙ returns 1 for n = 0 yet we know T₀ = 0

We can describe the minimum number of disks via the two relations,
Tₙ = 0 for n = 0
Tₙ = 2Tₙ₋₁ + 1 for n > 0

Note our relation for n > 0 to compute Tₙ requires that we know Tₙ₋₁, this problem is recursive because our function Tₙ requires we compute that function for a different argument.

Whenever we have inequalities that describe a function in like those above we call them a Recursion Relation.

Recursion Relations in general are not as fast as closed from solutions, but recursion relations can help us on our way to finding closed form solutions.

We use Tₙ >= 2Tₙ₋₁ + 1 to compute different instances of n

T₀ = 0
T₁ = 2(0) + 1 = 1
T₂ = 2(1) + 1 = 3
T₃ = 2(3) + 1 = 7
T₄ = 2(7) + 1 = 15
T₅ = 2(15) + 1 = 31
T₆ = 2(31) + 1 = 63

It could be noticed after some thought that 2ⁿ results in some interesting values
2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
2⁶ = 64

From with this we notice that 2ⁿ results in value 1 greater than the Tₙ we are looking for, at least for the instances of n we have tested.

We are lead to believe that Tₙ = 2ⁿ - 1

To prove Tₙ = 2ⁿ - 1 we use induction.

T₀ = 2⁰ - 1 = 1 - 1 = 0

Assume for k that Tₖ = 2ᵏ - 1
We want to show that Tₖ₊₁ = 2ᵏ⁺¹ - 1

We know that
Tₖ = 2Tₖ₋₁ + 1
Tₖ₊₁ = 2Tₖ + 1

Tₖ₊₁ = 2(2ᵏ - 1) + 1
= 2ᵏ⁺¹ - 2 + 1
= 2ᵏ⁺¹ - 1

Hence, Tₙ = 2ⁿ - 1 is true for all instances of n.

Upshot of Section:

(1) Look at small cases. This gives us insight into the problem.
(2) Find and prove a mathematical expression for the quantity of interest.
(3) Find and prove a closed from our mathematical expression.

I find this kind of spam 1.61803398874989484820... times better better than certain other kinds of spam.

1.2 Lines in a Plane

What is the maximum number Lₙ of regions defined by n lines in the plane?

We use the process of generalization and focus on small cases.

Zero lines implies that only the original single region exists.
n=0 -> L₀=1
One line bisects a region and splits it into two.
n=1 -> L₁=2
For two lines we have one line that bisects the region into two regions and the second line that slits those two regions into four regions. This holds regardless of if the lines intersect or not.
n=2 -> L₂=4

Looking at the first three cases we see Lₙ double each time, so we could run with the idea that with each newly added line the number of regions doubles.
Lₙ=2ⁿ is a good guess because it serves as a doubling function.
L₀=2⁰=1
L₁=2¹=2
L₂=2₂=4
We could then make a prediction as to what the value of L₃ is.
L₃=2³=8

If we draw two lines we know L₂=4 no mater how we draw the lines.
If we draw a third line we will see that 7 regions, 6 exterior regions and one internal region defined by the three lines.
Hence, we know that Lₙ=2ⁿ is not the model.

Lₙ can be described using the previous value of the last set of lines, that is Lₙ₋₁. This makes sense generally because to draw n number of lines to define Lₙ you must draw n-1 lines and define Lₙ₋₁ first.

Lₙ <= Lₙ₋₁ + n for n > 0

L₃ <= 4 + 3 = 7

Our description is currently an inequality because depending on how we draw the third like we will get seven or six as an answer to L₃. The answer is dependent on the intersections between out lines. If a given line intersects all other lines in the same place we will get Lₙ < Lₙ₋₁ + n while if a given like intersects all other lines in different places we will obtain Lₙ = Lₙ₋₁ + n.

We are interested in the latter case, where a given line intersects all others in different places. As such we can treat our inequality as equality.
Lₙ = Lₙ₋₁ + n for n > 0.

Now we have a recursive relations,

Lₙ = {1 for n=0
       {Lₙ‐₁ + n for n>0

Again, recursive relations are inefficient to compute so ideally we want to find a closed form solution.

A useful tool in dealing with recursive relations is unfolding them.

This concept of unfolding is really just using equivalence,

Lₙ = Lₙ₋₁ + n
Lₙ₋₁ = Lₙ₋₂ + (n - 1)
Lₙ₋₂ = Lₙ₋₃ + (n - 2)
. . .

We can expand Lₙ using this method,
Lₙ = Lₙ₋₁ + n
    = Lₙ₋₂ + (n - 1) + n
    = Lₙ₋₃ + (n - 2) + (n - 1) + n
      .
      .
      .
    = L₀ + 1 + 2 + . . . + (n - 2) + (n - 1) + n

The section 1 + 2 + . . . + (n - 2) + (n - 1) + n is the famous triangular numbers denoted as Sₙ.

Hence, Lₙ can be written in the following way,
Lₙ = L₀ + Sₙ
    = 1 + Sₙ

We can create a table to understand the relationship between n and Sₙ

n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
-------------------------------------------------------------------------------------
Sₙ| 1 | 3 | 6 |10 |15 |21 |28 |36 |45 | 55 | 66 | 78 | 91 |105 |

To evaluate Sₙ we use Gauss method, this works in the following way using the first 10 numbers.
   Sₙ = 1 + 2 + 3 + . . . + 8 + 9 + 10
+ Sₙ = 10 + 9 + 8 + . . . + 3 + 2 + 1
-------------------------------------------------
  2Sₙ = 11 + 11 + 11 + . . . 11 + 11 + 11

We get the sum of 11 100 times, hence, 2Sₙ = 10(11) -> Sₙ=10(11)/2 = 110/2 = 55

For n cases,
   Sₙ = 1 + 2 + 3 + . . . + (n-1) + n
+ Sₙ = n + (n-1) + . . . + 3 + 2 + 1
------------------------------------------------------------------
  2Sₙ = (n+1) + (n+1) + (n+1) + . . . (n+1) + (n+1) + (n+1)

2Sₙ = n(n+1) -> Sₙ = n(n+1)/2 for n >=0

We now can formulate the closed solution,
Lₙ = n(n+1)/2 + 1 for n>=0

We prove the closed form via induction,
L₀ = 1 + 0(0+1)/2 = 1 + 0 = 1
Assume Lₖ = 1 + k(k+1)/2
We want to show that Lₖ₊₁ = 1 + (k+1)((k+1)+1)/2
We know Lₖ = Lₖ₋₁ + k (recursive relation)
So, Lₖ₊₁ = Lₖ + (k+1)
Given Lₖ we have Lₖ₊₁ = 1 + (k(k+1)/2) + k + 1
                                   = 1 + (k(k+1)/2) + 2(k+1)/2
                                   = 1 + (k² + 3k + 2)/2
                                   = 1 + (k+1)(k+1+1)/2
                                   = 1 + (k+1)((k+1) + 1)/2
Hence, Lₖ₊₁ = 1 + (k+1)((k+1)+1)/2

The closed form is proven.

1.3 The Josephus Problem

There are n people numbered 1 to n around a circle, we eliminate every second remaining person until only one is left.

Let n = 10 -> 1,2,3,4,5,6,7,8,9,10
The order of elimination in the first round is 2,4,6,8,10
1,3,5,7,9 are left, we continue to eliminate every second person until one is left.
The order of elimination is 3,7,1,9
Hence, 5 is the winner.

Let the winners number be denoted as J(n).

Here is a table that shows us the results of J(n) for the first 6 cases.

n   | 1 2 3 4 5 6
-----------------------
J(n)| 1 1 3 1 3 5

Notice that each value for J(n) regardless of n is an odd number, this is because, and it can be seen in our n=10 case, that the first round of elimination removes all even values.

If n is an even number after a round of elimination we end up in a vary similar situation if we re-index the values.

Here is a table displaying the index for round 1 of n = 10,
i  |1 2 3 4 5 6 7 8 9 10
r₁|1 2 3 4 5 6 7 8 9 10

Notice the index is the same as the values 1 to n and all even indexes will be eliminated first round.

By the second round odd numbers now have even indexes,
i  |1 2 3 4 5
r₂|1 3 5 7 9

Still only even indexes will be eliminated which implies 3 and 7 are gone in round two.

Round three,
i  |1 2 3
r₃|9 1 5

We write r₃ in a different order because the last index (5) in round two was an odd, when this happens we put the number at that index at index (1) in the next round.

In round three 1 is eliminated because it has an even index

Round four,
i |1 2
r₄|5 9

9 is eliminated because it has an even index and that leaves us with 5, hence J(10) = 5

Suppose we have 2n people originally, then after the first round we have 1, 3, 5, 7, . . . , 2n-3, 2n-1.

2n - 3 and 2n - 1 are the last two odd numbers, recall by definition if x is even then 2|x.

At the start of a new round a persons number has doubled and decreased by 1, this can be considered the rule behind the index changes between round.

J(2n) = 2J(n) - 1 for n >=1

We now have a working but limited formulation of how to compute J(n).

J(10) = 2J(5) - 1 = 2(3) - 1 = 6 - 1 = 5
J(20) = 2J(10) - 1 = 2(5) - 1 = 10 - 1 = 9
J(40) = 2J(20) - 1 = 2(9) - 1 = 18 - 1 = 17

J(40) = J(5(8)) = J(5(2³))

So, the formulation J(5(2ᵐ)) = 2ᵐ⁺¹+1 works for the above cases as well.

In the case of an odd number of people, that is 2n+1 people, the person number 1 is wiped out just after 2n leaving 3 5 7 9 . . . 2n-1 2n+1

In this case everyone's number is doubled and increased by 1, hence J(2n + 1) = 2J(n) + 1

We now have two equations, one that can deal with the even case and one to deal with the odd case

The Recursive Relation,

J(1)       = 1
J(2n)     = 2J(n)-1 for n>=1
J(2n+1) = 2J(n)+1 for n>=1

Of course we want a closed from solution, we can build a table of values with the recursion relation

   n|1|2 3|4 5 6 7|8 9 10 11 12 13 14 15|16
J(n)|1|1 3|1 3 5 7|1 3   5    7  9 11 13 15|1

Notice that J(n) counts up the odd integers and whenever n=J(n) the count starts over.
Each count is grouped by a power of two.

At the start of each group J(n) = 1 and then increases by 2 within the group.

we can write n as n = 2ᵐ + l where 2ᵐ is the largest power of 2 not exceeding n and where l is what's left.

Hence, our solution seems to be J(2ᵐ+l) = 2l + 1 for m>=0 and 0<=l<2ᵐ

Now we must prove by induction :

If m=0 then l=0 hence J(1)=1
If m>0 and 2ᵐ+l=2n then l is even
J(2ᵐ+l)=2J(2ᵐ⁻¹+1/2) - 1 = 2l + 1