Problems

Let’s prove the following statement: every graph without isolated vertices is connected.
Proof We use the induction on the number of vertices. Clearly the statement is true for graphs with \(2\) vertices. Now, assume we have proven the statement for graphs with up to \(n\) vertices.
Take a graph with \(n\) vertices by induction hypothesis it must be connected. Let’s add a non-isolated vertex to it. As this vertex is not isolated, it is connected to one of the other \(n\) vertices. But then the whole graph of \(n+1\) vertices is connected!

Let’s compute the infinite sum: \[1+2 + 4 + 8 + 16 + ... + 2^n + ... = c\] Observe that \(1+2+4+8+... = 1 + 2(1+2+4+8+16+...)\), namely \(c = 1+2c\), then it follows that \[c = 1+2+4+8+... = -1.\]

Let’s prove that any \(90^{\circ}\) angle is equal to any angle larger than \(90^{\circ}\). On the diagram

We have the angle \(\angle ABC = 90^{\circ}\) and angle \(\angle BCD> 90^{\circ}\). We can choose a point \(D\) in such a way that the segments \(AB\) and \(CD\) are equal. Now find middles \(E\) and \(G\) of the segments \(BC\) and \(AD\) respectively and draw lines \(EF\) and \(FG\) perpendicular to \(BC\) and \(AD\).
Since \(EF\) is the middle perpendicular to \(BC\) the triangles \(BEF\) and \(CEF\) are equal which implies the equality of segments \(BF\) and \(CF\) and of angles \(\angle EBF = \angle ECF\), the same about the segments \(AF=FD\). By condition we have \(AB=CD\), thus the triangles \(ABF\) and \(CDF\) are equal, thus \(\angle ABF = \angle DCF\). But then we have \[\angle ABE = \angle ABF + \angle FBE = \angle DCF + \angle FCE = \angle DCE.\]

Let’s prove that \(1=2\). Take a number \(a\) and suppose \(b=a\). After multiplying both sides we have \(a^2=ab\). Subtract \(b^2\) from both sides to get \(a^2-b^2=ab-b^2\). The left hand side is a difference of two squares so \((a-b)(a+b)=b(a-b)\). We can cancel out \(a-b\) and obtain that \(a+b=b\). But remember from the start that \(a=b\), so substituting \(a\) for \(b\) we see that \(2b=b\), dividing by \(b\) we see that \(2=1\).

Let’s prove that \(1\) is the smallest positive real number: Assume the contrary and let \(x\) be the smallest positive real number. If \(x>1\) then \(1\) is smaller, thus \(x\) is not the smallest. If \(x<1,\) then \(\frac{x}{2}<x\) so \(x\) can not be the smallest either. Then \(x\) can only be equal to \(1\).

Nick has written in some order all the numbers \(1,2,...33\) at the vertices of a regular \(33\)-gon. His little sister Hannah assigned to each side of the \(33\)-gon the number equal to the sum of the numbers at the ends of that side. It turns out that Hannah obtained \(33\) consecutive numbers in certain order. Can you find an arrangement of numbers as written by Nick which lead to this situation?

Sometimes proof of a statement requires elaborate reasoning, but sometimes it enough to provide an example when the described construction works. Often enough the problem is asking whether an event is possible, or if an object exists under certain conditions making the existence seemingly unlikely, in such cases all you need to do is to provide an example to solve the problem. Today we will see how to construct such examples.

In how many ways can you read the word TRAIN from the picture below, starting from T and going either down or right at each step?

There are \(100\) people in a room. Each person knows at least \(67\) others. Show that there is a group of four people in this room that all know each other. We assume that if person \(A\) knows person \(B\) then person \(B\) also knows person \(A\).

The numbers \(a\) and \(b\) are integers and the number \(p \ge 3\) is prime. Suppose that \(a+b\) and \(a^2 +b^2\) are divisible by \(p\). Show that \(a^2 + b^2\) is divisible by \(p^2\).