Problems

For three sets \(A,B,C\) prove that \(A - (B\cup C) = (A-B)\cap (A-C)\). Draw a Venn diagram for this set.

For three sets \(A,B,C\) prove that \(A - (B\cap C) = (A-B)\cup (A-C)\). Draw a Venn diagram for this set.

Consider a set of natural numbers \(A\), consisting of all numbers divisible by \(6\), let \(B\) be the set of all natural numbers divisible by \(8\), and \(C\) be the set of all natural numbers divisible by \(12\). Describe the sets \(A\cup B\), \(A\cup B\cup C\), \(A\cap B\cap C\), \(A-(B\cap C)\).

In a distant village, there are \(3\) houses and \(3\) wells. Inhabitants of each house want to have access to all \(3\) wells. Is it possible to build non-intersecting straight paths from each house to each well? All houses and well must be level (that is, none of them are higher up, like on a mountain, nor are any of them on lower ground, like in a valley).

In good conditions, bacteria in a Petri cup spread quite fast, doubling every second. If there was initially one bacterium, then in \(32\) seconds the bacteria will cover the whole surface of the cup.

Now suppose that there are initially \(4\) bacteria. At what time will the bacteria cover the surface of the cup?

A piece containing exactly \(4\) black cells is cut out from a regular \(8\) by \(8\) chessboard. You are only allowed to cut along the edges of the cells and the piece must be connected - namely you cannot have cells attached only with a vertex, they have to share a common edge.

Find the largest possible area of such a piece.

A parliament has 650 members. In this parliament there is only one house and every member has at most three enemies. We wish to split this parliament into two separate houses in such a way that each member will have at most one enemy in the same house as them. We assume that hard feelings among members of parliament are mutual, namely if \(A\) recognises \(B\) as their enemy, then \(B\) also recognises \(A\) as their enemy.

Is this splitting possible?

Find all \(n\) such that a closed system of \(n\) gears in a plane can rotate. We call a system closed if the first gear wheel is connected to the second and the \(n\)th, the second is connected to the first and the third, the third is connected to the second and the fourth, the fourth is connected to the third and the fifth, and so on until the \(n\)th is connected to the \(n-1\)th and the first. In the picture, we have a closed system of three gears.

How many subsets are there of \(\{1,2,...,n\}\) (the integers from \(1\) to \(n\) inclusive) containing no consecutive digits? That is, we do count \(\{1,3,6,8\}\) but do not count \(\{1,3,6,7\}\).
For example, when \(n=3\), we have \(8\) subsets overall but only \(5\) contain no consecutive integers. The \(8\) subsets are \(\varnothing\) (the empty set), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1,3\}\), \(\{1,2\}\), \(\{2,3\}\) and \(\{1,2,3\}\), but we exclude the final three of these.

Remainder is the number that is “left over" from division. Even if a number is not divisible by another number fully, we can still divide, but leaving a remainder. The remainder is less than the number we’re dividing by. For example, a remainder of \(44\) in division by \(7\) is \(2\), because \(44 = 6 \times 7 + 2\). More generally, we can write \(n=qk+r\), where \(0\leq r<k\). We say that \(k\) goes into \(n\) \(q\) times, and a little bit (\(r\)) is left. If that little bit was larger than \(k\), it could “go into" \(n\) once more.

The general rule is that a remainder of a sum, difference or a product of two remainders is equal to the remainder of a sum, difference or a product of the original numbers. What that means is if we want to find a remainder of a product of two numbers, we need to look at the individual remainders, multiply them, and then take a remainder.

For example, \(10\) has remainder \(3\) when dividing by \(7\) and \(11\) has remainder \(4\) when dividing by \(7\). The product \(10\times11=110\) will have the same remainder as the product of the individual remainders. We first multiply \(3\times4=12\) and then take a remainder upon division by \(7\), which is \(5\) because \(12=7+5\). That means that \(110\) gives a remainder \(5\) in division by \(7\) - and it does, because \(110=15\times7+5\). If a number is divisible by a number we are dividing it, nothing remains and we say the remainder is \(0\).

Let’s have a look on some examples: