There are 100 prisoners, numbered 1-100. The prisoners' numbers are written onto 100 cards, put randomly into 100 envelopes numbered 1-100. They can't communicate, but are invited, one by one, to open 50 envelopes. If any prisoner fails to find his number, they all get killed.
I can't think of any right now, certainly not with the same magnitude of difference between chance and strategy. The "twelve coins problem" might meet your criterion, but I always hated it: I could never get my head around deducing the answer...