Find all sets comprising of 4 natural numbers such that the product of any 3 numbers in the set leaves a remainder of 1 when divided by the remaining number.

Click for solution It is easy to prove $abcd|abc+abd+acd+cda+1$ So we get $f(a,b,c,d)=1/a+1/b+1/c+1/d+1/abcd$ is at least $1$. So from here we get that $min(a,b,c,d)=1,2,3,4$ and using that $f(a,b,c,d)$ is cecreasing on each variable, we may plug in $a=1,2,3,4$ and find possible values for the remaining numbers. This gives not too much hand work to check solutions.

An $n$ by $n$ grid, where every square contains a number, is called an $n$-code if the numbers in every row and column form an arithmetic progression. If it is sufficient to know the numbers in certain squares of an $n$-code to obtain the numbers in the entire grid, call these squares a key. a.) Find the smallest $s \in \mathbb{N}$ such that any $s$ squares in an $n-$code $(n \geq 4)$ form a key. b.) Find the smallest $t \in \mathbb{N}$ such that any $t$ squares along the diagonals of an $n$-code $(n \geq 4)$ form a key.

Click for solution a) in worst case scenario, you can first pcik n numbers on thesame line or column with which you cannot find the whole grid obviously. Then if you pick one more number outside that line you cal also find the column of that number using the number on that column from the line you already know. And now if you know a line and a column you know all the grid.This is simple to show: suppose we know the first and last column and take another cell which is on neither fo these -suppose we take cell 3,3. Let's denote by x the value in this cell. Already you can express the value of the cel 2,3 as a function of x (more precisely it's the arithmetic media of x and the value of cell 1,3). Now if you know cell 2,3 depending on x, you know the whole row number 2 depending on x since the last value on that row (the one corresponding to the last column) you already know, and it's a known number. Working the same you can express the cells of row 3 as functions of x. So, you know the cell 2,2 for example as a function of x, and the cell 3,2 as a function of x. Now knowing that cells (1,2 )(which you know as being a cell on row 1), (2,2) and (3,2) form an arithmetic progression you can determine x. This was you can find out the whole grid. b) if you know just 2 numbers on the diagonal, you can arbitrarelly choose a progression for the line corresponding to the first number, and then with that line and the second number you can complete the grid as shown for point a). So since in the beginning we chose the ration arbitrarlly it means we have an infinite number of solutions so thw numbers are not enough. But three are as if you know 3 numbers on the diagonals, you just take the cells at the intersection of their lines and columns, this means a 3 X 3 square in which if you form a system of equations having as nedeterminates the ratios on the columns corresponding to those 3 numbers let's say, you can solve and thus determine 3 columns of the grid which are enough to determine the whole n-code.

Find the smallest $n \in \mathbb{N}$ such that if any 5 vertices of a regular $n$-gon are colored red, there exists a line of symmetry $l$ of the $n$-gon such that every red point is reflected across $l$ to a non-red point.

Click for solution Call "sequence" the way the colored points appear, reverse the sequence, if we put the reversed sequence over the points of the n_agon starting anywhere, and it doesnt overlap the colored points, then we may reflect the n-agon by the line perpendicular to the midpoint of the line joining the starting points of the original sequence and the reversed one. So what we have is that there is a starting position for the reversed sequence that doesnt overlap our original sequence. Every point of our original sequence overlaps with $5$ reversed sequences, so we have at most $25$ overlaps, more over, every pair of points of the original sequence have a common overlap, so we have at most $25-10=15$ overlaped reversed sequences, so we get for $n>15$ a non overlaping reversed sequence! Now, number the vertices from $0$ to $14$ clockwise, and put colored points in vertex: $0,1,3,6,10$ it is easy to see the overlaping arguments gives equality here.

Given $5n$ real numbers $r_i, s_i, t_i, u_i, v_i \geq 1 (1 \leq i \leq n)$, let $R = \frac {1}{n} \sum_{i=1}^{n} r_i$, $S = \frac {1}{n} \sum_{i=1}^{n} s_i$, $T = \frac {1}{n} \sum_{i=1}^{n} t_i$, $U = \frac {1}{n} \sum_{i=1}^{n} u_i$, $V = \frac {1}{n} \sum_{i=1}^{n} v_i$. Prove that $\prod_{i=1}^{n}\frac {r_i s_i t_i u_i v_i + 1}{r_i s_i t_i u_i v_i - 1} \geq \left(\frac {RSTUV +1}{RSTUV - 1}\right)^n$.

