Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 EGMO Problems"

(Created page with "==Day 1== ===Problem 1=== Let <math>ABC</math> be a triangle with <math>CA=CB</math> and <math>\angle{ACB}=120^\circ</math>, and let <math>M</math> be the midpoint of <math>AB...")
 
(→‎Problem 6)
 
(2 intermediate revisions by the same user not shown)
Line 10: Line 10:
 
<cmath>A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.</cmath>
 
<cmath>A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.</cmath>
  
−
[list=a]
+
(a) Prove that every integer <math>x \geq 2</math> can be written as the product of one or more elements of <math>A</math>, which are not necessarily different.
−
[*]Prove that every integer <math>x \geq 2</math> can be written as the product of one or more elements of <math>A</math>, which are not necessarily different.
 
  
−
[*]For every integer <math>x \geq 2</math> let <math>f(x)</math> denote the minimum integer such that <math>x</math> can be written as the
+
(b) For every integer <math>x \geq 2</math> let <math>f(x)</math> denote the minimum integer such that <math>x</math> can be written as the
 
product of <math>f(x)</math> elements of <math>A</math>, which are not necessarily different.
 
product of <math>f(x)</math> elements of <math>A</math>, which are not necessarily different.
 +
 
Prove that there exist infinitely many pairs <math>(x,y)</math> of integers with <math>x\geq 2</math>, <math>y \geq 2</math>, and <cmath>f(xy)<f(x)+f(y).</cmath> (Pairs <math>(x_1,y_1)</math> and <math>(x_2,y_2)</math> are different if <math>x_1 \neq x_2</math> or <math>y_1 \neq y_2</math>).
 
Prove that there exist infinitely many pairs <math>(x,y)</math> of integers with <math>x\geq 2</math>, <math>y \geq 2</math>, and <cmath>f(xy)<f(x)+f(y).</cmath> (Pairs <math>(x_1,y_1)</math> and <math>(x_2,y_2)</math> are different if <math>x_1 \neq x_2</math> or <math>y_1 \neq y_2</math>).
 
[/list]
 
[/list]
Line 22: Line 22:
 
===Problem 3===
 
===Problem 3===
 
The <math>n</math> contestant of EGMO are named <math>C_1, C_2, \cdots C_n</math>. After the competition, they queue in front of the restaurant according to the following rules.
 
The <math>n</math> contestant of EGMO are named <math>C_1, C_2, \cdots C_n</math>. After the competition, they queue in front of the restaurant according to the following rules.
−
[list]
+
 
−
[*]The Jury chooses the initial order of the contestants in the queue.
+
(i) The Jury chooses the initial order of the contestants in the queue.
−
[*]Every minute, the Jury chooses an integer <math>i</math> with <math>1 \leq i \leq n</math>.
+
 
−
[list]
+
(ii) Every minute, the Jury chooses an integer <math>i</math> with <math>1 \leq i \leq n</math>.
−
[*]If contestant <math>C_i</math> has at least <math>i</math> other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly <math>i</math> positions.
+
 
−
[*]If contestant <math>C_i</math> has fewer than <math>i</math> other contestants in front of her, the restaurant opens and process ends.
+
(iii) If contestant <math>C_i</math> has at least <math>i</math> other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly <math>i</math> positions.
−
[/list]
+
 
−
[/list]
+
(iv) If contestant <math>C_i</math> has fewer than <math>i</math> other contestants in front of her, the restaurant opens and process ends.
−
[list=a]
+
 
−
[*]Prove that the process cannot continue indefinitely, regardless of the Jury’s choices.
+
(a) Prove that the process cannot continue indefinitely, regardless of the Jury’s choices.
−
[*]Determine for every <math>n</math> the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.
+
 
−
[/list]
+
(b) Determine for every <math>n</math> the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.
  
 
[[2018 EGMO Problems/Problem 3|Solution]]
 
[[2018 EGMO Problems/Problem 3|Solution]]
 +
 
==Day 2==
 
==Day 2==
 
===Problem 4===
 
===Problem 4===
Line 50: Line 51:
  
 
===Problem 6===
 
===Problem 6===
−
[list=a]
+
(a) Prove that for every real number <math>t</math> such that <math>0 < t < \tfrac{1}{2}</math> there exists a positive integer <math>n</math> with the following property: for every set <math>S</math> of <math>n</math> positive integers there exist two different elements <math>x</math> and <math>y</math> of <math>S</math>, and a non-negative integer <math>m</math> (i.e. <math>m \ge 0 </math>), such that <cmath> |x-my|\leq ty.</cmath>
−
[*]Prove that for every real number <math>t</math> such that <math>0 < t < \tfrac{1}{2}</math> there exists a positive integer <math>n</math> with the following property: for every set <math>S</math> of <math>n</math> positive integers there exist two different elements <math>x</math> and <math>y</math> of <math>S</math>, and a non-negative integer <math>m</math> (i.e. <math>m \ge 0 </math>), such that <cmath> |x-my|\leq ty.</cmath>
+
 
