IMO 1987 (XXVIII International Mathematical Olympiad)

Sum of k times permutations with k fixed points equals n!

Let $p_n(k)$ be the number of permutations of the set $\{1,\dots ,n\}$, $n\ge 1$, which have exactly $k$ fixed points. Prove that ${\sum }_{k=0}^{n}k\cdot p_n(k)=n!.$ (Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself. An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i)=i$.)

Topic: Combinatoria, Teoria dei Numeri Metodo: Doppio conteggio, Induzione Abilita: Conteggio sistematico, Manipolazione algebrica, Riconoscimento di pattern Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri Fonte: apri PDF p.1

Sum of k times permutations with k fixed points equals n!

Let $p_n(k)$ be the number of permutations of the set $\{1,\dots ,n\}$, $n\ge 1$, which have exactly $k$ fixed points. Prove that ${\sum }_{k=0}^{n}k\cdot p_n(k)=n!.$ (Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself. An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i)=i$.)

src_imho_1987__Q01

Quadrilateral AKNM and triangle ABC have equal areas

In an acute-angled triangle $ABC$ the interior bisector of the angle $A$ intersects $BC$ at $L$ and intersects the circumcircle of $ABC$ again at $N$. From point $L$ perpendiculars are drawn to $AB$ and $AC$, the feet of these perpendiculars being $K$ and $M$ respectively. Prove that the quadrilateral $AKNM$ and the triangle $ABC$ have equal areas.

Topic: Geometria piana Metodo: Trigonometria, Simmetria Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria Fonte: apri PDF p.1

Quadrilateral AKNM and triangle ABC have equal areas

In an acute-angled triangle $ABC$ the interior bisector of the angle $A$ intersects $BC$ at $L$ and intersects the circumcircle of $ABC$ again at $N$. From point $L$ perpendiculars are drawn to $AB$ and $AC$, the feet of these perpendiculars being $K$ and $M$ respectively. Prove that the quadrilateral $AKNM$ and the triangle $ABC$ have equal areas.

src_imho_1987__Q02

Approximating zero by integer linear combination with bounded coefficients

Let $x_1,x_2,\dots ,x_n$ be real numbers satisfying $x_1^2+x_2^2+\cdots +x_n^2=1$. Prove that for every integer $k\ge 2$ there are integers $a_1,a_2,\dots ,a_n$, not all $0$, such that $|a_i|\le k-1$ for all $i$ and $|a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n|\le \frac{(k-1)\sqrt{n}}{k^n-1}.$

Topic: Combinatoria, Teoria dei Numeri, Disuguaglianze Metodo: Principio dei cassetti, Disuguaglianze Abilita: Modellizzazione, Conteggio sistematico, Stima, Manipolazione algebrica Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri, Algebra e Analisi Fonte: apri PDF p.1

Approximating zero by integer linear combination with bounded coefficients

Let $x_1,x_2,\dots ,x_n$ be real numbers satisfying $x_1^2+x_2^2+\cdots +x_n^2=1$. Prove that for every integer $k\ge 2$ there are integers $a_1,a_2,\dots ,a_n$, not all $0$, such that $|a_i|\le k-1$ for all $i$ and $|a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n|\le \frac{(k-1)\sqrt{n}}{k^n-1}.$

src_imho_1987__Q03

No function on non-negative integers satisfies f(f(n))=n+1987

Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for every $n$.

Topic: Insiemi e funzioni, Teoria dei Numeri Metodo: Invarianti, Induzione Abilita: Ragionamento geometrico, Manipolazione algebrica, Riconoscimento di pattern, Astrazione Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF p.1

No function on non-negative integers satisfies f(f(n))=n+1987

Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for every $n$.

src_imho_1987__Q04

n points with all pairwise distances irrational but every triple rational-area triangle

Let $n$ be an integer greater than or equal to $3$. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

Topic: Geometria piana, Combinatoria Metodo: method_casework, Coordinate Abilita: Modellizzazione, Ragionamento geometrico, Conteggio sistematico, Riconoscimento di pattern Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

n points with all pairwise distances irrational but every triple rational-area triangle

Let $n$ be an integer greater than or equal to $3$. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

src_imho_1987__Q05

Primality of k^2+k+n for all k up to n-2 follows from small cases

Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le \sqrt{n/3}$, then $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le n-2$.

Topic: Teoria dei Numeri Metodo: Congruenze, Fattorizzazione, Casework Abilita: Manipolazione algebrica, Riconoscimento di pattern, Lettura attenta, Casework accurato Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF p.1

Primality of k^2+k+n for all k up to n-2 follows from small cases

Let $n$ be an integer greater than or equal to $2$. Prove that if $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le \sqrt{n/3}$, then $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le n-2$.

src_imho_1987__Q06