Unofficial archive — problems, solutions & results © IMC, reproduced with permission.

Studolymp / IMC / 2007

IMC 2007
contestants 243 · problems 12 (6+6) · scale 0–20 · per-problem yes

Problems

Day 1

P1

Let ff be a polynomial of degree 2 with integer coefficients. Suppose that f(k)f(k) is divisible by 5 for every integer kk. Prove that all coefficients of ff are divisible by 5.

P2

Let n2n \ge 2 be an integer. What is the minimal and maximal possible rank of an n×nn \times n matrix whose n2n^2 entries are precisely the numbers 1,2,,n21, 2, \dots, n^2?

P3

Call a polynomial P(x1,,xk)P(x_1, \dots, x_k) good if there exist 2×22 \times 2 real matrices A1,,AkA_1, \dots, A_k such that P(x1,,xk)=det(i=1kxiAi).P(x_1, \dots, x_k) = \det \left( \sum_{i=1}^{k} x_i A_i \right). Find all values of kk for which all homogeneous polynomials with kk variables of degree 2 are good. (A polynomial is homogeneous if each term has the same total degree.)

P4

Let GG be a finite group. For arbitrary sets U,V,WGU, V, W \subset G, denote by NUVWN_{UVW} the number of triples (x,y,z)U×V×W(x, y, z) \in U \times V \times W for which xyzxyz is the unity.

Suppose that GG is partitioned into three sets AA, BB and CC (i.e. sets A,B,CA, B, C are pairwise disjoint and G=ABCG = A \cup B \cup C). Prove that NABC=NCBAN_{ABC} = N_{CBA}.

P5

Let nn be a positive integer and a1,,ana_1, \dots, a_n be arbitrary integers. Suppose that a function f:ZRf : \mathbb{Z} \to \mathbb{R} satisfies i=1nf(k+ai)=0\sum\limits_{i=1}^{n} f(k + a_i \ell) = 0 whenever kk and \ell are integers and 0\ell \ne 0. Prove that f=0f = 0.

P6

How many nonzero coefficients can a polynomial P(z)P(z) have if its coefficients are integers and P(z)2|P(z)| \le 2 for any complex number zz of unit length?

Day 2

P7

Let f:RRf : \mathbb{R} \to \mathbb{R} be a continuous function. Suppose that for any c>0c > 0, the graph of ff can be moved to the graph of cfcf using only a translation or a rotation. Does this imply that f(x)=ax+bf(x) = ax + b for some real numbers aa and bb?

P8

Let xx, yy, and zz be integers such that S=x4+y4+z4S = x^4 + y^4 + z^4 is divisible by 29. Show that SS is divisible by 29429^4.

P9

Let CC be a nonempty closed bounded subset of the real line and f:CCf : C \to C be a nondecreasing continuous function. Show that there exists a point pCp \in C such that f(p)=pf(p) = p.

(A set is closed if its complement is a union of open intervals. A function gg is nondecreasing if g(x)g(y)g(x) \le g(y) for all xyx \le y.)

P10

Let n>1n > 1 be an odd positive integer and A=(aij)i,j=1nA = (a_{ij})_{i,j = 1 \dots n} be the n×nn \times n matrix with aij={2if i=j1if ij±2(modn)0otherwise.a_{ij} = \begin{cases} 2 & \text{if } i = j \\ 1 & \text{if } i - j \equiv \pm 2 \pmod n \\ 0 & \text{otherwise.} \end{cases} Find detA\det A.

P11

For each positive integer kk, find the smallest number nkn_k for which there exist real nk×nkn_k \times n_k matrices A1,A2,,AkA_1, A_2, \dots, A_k such that all of the following conditions hold:

(1) A12=A22==Ak2=0A_1^2 = A_2^2 = \dots = A_k^2 = 0,

(2) AiAj=AjAiA_i A_j = A_j A_i for all 1i,jk1 \le i, j \le k, and

(3) A1A2Ak0A_1 A_2 \dots A_k \ne 0.

P12

Let f0f \ne 0 be a polynomial with real coefficients. Define the sequence f0,f1,f2,f_0, f_1, f_2, \dots of polynomials by f0=ff_0 = f and fn+1=fn+fnf_{n+1} = f_n + f_n' for every n0n \ge 0. Prove that there exists a number NN such that for every nNn \ge N, all roots of fnf_n are real.