BME math contest 2020

deadline: 29 May 12 o'clock midnight
number of problems that can be handled in: 5

Problem nr. 1

Prove that $\frac{2}{2^{2n}}\sum_{k=0}^n \left(\begin{matrix}2n \\ 2k \end{matrix}\right)13^k$ is an integer equal to $1$ modulo $3$ for every $n=1,2,\ldots$! (7 points)

Problem nr. 2

Let $p:\mathbb R^n\to \mathbb R$ be a multivariate real polynomial and $h(x_1,\ldots,x_n)=$ $x^2_1+\ldots +x^2_n-1$. Prove: if the zero-set of $h$ (i.e. the set of points ${\mathbf x}\in \mathbb R^n$ for which $h({\mathbf x})=0$) is contained in the zero-set of $p$, then $p$ can be written as a product $p= qh$ where also $q$ is a polynomial! (7 points)

Problem nr. 3

On the white real plane we mark all points having integer coordinates only, with black. A point $P$ is not visible from another point $Q$, if there is a black point in between them; that is, if the open line-segment $\overline{PQ}$ contains a black point. Answer (with proof) the following questions!

  • Does there exists a line determined by two black points such that no black point of the line is visible from the origin?

  • Does there exist for any $k>0$ a square of size $k\times k$, such that no black point of the square is visible from the origin?
(Answering one of them values 7, answering both values 11 points.)

Problem nr. 4

Let $f_1,\ldots,f_{2n-1}:[a,b] \to \mathbb R$ be continuous concave functions assuming zero at both ends of the interval $[a,b]$. Suppose that the indexing of these functions is such that max$(f_1) \leq \ldots\leq$ max$(f_{2n-1})$. Prove that the inequality $$ \sum_{k=1}^n {\rm max}(f_k) \leq {\rm max}\left(\sum_{k=1}^{2n-1}f_k \right) $$ is automatically satisfied! (Proof regarding the $n=2$ case, only, values 7 points. Dealing with the $n\geq 2$ general case results in 2 more points - i.e. a total of 9 points.)

Problem nr. 5

Let $e$ and $f$ be two parallel lines of the plane and consider a finite number of line segments in between (i.e. with one end-point one $e$, the other one on $f$). Let $G$ be the graph whose vertices are these line segments and whose edges are formed by the intersecting pairs (i.e. those with a common point which is not their end-point). Prove that if $G$ contains no triangle, then $G$ is a bipartite graph and in general, if $G$ contains no clique of size bigger than $k$, then the vertices of $G$ can be colored with $k$ colors. (The general case values 11, the special case only values 7 points.)

Problem nr. 6

Two countries agreed to resolve a border issue by talk and have sent (each of them) a delegation of $n>2$ diplomats. For each diplomat, strict protocoll regulates the number of delegacy members from the other contry's contingent that he or she needs to shake hands with. This number is 1 for the shortest diplomats of each contingent, 2 for the next ones in tallness and so on; the only exception being both delagations' tallest diplomats, who need to shake hands with $n-1$, rather than with $n$ members of the other delegation. Give an explicit formula for the number $c_n$ of ways the regulations of the protocoll can be met! (9 points, if the formula is "fully explicit"; e.g. it allows us to read the value of $\lim_n \sqrt[n]{c_n}$. Less explicit - for example, one containing a summation over $n$ terms - expressions may value less points.)

Problem nr. 7

Let $K$ be a field of zero characteristic and $F\supset K$ a field extension of degree $d\lt \infty$. Consider $F$ as a vectorspace over $K$ and in this sense let $U, V \subset F$ be two $(d-1)$-dimensional subspaces. Show that there must exist an $r\in F$ such that $r U=V$. (10 points)

Problem nr. 8

Let $K$ be a convex flat figure (that is, a convex, compact set of the real plane with non-empty interior). Prove that there exists a triangle $\hat{T}$ such that $T\subset K\subset \hat{T}$ where $T$ is the smaller triangle whose vertices are the middle-points of the sides of $\hat{T}$. Find further a generalization of this satetment to arbitrary $d\geq 2$ dimensions (in which, in stead of triangles, a suitable $d$-dimensional polytope is used) and verify that it still holds. (10 points for the $d=2$ case and +1 point for the generalization.)

Problem nr. 9

Let $A_1,\ldots A_m$ be a collection of real, symmetric, $n\times n$ matrices such that $\sum_{k=1}^m A_k^2=I$. Decide if the equality $\sum_{k=1}^m A_k X A_k=X$ implies or not if the (real, $n\times n$) matrix $X$ commutes with each $A_k$! (Complete answer values 11 points; dealing with the case only when $X$ is an orthogonal projection values 7 points).

Problem nr. 10

Give a lower, $n$-dependent bound on $m$, for which the system of $m$ equations in $n$ unknowns $$ \sum_{k=1}^n x_k^{r_j} = s_j \;\;\;(j=1,\ldots,m) $$ allows at most one $x_1\geq\ldots\geq x_n\gt 0$ solution for arbitrary real parameters $s_1,\ldots,s_m \gt 0$ and $r_1\gt\ldots\gt r_m\gt 0$! (Showing $2n$ as a lower bound values 10 points; proving anything better than just $2n$ minus a constant values 13 points.)