If you like cool problems, here is one I have not found a simple solution for, but I once saw it in a place where a simple solution should exist.

You have an odd number >=3 of items with the property that any time you remove one, there is a way to split the remaining items into two equal count piles of equal weight. Show all items have the same weight.

It's easy for 3 items, A,B,C. Remove C, A balances B, then do A,C, now all equal.

It's easy to check by hand for a few small cases.

I proved it using more advanced stuff from lin alg. But I've never found a simple solution yet.

EDIT: corrected with "equal count piles"

The puzzle is related to the game 20 questions. If you can ask only 20 yes/no questions, you can differentiate 2^20 items. For example, with 20 yes/no questions, you can determine an integer in 1 to 1,000,000 (technically, up to 2^20).

Now consider you need to figure out what integer between 1 and 1,000,000 I am think of, but I am allowed to lie at most once. Now how many questions will you need to ensure you get the answer?

Doing this by hand and creating more and more convoluted tricks is possible, but in reality this is another error correction problem: The original problem is a binary message of length 20 bits, from which you get the 20 bit message.

With at most one lie, there is a 20 bit message, me (the noisy channel) can add at most one error, so you need the minimal length binary code that takes a message of length 20 and a max error of 1 bit.

To find the number needed, use a coding table like http://www.codetables.de/.

So you need to find how many more bits you need. To fix d bits, you need 2d+1 'distance' in your code to make sure d errors do not move one valid point within Hamming distance d of another answer, so we need d = 3.

So you need a binary code, d = 3, and encoding a message of length k=20. Click on Linear Codes, then the GF2 button, and you see the big table of best codes. Find the column with k = 20 (our message length), scroll down over increasing n (number of questions needed), until the first d=3 entry. There n = 25, so 25 questions will do it. This is the result http://www.codetables.de/BKLC/BKLC.php?q=2&n=25&k=20

This is provably best, otherwise the table would have a range if there were not proof (look around the table, notice some are ranges).

To design the questions, most places with tables have code constructions. So click the entry, and they describe the construction (unfortunately in error correction code terms), but that can be reversed into English and actual questions to get your answer.

This technique would let you answer any problem along the line of "How many questions, each with b options, would it take to determine between N items, if there are at most d lies told?"