EvilMonkeyTheorem1

How many monkeys does it take to screw in a lightbulb?

Short answer: 1

Long answer:

Define n as the height of the lightbulb's position, s as the number of skrews in the lightbulb plate/installation, and k be the average height of a full-grown evil death-trained samurai monkey (the only readily available), assuming negligable deviation of heights.

We know that the EDTSM units each constitutes an assumed state of capability. One monkey can skrew in exactly one skrew at a time. Given the history of EDTSMs, we can assume that the monkey who skrews in the lightbulb will without failure, fall afterwards; as pounding a single skrew in with a paw has been proven to subject immediate large amounts of incapacitating blood-loss shortly after.

Given that the EDTSMs have no tools available to them, we must assume that they will use a tree structure (a monkey pyramid) in order to reach the lightbulb. This requires at least two monkeys below each 'parent' monkey. Therefore, we assume the height of the monkey tree as ceil(n/k), where n is the total height, and k is the height of each monkey-level.

We know that a full-spanned tree structure's height is logarithmic to it's area. Therefore, the minimum number of monkeys in the structure is 2^ceil(n/k), where the height is lg(ceil(n/k)). Deduced prior, we know that each structure will topple directly after each skrew is finished. However, EDTSMs are only capable of pounding one skrew in each.

Once the root monkey has completed his task, he will jump off; and a new monkey will climb the tree to the root position. We then deduce that each skrew requires one monkey to complete, including the initial root monkey (part of 2^ceil(n/k)), therefore the number of total monkeys required can not be less than 2^ceil(n/k) + s - 1, where s is the number of skrews in the lightbulb. We concider k as a constant in this case, therefore we can say that the asymptotic upper-bound of the number of required monkeys is equal to O(2^ceil(n/k)+s).

Proof by induction:

Assumptions:

• each monkey is of relatively-equal size, k.
• In the case of ceil(n/k) in {0,1}, we ignore the 0 as we still require a monkey in the tree, and one EDTSM is required per skrew.
• In the case of ceil(n/k) > 1, 2^ceil(n/k)+s-1 is the required number of EDTSM units.
• Let h <- ceil(n/k) (Height of structure required in monkeys)

BASIS (h = 1, s = 1):

This can be attributed to an open-display solution (only lightbulb / no skrews). We know that each skrew requires one monkey each.
2^h + s - 1 = 2¹ + 1 - 1 = 1 Proof: Valid

INDUCTION (h = 1, s > 1): (Require one EDTSM each s)

T(h, s+1) = 2^h + s + 1 - 1

= T(h, s) + 1 Proof: Valid

INDUCTION (H > 1, s = 1): (Require exactly one EDTSM tree)

We know: s - 1 = 0
T(h,s) = T(h) = 2^h
T(h+1) = 2^h+1 = 2^h*2 = T(h)*2 Proof: Valid

INDUCTION (h > 1, s > 1):

Let T(h) = 2^h, T(s) = s - 1
T(h) + T(s) = 2^h + s - 1
T(h+1) + T(s+1) = 2^h*2 + s

= 2*T(h) + T(s) + 1 Proof: Valid

Answer

Therefore, the number of monkeys it take to screw in a lightbulb is

2^ceil(n/k) + s - 1

Future Work

• Account for likelyhood of toppled tree at specified height limit.
• A more extensive examination of the issues discussed is needed.