Hints: Brainteasers¶
The exercises are collapsed initially. Click on the title to expand.
Avoid looking at the hints too quickly. Allow at least 10 minutes of thinking before resorting to them.
Info
If you enjoy this kind of problems then have a look at Algorithmic Puzzles and Cracking the coding interview.
Note
These are not assessment-type questions. You will not be examined on similar questions.
The aim is to train you to look at problems and go through the thinking process of solving them. This is a general important skill required in this module and in life as a whole!
Question 1¶
Q1
Add the missing arithmetic operators (\(+,-,\times,/\)) and parentheses to the following expression to make it true:
Think outside the box! If the result is an integer then it is not always produced by other integers, e.g \(1/2\times 6 = 3\).
You can use the same operator more than once.
If you divide by ½ then it is equivalent to multiplying by 2.
Question 2¶
Q2
A little girl counts from 1 to 1000 using the fingers of her left hand as follows. She starts by calling her thumb 1, the first finger 2, middle finger 3, ring finger 4, and little finger 5. Then she reverses direction, calling the ring finger 6, middle finger 7, the first finger 8, and her thumb 9, after which she calls her first finger 10, and so on. If she continues to count in this manner, on which finger will she stop?
....
Question 3¶
Q3
There are 100 closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed.
He continues like this until his 100\(^\text{th}\) pass in the hallway, in which he only changes the state of locker number 100.
How many lockers will be left open at the end?
Try to write a quick script to simulate the process, then see if you see a patern.
Think about a specific locker \(\ell\): how often do we toggle its state?
Question 4¶
Q4
There are eight identical-looking coins; one of these coins is counterfeit and is known to be lighter than the genuine coins.
What is the minimum number of weightings needed to identify the fake coin with a two-pan balance scale without weights?
...
Question 5¶
Q5
You have a 5 litre jug and a 3 litre jug, and an unlimited supply of water, but no measuring cups.
How would you come up with exactly 4 litre of water?
...
Question 6¶
Q6
Little Alice has 10 pockets and £44 in £1 coins.
She wants to put her coins in her pockets so distributed that each pocket contains a different number of pounds.
Can she do so?
Not possible, but why?
What is the smallest number of coins that ensures we have different number of coins in each pocket?
Question 7¶
Q7
Below is an \(8\times 8\) chess board in which two diagonally opposite corners have been cut off.
You are given plenty of dominoes, such that each domino can cover exactly two squares.
Can you cover the entire board with dominoes? (No dominoes are allowed to overlap or be partly outside the board.)
Can you prove your answer is correct? (Show an example solution if this is possible, or show that it is impossible.)
Not possible... why?
How about if the 2 squares were both black?
Does it matter if the squares are from the opposite corners, or from anywhere else?
Idea of invariant.