Problems

Is it possible to cover a \((4n+2) \times (4n+2)\) board with the \(L\)-tetraminos without overlapping for any \(n\)? The pieces can be flipped and turned.

Is it possible to cover a \(4n \times 4n\) board with the \(L\)-tetraminos without overlapping for any \(n\)? The pieces can be flipped and turned.

There are \(100\) people standing in line, and one of them is Arthur. Everyone in the line is either a knight, who always tells the truth, or a liar who always lies. Everyone except Arthur said, "There are exactly two liars between Arthur and me." How many liars are there in this line, if it is known that Arthur is a knight?

Show that a bipartite graph with \(n\) vertices cannot have more than \(\frac{n^2}{4}\) edges.

In a graph \(G\), we call a matching any choice of edges in \(G\) in such a way that all vertices have only one edge among chosen connected to them. A perfect matching is a matching which is arranged on all vertices of the graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have degree at least \(n\) (the number of edges exiting the vertex). Prove that one can choose a perfect matching in \(G\).

A new customer comes to the hotel and wants a room. It happened today that all the rooms are occupied. What should you do?

Now imagine you got \(10\) new guests arriving to the completely full hotel. What should you do now?

The next day you have even harder situation: to the hotel, where all the rooms are occupied arrives a bus with infinitely many new customers. In the bus all the seats have numbers \(1,2,3...\) corresponding to all natural numbers. How to deal with this one?

Imagine you have \(2\) new guests arriving to the full hotel. How do you accommodate them?

What would you do about \(10000\) new guests arriving to the full hotel?