Lambdia

Computational complexity

3 articles

Twelve Marbles, Three Weighings, and Twenty-Seven Ways to Land

Twenty-four possible answers against 3^3 = 27 outcome sequences leaves just enough room, and four against four splits those answers into exactly 8, 8 and 8. Six against six always tips, so it wastes the level outcome and leaves twelve answers for nine remaining sequences, which makes halving impossible rather than merely slow. The counting argument bounds outcome sequences rather than strategies, so it rules out every adaptive continuation at once, and the explicit schedule closes the positive half.

0

23 People Make a Shared Birthday a Coin Flip, and 253 Pairs Explain It

The reflex answer is around 180, half the calendar. The real threshold is 23, because a match needs a pair and 23 people carry 253 of them. The same reasoning puts the answer to "does anyone share MY birthday" at 253 people, eleven times the crowd, and the square-root threshold behind both is why a 64-bit random id collides after five billion draws rather than eighteen quintillion.

0