Click for solution Let $X=(x_1,x_2,x_3,x_4,x_5)$, $F(X)=\ln \frac{x_1x_2x_3x_4x_5+1}{x_1x_2x_3x_4x_5-1}$. Then $F(x)$ is a convex function in a domain $(0,+\infty)^5$. For proving this, we must assure that Hessian $H(X)=(\partial^2 F/\partial x_i\partial x_j)_{i,j=1}^5$ is non-negative defined in every point $(x_1,x_2,x_3,x_4,x_5)$. We have $\partial^2 F/\partial x_i\partial x_j=\frac{2p(p^2+1)}{x_ix_j(p^2-1)^2}, i\ne j$ and $\partial^2 F/\partial x_i^2=\frac{4p^3}{x_i^2(p^2-1)^2}.$ (here $p=x_1x_2x_3x_4x_5$) So, we have to prove that the matrix with diagonal entries $2p^2$ and not-diagonal elements $p^2+1$ is not-negative defined (we multipled rows and columns by corresponding $x_i$ and then multiply by some constant). But it is clear: matrix with equal entries is non-negative defined, and our matrix differs from it by a positive scalar matrix. So, just apply Jensen for this function.

Given distinct prime numbers $p$ and $q$ and a natural number $n \geq 3$, find all $a \in \mathbb{Z}$ such that the polynomial $f(x) = x^n + ax^{n-1} + pq$ can be factored into 2 integral polynomials of degree at least 1.

Click for solution Generalization. Given two integers $ p$ and $ q$ and a natural number $ n \geq 3$ such that $ p$ is prime and $ q$ is squarefree, and such that $ p\nmid q$. Find all $ a \in \mathbb{Z}$ such that the polynomial $ f(x) = x^n + ax^{n - 1} + pq$ can be factored into 2 integral polynomials of degree at least 1. Solution. I hope the following solution is correct. It is more or less a straightforward generalization of IMO 1993 problem 1. The idea behind is an extension of Eisenstein's criterion for irreducible polynomials: Lemma 1. Let p be a prime number. If a polynomial $ A\left(x\right) = a_nx^n + a_{n - 1}x^{n - 1} + ... + a_1x + a_0$ with integer coefficients $ a_n$, $ a_{n - 1}$, ..., $ a_1$, $ a_0$ is reducible in $ \mathbb{Z}\left[x\right]$, and the prime p divides the coefficients $ a_0$, $ a_1$, ..., $ a_{n - 2}$, but does not divide $ a_n$, and $ p^2$ does not divide $ a_0$, then p does not divide $ a_{n - 1}$, and the polynomial A(x) must have a rational root. Proof of Lemma 1. Since the polynomial A(x) is reducible in $ \mathbb{Z}\left[x\right]$, we can write it in the form A(x) = B(x) C(x), where $ B\left(x\right) = b_ux^u + ... + b_1x + b_0$ and $ C\left(x\right) = c_vx^v + ... + c_1x + c_0$ are non-constant polynomials with integer coefficients $ b_u$, ..., $ b_1$, $ b_0$, $ c_v$, ..., $ c_1$, $ c_0$. Then, for any i, we have $ a_i = \sum_{k = 0}^i b_kc_{i - k}$ (this follows from multiplying out the equation A(x) = B(x) C(x)). Particularly, $ a_0 = b_0c_0$. But since the integer $ a_0$ is divisible by the prime p, but not by $ p^2$, this yields that one of the integers $ b_0$ and $ c_0$ is divisible by p, and the other one is not. WLOG assume that $ b_0$ is divisible by p, and $ c_0$ is not. Not all coefficients $ b_u$, ..., $ b_1$, $ b_0$ of the polynomial B(x) can be divisible by p (else, $ a_n = \sum_{k = 0}^n b_kc_{n - k}$ would also be divisible by p, what is excluded). Let $ \lambda$ be the least nonnegative integer such that the coefficient $ b_{\lambda}$ is not divisible by p. Then, all the integers $ b_k$ with $ k < \lambda$ are divisible by p. Hence, in the sum $ a_{\lambda} = \sum_{k = 0}^{\lambda} b_kc_{\lambda - k}$, all the summands $ b_kc_{\lambda - k}$ with $ k < \lambda$ are divisible by p, but the summand $ b_{\lambda}c_0$ (this is the summand for $ k = \lambda$) is not (since $ b_{\lambda}$ is not divisible by p, and neither is $ c_0$). Hence, the whole sum $ a_{\lambda}$ is not divisible by p. But we know that the coefficients $ a_0$, $ a_1$, ..., $ a_{n - 2}$ are all divisible by p; hence, $ a_{\lambda}$ must be one of the coefficients $ a_{n - 1}$ and $ a_n$. Thus, either $ \lambda = n - 1$ or $ \lambda = n$. If $ \lambda = n$, then it follows, since the integer $ b_{\lambda}$ is defined, that the polynomial B(x) has a coefficient $ b_n$. In other words, the polynomial B(x) has degree n. Since the polynomial A(x) has degree n, too, it follows from A(x) = B(x) C(x) that the polynomial C(x) is a constant. This is a contradiction. Thus, we must have $ \lambda = n - 1$. Hence, the integer $ a_{n - 1} = a_{\lambda}$ is not divisible by p. Also, since the integer $ b_{\lambda}$ is defined, it follows that the polynomial B(x) has a coefficient $ b_{n - 1}$. In other words, the polynomial B(x) has degree $ \geq n - 1$. Since the polynomial A(x) has degree n and A(x) = B(x) C(x), this yields that the polynomial C(x) has degree $ \leq 1$. The degree cannot be 0, since the polynomial C(x) is not constant; thus, the degree is 1. Hence, the polynomial A(x) has a linear factor, i. e. it has a rational root. Lemma 1 is proven. Now let us solve the problem: The number $ pq$ is squarefree (since $ p$ is prime and $ q$ is squarefree, and since $ p\nmid q$). Applying Lemma 1 to the polynomial $ x^n + ax^{n - 1} + pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root. If we denote this root by $ r$, then $ r^n + ar^{n - 1} + pq = 0$, so that $ pq = - r^n - ar^{n - 1} = - \left(r + a\right) r^{n - 1}$ is divisible by $ r^2$ (since $ n\geq 3$ yields $ n - 1\geq 2$, so that $ r^{n - 1}$ is divisible by $ r^2$), so that $ r = 1$ or $ r = - 1$ (since $ pq$ is squarefree), so that one of the numbers $ 1$ and $ - 1$ must be a root of the polynomial $ x^n + ax^{n - 1} + pq$. Hence, we see that, if the polynomial $ x^n + ax^{n - 1} + pq$ can be factored into two non-constant integral polynomials, then one of the numbers $ 1$ and $ - 1$ must be a root of this polynomial. Conversely, if one of the numbers $ 1$ and $ - 1$ is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers $ 1$ and $ - 1$ is a root of the polynomial $ x^n + ax^{n - 1} + pq$. But in fact, $ 1$ is a root of the polynomial $ x^n + ax^{n - 1} + pq$ if and only if $ 1^n + a\cdot 1^{n - 1} + pq = 0$, what is equivalent to $ 1 + a + pq = 0$, i. e. to $ a = - 1 - pq$, and $ - 1$ is a root of the polynomial $ x^n + ax^{n - 1} + pq$ if and only if $ \left( - 1\right)^n + a\cdot\left( - 1\right)^{n - 1} + pq = 0$, what is equivalent to $ a = 1 + \left( - 1\right)^n pq$. So, the two required values of $ a$ are $ a = - 1 - pq$ and $ a = 1 + \left( - 1\right)^n pq$. The problem is thus solved. Old version of the solution (of the original problem, not of the generalization). Applying Lemma 1 to the polynomial $ x^n + ax^{n - 1} + pq$, using the prime p, we see that, if this polynomial can be factored into two non-constant integral polynomials, then it must have a rational root. Since it is a monic polynomial with integer coefficients, it thus must have an integer root, and by a well-known theorem, this integer root then must be a divisor of pq. This means that the root is one of the numbers pq, p, q, 1, -pq, -p, -q, -1. Actually, none of the numbers pq, p, q, -pq, -p, -q can be a root of the polynomial $ x^n + ax^{n - 1} + pq$ (in fact, every of these numbers is divisible by p or by q, and if an integer root r of the polynomial $ x^n + ax^{n - 1} + pq$ would be divisible by p, then $ r^n + ar^{n - 1}$ would be divisible by $ p^{n - 1}$, while $ pq$ wouldn't be because of $ n\geq 3$, so $ r^n + ar^{n - 1} + pq$ couldn't be 0, what yields a contradiction, and similarly we obtain a contradiction if an integer root would be divisible by q). Hence, only 1 and -1 remain as possible candidates for integer roots of the polynomial $ x^n + ax^{n - 1} + pq$. Hence, we see that, if the polynomial $ x^n + ax^{n - 1} + pq$ can be factored into two non-constant integral polynomials, then one of the numbers 1 and -1 must be a root of this polynomial. Conversely, if one of the numbers 1 and -1 is a root of this polynomial, then it has an integer root and thus can be factored into two non-constant integral polynomials. Hence, in order to solve the problem, it remains to find all integers a such that one of the numbers 1 and -1 is a root of the polynomial $ x^n + ax^{n - 1} + pq$. But in fact, 1 is a root of the polynomial $ x^n + ax^{n - 1} + pq$ if and only if $ 1^n + a\cdot 1^{n - 1} + pq = 0$, what is equivalent to $ 1 + a + pq = 0$, i. e. to a = - 1 - pq, and -1 is a root of the polynomial $ x^n + ax^{n - 1} + pq$ if and only if $ \left( - 1\right)^n + a\cdot\left( - 1\right)^{n - 1} + pq = 0$, what is equivalent to $ a = 1 + \left( - 1\right)^n pq$. So, the two required values of a are a = - 1 - pq and $ a = 1 + \left( - 1\right)^n pq$. Darij

For any 2 convex polygons $S$ and $T$, if all the vertices of $S$ are vertices of $T$, call $S$ a sub-polygon of $T$. I. Prove that for an odd number $n \geq 5$, there exists $m$ sub-polygons of a convex $n$-gon such that they do not share any edges, and every edge and diagonal of the $n$-gon are edges of the $m$ sub-polygons. II. Find the smallest possible value of $m$.