Problems

Age
Difficulty
Found: 18

The king possesses \(7\) bags of gold coins, each containing \(100\) coins. While the coins in each bag appear identical, they vary in weight and they cannot be told apart by looking. The king recalls that within these bags, one contains coins that weigh \(7\)g each, another has coins weighing \(8\)g, the third bag contains coins weighing \(9\)g, the fourth has coins weighing \(10\)g, the fifth contains coins weighing \(11\)g, the sixth holds coins weighing \(12\)g, and finally, the seventh bag contains coins weighing \(13\)g each. However, he cannot remember which bag corresponds to which coin weight.
The king reported his situation to his chancellor, pointing to one of the bags, and asked how to determine the weight of the coins in that bag. The chancellor has large two-cup scales without weights. These scales can precisely indicate whether the weights on the cups are equal or, if not, which cup is heavier. Can the chancellor ascertain which coins are in the bag indicated by the king, using no more than two weightings? The chancellor is permitted to take as many coins as necessary to conduct the weightings.
image

There are \(20\) chairs in the room, which come in two colors: blue and red. Each chair is occupied by either a knight or a liar. Knights always tell the truth, while liars always lie. Initially, each of those seated claimed to be sitting on a blue chair. Then, they switched seats, after which half of the participants asserted that they were now sitting on blue chairs, while the other half claimed to be sitting on red ones. How many knights are currently occupying red chairs?

Now there are three doors with statements on them:

  1. There is nothing behind the third door.

  2. There is a trap behind the first door.

  3. There is nothing behind this door.

Your guide says: There is treasure behind one of the doors, trap behind another one and there is nothing behind the third door. The sign on the door leading to treasure is true, the sign on the door leading to a trap is false, and the third sign might be true or false.
Which door will you open, if you really really want the treasure?

This is a famous problem, called Monty Hall problem after a popular TV show in America.
In the problem, you are on a game show, being asked to choose between three doors. Behind each door, there is either a car or a goat. You choose a door. The host, Monty Hall, picks one of the other doors, which he knows has a goat behind it, and opens it, showing you the goat. (You know, by the rules of the game, that Monty will always reveal a goat.) Monty then asks whether you would like to switch your choice of door to the other remaining door. Assuming you prefer having a car more than having a goat, do you choose to switch or not to switch?
image

Each integer on the number line is coloured either yellow or blue. Prove that there is a colour with the following property: For every natural number \(k\), there are infinitely many numbers of this colour divisible by \(k\).

There are \(100\) non-zero numbers written in a circle. Between every two adjacent numbers, their product was written, and the previous numbers were erased. It turned out that the number of positive numbers after the operation coincides with the amount of positive numbers before. What is the minimum number of positive numbers that could have been written initially?

In a certain state, there are three types of citizens:

  • A fool considers everyone a fool and themselves smart;

  • A modest clever person knows truth about everyone’s intellectual abilities and consider themselves a fool;

  • A confident clever person knows about everyone intellectual abilities correctly and consider themselves smart.

There are \(200\) deputies in the High Government. The Prime Minister conducted an anonymous survey of High Government members, asking how many smart people are there in the High Government. After reading everyone’s response he could not find out the number of smart people. But then the only member who did not participate in the survey returned from the trip. They filled out a questionnaire about the entire Government including themselves and after reading it the Prime Minister understood everything. How many smart could there be in the High Government (including the traveller)?

Theorem: If we mark \(n\) points on a circle and connect each point to every other point by a straight line, the lines divide the interior of the circle is into is \(2n-1\) regions.
"Proof": First, let’s have a look at the smallest natural numbers.

  • When \(n=1\) there is one region (the whole disc).

  • When \(n=2\) there are two regions (two half-discs).

  • When \(n=3\) there are \(4\) regions (three lune-like regions and one triangle in the middle).

  • When \(n=4\) there are \(8\) regions, and if you’re still not convinced then try \(n=5\) and you’ll find \(16\) regions if you count carefully.

Our proof in general will be by induction on \(n\). Assuming the theorem is true for \(n\) points, consider a circle with \(n+1\) points on it. Connecting \(n\) of them together in pairs produces \(2n-1\) regions in the disc, and then connecting the remaining point to all the others will divide the previous regions into two parts, thereby giving us \(2\times (2n-1)=2n\) regions.

Let’s "prove" that the number \(1\) is a multiple of \(3\). We will use the symbol \(\equiv\) to denote "congruent modulo \(3\)". Thus, what we need to prove is that \(1\equiv 0\) modulo \(3\). Let’s see: \(1\equiv 4\) modulo \(3\) means that \(2^1\equiv 2^4\) modulo \(3\), thus \(2\equiv 16\) modulo \(3\), however \(16\) gives the remainder \(1\) after division by \(3\), thus we get \(2\equiv 1\) modulo \(3\), next \(2-1\equiv 1-1\) modulo \(3\), and thus \(1\equiv 0\) modulo \(3\). Which means that \(1\) is divisible by \(3\).

There are real numbers written on each field of a \(m \times n\) chessboard. Some of them are negative, some are positive. In one move we can multiply all the numbers in one column or row by \(-1\). Is that always possible to obtain a chessboard where sums of numbers in each row and column are non-negative?