−
[*]Determine whether for every real number <math>t</math> such that <math>0 < t < \tfrac{1}{2} </math> there exists an infinite set <math>S</math> of positive integers such that <cmath>|x-my| > ty</cmath> for every pair of different elements <math>x</math> and <math>y</math> of <math>S</math> and every positive integer <math>m</math> (i.e. <math>m > 0</math>).
+
(b) Determine whether for every real number <math>t</math> such that <math>0 < t < \tfrac{1}{2} </math> there exists an infinite set <math>S</math> of positive integers such that <cmath>|x-my| > ty</cmath> for every pair of different elements <math>x</math> and <math>y</math> of <math>S</math> and every positive integer <math>m</math> (i.e. <math>m > 0</math>).
  
 
[[2018 EGMO Problems/Problem 6|Solution]]
 
[[2018 EGMO Problems/Problem 6|Solution]]

Latest revision as of 13:02, 24 December 2022

Day 1

Problem 1

Let $ABC$ be a triangle with $CA=CB$ and $\angle{ACB}=120^\circ$, and let $M$ be the midpoint of $AB$. Let $P$ be a variable point of the circumcircle of $ABC$, and let $Q$ be the point on the segment $CP$ such that $QP = 2QC$. It is given that the line through $P$ and perpendicular to $AB$ intersects the line $MQ$ at a unique point $N$. Prove that there exists a fixed circle such that $N$ lies on this circle for all possible positions of $P$.

Solution

Problem 2

Consider the set \[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\]

(a) Prove that every integer $x \geq 2$ can be written as the product of one or more elements of $A$, which are not necessarily different.

(b) For every integer $x \geq 2$ let $f(x)$ denote the minimum integer such that $x$ can be written as the product of $f(x)$ elements of $A$, which are not necessarily different.

Prove that there exist infinitely many pairs $(x,y)$ of integers with $x\geq 2$, $y \geq 2$, and \[f(xy)<f(x)+f(y).\] (Pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if $x_1 \neq x_2$ or $y_1 \neq y_2$). [/list]

Solution

Problem 3

The $n$ contestant of EGMO are named $C_1, C_2, \cdots C_n$. After the competition, they queue in front of the restaurant according to the following rules.

(i) The Jury chooses the initial order of the contestants in the queue.

(ii) Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.

(iii) If contestant $C_i$ has at least $i$ other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.

(iv) If contestant $C_i$ has fewer than $i$ other contestants in front of her, the restaurant opens and process ends.

(a) Prove that the process cannot continue indefinitely, regardless of the Jury’s choices.

(b) Determine for every $n$ the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.

Solution

Day 2

Problem 4

A domino is a $1 \times 2$ or $2 \times 1$ tile. Let $n \ge 3$ be an integer. Dominoes are placed on an $n \times n$ board in such a way that each domino covers exactly two cells of the board, and dominoes do not overlap. The value of a row or column is the number of dominoes that cover at least one cell of this row or column. The configuration is called balanced if there exists some $k \ge 1$ such that each row and each column has a value of $k$. Prove that a balanced configuration exists for every $n \ge 3$, and find the minimum number of dominoes needed in such a configuration.

Solution

Problem 5

Let $\Gamma$ be the circumcircle of triangle $ABC$. A circle $\Omega$ is tangent to the line segment $AB$ and is tangent to $\Gamma$ at a point lying on the same side of the line $AB$ as $C$. The angle bisector of $\angle BCA$ intersects $\Omega$ at two different points $P$ and $Q$. Prove that $\angle ABP = \angle QBC$.

Solution

Problem 6

(a) Prove that for every real number $t$ such that $0 < t < \tfrac{1}{2}$ there exists a positive integer $n$ with the following property: for every set $S$ of $n$ positive integers there exist two different elements $x$ and $y$ of $S$, and a non-negative integer $m$ (i.e. $m \ge 0$), such that \[|x-my|\leq ty.\]

(b) Determine whether for every real number $t$ such that $0 < t < \tfrac{1}{2}$ there exists an infinite set $S$ of positive integers such that \[|x-my| > ty\] for every pair of different elements $x$ and $y$ of $S$ and every positive integer $m$ (i.e. $m > 0$).

Solution

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_EGMO_Problems&oldid=184647"