Problems
In an \(n \times n\) board the squares are painted black or white in some way. Three of the squares in the corners are white and one is black. Show that there is a \(2\times 2\) square with an odd number of white unit squares.
On an \(8\times 8\) board there is a lamp in every square. Initially every lamp is turned off. In a move we choose a lamp and a direction (it can be the vertical direction or the horizontal one) and change the state of that lamp and all its neighbours in that direction. After a certain number of moves, there is exactly one lamp turned on. Find all the possible positions of that lamp.
In an \(5\times 5\) board one corner was removed. Is it possible to cover the remaining board with linear trominos (\(1\times 3\) blocks)?
One can hardly imagine modern life without numbers, but have you wondered when and how the numbers were invented? It turns out people started using numbers about \(42000\) years BCE supposedly to mark the dates in calendar. But how do we represent the numbers in writing? Well, there are two ways: examples of the first abstract numeral systems are generally tallying systems, the ones where the value or contribution of a digit does not depend on its position, a good example is the famous Roman numeral system: \(I\, V\, X\, L\, C\, D\, M\), here a digit has only one value: \(I\) means one, \(X\) means ten and \(C\) a hundred. However, one might struggle to express large numbers in Roman system.
Majority of ancient civilisations, Sumerian, Egyptian, Babylonian, Chinese, Japanese, Indian used what is called positional numeral systems, where the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. All these systems, even when invented independently, have something in common, they are what is called "base-\(10\)".
Try to guess why do we use the decimal numeral system, which has exactly \(10\) digits in our everyday use. Because it does not actually have to be \(10\) digits, it could easily be \(3,8,16\), the binary system (with only digits \(0\) and \(1\)) is used in all electronic devices, since it is enough to represent any bit of information we might possibly know.
Convert the binary number \(10011\) into decimal, and convert the decimal number \(28\) into binary. Multiply by \(2\) as binary numbers both \(10011\) and the result of conversion of \(28\) into binary numbers.
The ternary numeral system has only \(3\) digits: \(0,\) \(1\) and \(2\). Therefore the number \(3\) is written in ternary as \(10\). Write down the numbers \(23\) and \(156\) in ternary and add them as ternary.
Write down the first fifteen numbers in binary system.
Given a natural number \(n\) you are allowed to perform two operations: "double up", namely get \(2n\) from \(n\), and "increase by \(1\)", i.e. to get \(n+1\) from \(n\). Find the smallest amount of operations one needs to perform to get the number \(n\) from \(1\).
Alice the fox and Basilio the cat have grown \(20\) counterfeit bills on a money tree and now write seven-digit numbers on them. Each bill has \(7\) empty cells for numbers. Basilio calls out one digit "1" or "2" (he doesn’t know the others), and Alice writes the number into any empty cell of any bill and shows the result to Basilio. When all the cells are filled, Basilio takes as many bills with different numbers as possible (out of several with the same number, he takes only one), and the rest is taken by Alice. What is the largest number of bills Basilio can get, regardless of Alice’s actions?
The king decided to reward a group of \(n\) wise men. They will be placed in a row one after the other (so that everyone is looking in the same direction), and each is going to wear a black or a white hat. Everyone will see the hats of everyone in front, but not those behind them. The wise men will take turns (from the last to the first) to name the color (white or black) and the natural number of their choice.
At the end, the number of sages who have named the color of their hat correctly is counted: that is exactly how many days the whole group will be paid a salary raise. The wise men were allowed to agree in advance on how to respond. At the same time, the wise men know that exactly \(k\) of them are insane (they do not know who exactly). Any insane man names the color white or black, regardless of the agreement. What is the maximum number of days with a pay supplement that the wise men can guarantee to a group, regardless of the location of the insane in the queue?