Japan Mathematical Olympiad 2005 — Honsen (Final)

Flipping 5-in-a-row coins on 17x17 grid to all tails

Coins, each with a distinguishable head (front) and tail (back), are arranged in a $17\times 17$ square array, all placed heads up. In one operation, one simultaneously flips $5$ consecutive coins in a column, $5$ consecutive coins in a row, or $5$ consecutive coins along a diagonal. By repeating this operation some number of times, is it possible to reach the state in which all coins are tails up?

Topic: Combinatoria Metodo: Invarianti, Colorazione Abilita: Astrazione, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Flipping 5 in a row monete sulla griglia 17x17 a tutte le code

Le monete, ciascuna con una testa (front) e una coda (back) distinguibili, sono disposte in una matrice quadrata $17\times 17$, tutte posizionate a testa in su. In un’operazione, si lanciano contemporaneamente monete consecutive $5$ in una colonna, monete consecutive $5$ in una riga o monete consecutive $5$ lungo una diagonale. Ripetendo questa operazione un certo numero di volte, è possibile raggiungere lo stato in cui tutte le monete sono in coda?

src_jmo15mq_honsen__Q01

Lattice points on segments of a periodic integer polynomial orbit are constant

Let $P(x,y)$ and $Q(x,y)$ be two-variable polynomials with integer coefficients, and let $a_0,b_0$ be integers. Define sequences $a_n,b_n$ by $a_{n+1}=P(a_n,b_n),b_{n+1}=Q(a_n,b_n)(n=0,1,2,\dots ).$ Suppose that $(a_1,b_1)\ne (a_0,b_0)$ but there exists a positive integer $k$ with $(a_k,b_k)=(a_0,b_0)$. Prove that the number of points in the plane lying on the segment whose endpoints are $(a_n,b_n)$ and $(a_{n+1},b_{n+1})$ and having both $x$-coordinate and $y$-coordinate integers does not depend on $n$.

Topic: Teoria dei Numeri, Geometria analitica, Algebra Metodo: Congruenze Abilita: Astrazione, Manipolazione algebrica Area: Aritmetica e Teoria dei Numeri, Geometria, Algebra e Analisi Fonte: apri PDF

I punti di lattice su segmenti di un’orbita polinomica intera periodica sono costanti

Lasciate che $P(x,y)$ e $Q(x,y)$ siano polinomi a due variabili con coefficienti interi, e lasciate che $a_0,b_0$ siano interi. Definire le sequenze $a_n,b_n$ da $a_{n+1}=P(a_n,b_n),b_{n+1}=Q(a_n,b_n)(n=0,1,2,\dots ).$ Supponiamo che $(a_1,b_1)\ne (a_0,b_0)$ ma esiste un intero positivo $k$ con $(a_k,b_k)=(a_0,b_0)$. Dimostrare che il numero di punti del piano che si trovano sul segmento i cui punti terminali sono $(a_n,b_n)$ e $(a_{n+1},b_{n+1})$ e che hanno entrambi i numeri interi $x$ e $y$ non dipende da $n$.

src_jmo15mq_honsen__Q02

Cube-root inequality for positive reals summing to 1

Let $a,b,c$ be positive real numbers satisfying $a+b+c=1$. Prove that $a\sqrt[3]{1+b-c}+b\sqrt[3]{1+c-a}+c\sqrt[3]{1+a-b}\le 1.$

Topic: Disuguaglianze Metodo: Disuguaglianze Abilita: Manipolazione algebrica, Stima Area: Algebra e Analisi Fonte: apri PDF

*Ineguaglianza a radice cubica per i valori reali positivi che sommano a 1 *

$a,b,c$ siano numeri reali positivi che soddisfino $a+b+c=1$. Provare che $a\sqrt[3]{1+b-c}+b\sqrt[3]{1+c-a}+c\sqrt[3]{1+a-b}\le 1.$

src_jmo15mq_honsen__Q03

Concyclicity of X, F, G, H from tangents and a secant of a circle

Let $A,B$ be two points on a circle $\Gamma$. The tangent to $\Gamma$ at $A$ and the tangent to $\Gamma$ at $B$ meet at a point $X$. Let $C,D$ be two points on $\Gamma$ such that $C,D,X$ lie on a line in this order. Suppose line $CA$ and line $BD$ meet perpendicularly at a point $F$. Let $G$ be the intersection of $CD$ and $AB$, and let $H$ be the intersection of the perpendicular bisector of $GX$ with $BD$. Prove that the four points $X,F,G,H$ lie on one circle.

Topic: Geometria piana Abilita: Ragionamento geometrico Area: Geometria Fonte: apri PDF

Conciclicità di X, F, G, H da tangenti e da una sezione di un cerchio

$A,B$ siano due punti su un cerchio $\Gamma$. La tangente di $\Gamma$ a $A$ e la tangente di $\Gamma$ a $B$ si incontrano a un punto $X$. $C,D$ siano due punti su $\Gamma$ in modo tale che $C,D,X$ si trovi su una linea in questo ordine. Supponiamo che la linea $CA$ e la linea $BD$ si incontrino perpendicolare a un punto $F$. Il $G$ è l’intersezione di $CD$ e $AB$, e $H$ è l’intersezione del bisettore perpendicolare di $GX$ con $BD$. Provare che i quattro punti $X,F,G,H$ si trovano su un cerchio.

src_jmo15mq_honsen__Q04

Existence of an envy-free assignment that is not dominated by another

There are $10$ subordinates and $10$ jobs. For each subordinate and each job, two real numbers, called that subordinate’s enthusiasm and ability for that job, are fixed. As the section chief, you wish to assign exactly one job to each subordinate. Suppose subordinate $A$ has higher enthusiasm for job $v$ than for job $u$, and moreover $A$ has higher ability for job $v$ than subordinate $B$ does; then, if you assign $u$ to $A$ and $v$ to $B$, subordinate $A$ becomes dissatisfied. Also, if by using an assignment different from yours it is possible to make every job be given to a person with higher ability for it (than in your assignment), then you are scolded by the company president. Prove that there exists an assignment under which no subordinate is dissatisfied and you are not scolded by the president.

Topic: Combinatoria, Logica Metodo: Estremalità Abilita: Modellizzazione, Astrazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Esistenza di un incarico senza invidia che non è dominato da un altro

Ci sono $10$ subordinati e $10$ posti di lavoro. Per ogni subordinato e per ogni lavoro, due numeri reali, chiamati entusiasmo e capacità di quel subordinato per quel lavoro, sono fissati. Come capo di sezione, lei vuole assegnare esattamente un lavoro a ogni subordinato. Supponiamo che il subordinato $A$ abbia un maggiore entusiasmo per il lavoro $v$ rispetto al lavoro $u$, e inoltre $A$ abbia una maggiore capacità per il lavoro $v$ rispetto al subordinato $B$; quindi, se assegnate $u$ a $A$ e $v$ a $B$, il subordinato $A$ diventa insoddisfatto. Inoltre, se utilizzando un incarico diverso dal tuo è possibile fare in modo che ogni lavoro venga dato a una persona con una maggiore capacità per esso (come nel tuo incarico), allora sei rimproverato dal presidente dell’azienda. Dimostrare che esiste un incarico in cui nessun subordinato è insoddisfatto e che il presidente non ti rimprovera.

src_jmo15mq_honsen__Q05