Four Crates, All Lies

Question

Four sealed crates each contain a single commodity: almonds, beans, coffee, or dates, one commodity per crate. The stencilled labels were applied so badly that every crate is mislabeled. You may pull one sample item at a time from a crate of your choice, look at it, then decide where to pull next. What is the minimum number of pulls that guarantees you can relabel all four crates correctly?

Accepted Answer

Two pulls. Lower bound, information count. The label assignments with every crate wrong are the derangements of 4 objects: there are D_4 = 9 of them. A pull from a crate labeled X returns one of at most 3 commodities (never X), so one pull distinguishes at most 3 worlds: 3 < 9, one pull cannot suffice. Two pulls give at most 3 times 3 = 9 outcomes, exactly enough, so the bound is 2 if an actual scheme uses every outcome perfectly. Achievability, adaptive scheme. Pull from the crate labeled almonds. Say it yields beans (the other two outcomes are symmetric). The surviving worlds, writing contents in label order (almonds, beans, coffee, dates), are exactly three: (b,a,d,c), (b,c,d,a), (b,d,a,c). Their second coordinates are a, c, d: all different. So pull next from the crate labeled beans; its content names the world outright, and you relabel all four crates with certainty. Exhaustive check over all 9 derangements and all first-pull outcomes confirms 2 always suffices. The part interviewers probe: adaptivity is load-bearing. If you had to announce both pulls in advance, two pulls would fail: for every fixed pair of crates there exist two derangements agreeing on both pulled crates an

Four Crates, All Lies

Problem

Your answer

Hints

More Brainteasers & Logic to train on