Školjka

%V0 Consider a matrix of size $n\times n$ whose entries are real numbers of absolute value not exceeding $1$. The sum of all entries of the matrix is $0$. Let $n$ be an even positive integer. Determine the least number $C$ such that every such matrix necessarily has a row or a column with the sum of its entries not exceeding $C$ in absolute value.

%V0 In a country there are $n>3$ cities. We can add a street between $2$ cities $A$ and $B$, iff there exist $2$ cities $X$ and $Y$ different from $A$ and $B$ such that there is no street between $A$ and $X$, $X$ and $Y$, and $Y$ and $B$. Find the biggest number of streets one can construct! Official Wording The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge).

%V0 Given $n$ real numbers $x_1$, $x_2$, ..., $x_n$, and $n$ further real numbers $y_1$, $y_2$, ..., $y_n$. The entries $a_{ij}$ (with $1\leq i,\;j\leq n$) of an $n\times n$ matrix $A$ are defined as follows: $a_{ij}=\left\{\begin{array}{c}1\text{\ \ \ \ \ \ if\ \ \ \ \ \ }x_{i}+y_{j}\geq 0;\\ 0\text{\ \ \ \ \ \ if\ \ \ \ \ \ }x_{i}+y_{j}<0.\end{array}\right.$ Further, let $B$ be an $n\times n$ matrix whose elements are numbers from the set $\left\{0;\ 1\right\}$ satisfying the following condition: The sum of all elements of each row of $B$ equals the sum of all elements of the corresponding row of $A$; the sum of all elements of each column of $B$ equals the sum of all elements of the corresponding column of $A$. Show that in this case, $A = B$. comment (This one is from the ISL 2003, but in any case, the official problems and solutions - in German - are already online, hence I take the liberty to post it here.) Darij

%V0 Define a $k$-clique to be a set of $k$ people such that every pair of them are acquainted with each other. At a certain party, every pair of 3-cliques has at least one person in common, and there are no 5-cliques. Prove that there are two or fewer people at the party whose departure leaves no 3-clique remaining.

%V0 Let $n,k \in \mathbb{Z}^{+}$ with $k \leq n$ and let $S$ be a set containing $n$ distinct real numbers. Let $T$ be a set of all real numbers of the form $x_1 + x_2 + \ldots + x_k$ where $x_1, x_2, \ldots, x_k$ are distinct elements of $S.$ Prove that $T$ contains at least $k(n-k)+1$ distinct elements.

%V0 a) Show that the set $\mathbb{Q}^{ + }$ of all positive rationals can be partitioned into three disjoint subsets. $A,B,C$ satisfying the following conditions: $$BA = B; B^2 = C; BC = A;$$ where $HK$ stands for the set $\{hk: h \in H, k \in K\}$ for any two subsets $H, K$ of $\mathbb{Q}^{ + }$ and $H^2$ stands for $HH.$ b) Show that all positive rational cubes are in $A$ for such a partition of $\mathbb{Q}^{ + }.$ c) Find such a partition $\mathbb{Q}^{ + } = A \cup B \cup C$ with the property that for no positive integer $n \leq 34,$ both $n$ and $n + 1$ are in $A,$ that is, $$\text{min} \{n \in \mathbb{N}: n \in A, n + 1 \in A \} > 34.$$