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

One Gold Bar, Two Cuts, Seven Evenings: 1, 2 and 4

Seven pieces cost six cuts and the schedule pays correctly, so the six-cut answer breaks one constraint and nothing else. Because the worker can hand pieces back, the contract is on his holding rather than on the transfer, and the ledger turns out to be a three-bit counter. Brute force finds 1-2-4 is the only three-piece solution.

0

23 personnes suffisent pour un anniversaire commun, et 253 paires l'expliquent

La réponse réflexe tourne autour de 180, la moitié du calendrier. Le vrai seuil est 23, parce qu'une coïncidence demande une paire et que 23 personnes en portent 253. Le même raisonnement met la question « quelqu'un partage-t-il MON anniversaire » à 253 personnes, onze fois plus de monde, et le seuil en racine carrée derrière les deux explique qu'un identifiant aléatoire de 64 bits se répète après cinq milliards de tirages et non dix-huit trillions.

0