These puzzles involve finding the number finding the best ordering or an optimal strategy for a given set of constraints.

You have set of twelve balls which appear identical. Eleven are all exactly the same weight, and the remaining ball is either a fraction heavier or a fraction lighter than the others. You are given a two-pan scale balance in which to weigh the balls against each other. You are asked to devise a scheme involving only 3 weighings which is guaranteed to find the 'odd ball' and determine whether it is heavier or lighter than the rest.

Having solved the question above, can you do the same thing but with 13 balls instead of 12?

- If so, give a scheme to find the odd ball. Can you then do the same for 14, 15, ...?
- If not, give a proof of its impossibility. Can you find a way round the problem; what else would you need?

Four friends (Alfred, Becky, Charlie, and David) wish to cross the old bridge over the river. However it is dark and the bridge is not very safe. They decide that no more than two of them my cross at a time, and that the people crossing should carry a torch with them.

Alfred is rather nimble on his feet and can cross the bridge in only one minute. Becky is a bit slower, and takes two minutes. Charlie is a little overweight, so takes four minutes. David is the slowest due to a sprained ankle. He takes eight minutes. They only have one torch between them, so when crossing in a pair, they must stick together, thus crossing at the speed of the slower person.

Devise a scheme for the four friends (and their torch) to cross the river in as short a time as possible.

You are standing in a hallway, and there are three switches on the wall, all in the 'off' position. You are told that there is a single light in a room off the hall, which exactly one of the switches operates. The other two do nothing. However, the door is closed and there is no way of telling the state of the light from the outside. Your challenge is to play with the light switches any way you like, and then to open the door and enter the room. Without further adjusting the switches, you must determine which of the three switches is connected to the light.

The king has 100 wise men to advise him. He thinks this is perhaps a bit excessive, so decides to reduce their number somewhat. He devises the following strategy which he outlines to his wise men one evening:

"At dawn tomorrow," says the king, "I shall take you all out to the main court and line you up in a random order around the edge. On each of your heads I will place a coloured hat - either red, green or blue. Naturally, you will be able to see the colour of all the hats except your own. Then, starting from the beginning of the line, I shall ask each of you in turn to guess the colour of his own hat. Those who are correct shall continue to be one of my wise men. Those who are wrong will be banished from my lands forever more." The king then added one final warning: "Apart from hearing the responses of those who guess before you, you shall be allowed no other form of communication. The guards will be watching you closely, and any sign of cheating will result is you all being banished."

But the wise men were very wise, and spent the rest of that evening working out their best strategy. How many of the 100 could they *guarantee* to save (even with no knowledge of the distribution and allocation of different hat colours)?

You are given 10 bags, each of which contains a large number of coins. Up to three of the bags may consist wholly of counterfeit coins, but the other bags consist wholly of genuine coins. Each genuine coin weighs exactly 1g, whereas each counterfeit coin weighs 0.9g. You have a set of digital scales that will accurately weigh any number of coins. However, you may only use the scales to perform one weighing. What is the minimum number of coins you need in each bag to be able to tell which bags (if any) contain counterfeit coins?