Olympiad problems

2013 Online Math Open Problems, 20

Let $a_1,a_2,\ldots, a_{2013}$ be a permutation of the numbers from $1$ to $2013$. Let $A_n = \frac{a_1 + a_2 + \cdots + a_n} {n}$ for $n = 1,2,\ldots, 2013$. If the smallest possible difference between the largest and smallest values of $A_1,A_2,\ldots, A_{2013}$ is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers, find $m+n$. [i]Ray Li[/i]

2013 AIME Problems, 14

Tags: trig identities , number theory , relatively prime , geometric series , quadratic , ratio , trigonometry

For $\pi\leq\theta<2\pi$, let \[ P=\dfrac12\cos\theta-\dfrac14\sin2\theta-\dfrac18\cos3\theta+\dfrac1{16}\sin4\theta+\dfrac1{32}\cos5\theta-\dfrac1{64}\sin6\theta-\dfrac1{128}\cos7\theta+\ldots \] and \[ Q=1-\dfrac12\sin\theta-\dfrac14\cos2\theta+\dfrac1{8}\sin3\theta+\dfrac1{16}\cos4\theta-\dfrac1{32}\sin5\theta-\dfrac1{64}\cos6\theta+\dfrac1{128}\sin7\theta +\ldots \] so that $\tfrac PQ = \tfrac{2\sqrt2}7$. Then $\sin\theta = -\tfrac mn$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

2005 Germany Team Selection Test, 1

Tags: quadratic , sequence , relatively prime , number theory

Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$. [i]Proposed by Jaroslaw Wroblewski, Poland[/i]

1998 AIME Problems, 4

Tags: relatively prime , probability , number theory

Nine tiles are numbered $1, 2, 3, \ldots, 9,$ respectively. Each of three players randomly selects and keeps three of the tile, and sums those three values. The probability that all three players obtain an odd sum is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

2010 Contests, 3

Tags: number theory , least common multiple , relatively prime

The sum $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}=\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

2013 NIMO Summer Contest, 2

Tags: number theory , relatively prime

If $\frac{2+4+6}{1+3+5}-\frac{1+3+5}{2+4+6} = \frac{m}{n}$ for relatively prime integers $m$ and $n$, compute $100m+n$. [i]Proposed by Evan Chen[/i]

2019 AIME Problems, 2

Tags: number theory , relatively prime

Jenn randomly chooses a number $J$ from $1, 2, 3,\ldots, 19, 20$. Bela then randomly chooses a number $B$ from $1, 2, 3,\ldots, 19, 20$ distinct from $J$. The value of $B - J$ is at least $2$ with a probability that can be expressed in the form $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

2016 Azerbaijan IMO TST First Round, 1

Tags: prime number , relatively prime , number theory

Find the maximum value of natural components of number $96$ that we can seperate such that all of them must be relatively prime number withh each other.

2014 Online Math Open Problems, 8

Tags: probability , number theory , relatively prime

Let $a$ and $b$ be randomly selected three-digit integers and suppose $a > b$. We say that $a$ is [i]clearly bigger[/i] than $b$ if each digit of $a$ is larger than the corresponding digit of $b$. If the probability that $a$ is clearly bigger than $b$ is $\tfrac mn$, where $m$ and $n$ are relatively prime integers, compute $m+n$. [i]Proposed by Evan Chen[/i]

2013 AIME Problems, 12

Tags: trigonometry , geometry , relatively prime , number theory , area of a triangle

Let $\triangle PQR$ be a triangle with $\angle P = 75^\circ$ and $\angle Q = 60^\circ$. A regular hexagon $ABCDEF$ with side length 1 is drawn inside $\triangle PQR$ so that side $\overline{AB}$ lies on $\overline{PQ}$, side $\overline{CD}$ lies on $\overline{QR}$, and one of the remaining vertices lies on $\overline{RP}$. There are positive integers $a$, $b$, $c$, and $d$ such that the area of $\triangle PQR$ can be expressed in the form $\tfrac{a+b\sqrt c}d$, where $a$ and $d$ are relatively prime and $c$ is not divisible by the square of any prime. Find $a+b+c+d$.

2012 Purple Comet Problems, 6

Tags: number theory , ratio , relatively prime

Volume $A$ equals one fourth of the sum of the volumes $B$ and $C$, while volume $B$ equals one sixth of the sum of the volumes $A$ and $C$. There are relatively prime positive integers $m$ and $n$ so that the ratio of volume $C$ to the sum of the other two volumes is $\frac{m}{n}$. Find $m+n$.

2014 Purple Comet Problems, 14

Tags: probability , relatively prime , number theory

Steve needed to address a letter to $2743$ Becker Road. He remembered the digits of the address, but he forgot the correct order of the digits, so he wrote them down in random order. The probability that Steve got exactly two of the four digits in their correct positions is $\tfrac m n$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

2018 Mexico National Olympiad, 3

Tags: number theory , relatively prime

A sequence $a_2, a_3, \dots, a_n$ of positive integers is said to be [i]campechana[/i], if for each $i$ such that $2 \leq i \leq n$ it holds that exactly $a_i$ terms of the sequence are relatively prime to $i$. We say that the [i]size[/i] of such a sequence is $n - 1$. Let $m = p_1p_2 \dots p_k$, where $p_1, p_2, \dots, p_k$ are pairwise distinct primes and $k \geq 2$. Show that there exist at least two different campechana sequences of size $m$.

2005 Taiwan TST Round 2, 3

Tags: quadratic , sequence , relatively prime , number theory

Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$. [i]Proposed by Jaroslaw Wroblewski, Poland[/i]

2021 Saint Petersburg Mathematical Olympiad, 7

Tags: number theory , relatively prime

Kolya found several pairwise relatively prime integers, each of which is less than the square of any other. Prove that the sum of reciprocals of these numbers is less than $2$.

2021 Math Prize for Girls Problems, 11

Tags: number theory , relatively prime

Say that a sequence $a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$, $a_7$, $a_8$ is [i]cool[/i] if * the sequence contains each of the integers 1 through 8 exactly once, and * every pair of consecutive terms in the sequence are relatively prime. In other words, $a_1$ and $a_2$ are relatively prime, $a_2$ and $a_3$ are relatively prime, $\ldots$, and $a_7$ and $a_8$ are relatively prime. How many cool sequences are there?

1998 Kurschak Competition, 1

Tags: number theory , relatively prime

Is there an infinite sequence of positive integers where no two terms are relatively prime, no term divides any other term, and there is no integer larger than $1$ that divides every term of the sequence?

2012 Purple Comet Problems, 21

Tags: number theory , probability , relatively prime

Each time you click a toggle switch, the switch either turns from [i]off[/i] to [i]on[/i] or from [i]on[/i] to [i]off[/i]. Suppose that you start with three toggle switches with one of them [i]on[/i] and two of them [i]off[/i]. On each move you randomly select one of the three switches and click it. Let $m$ and $n$ be relatively prime positive integers so that $\frac{m}{n}$ is the probability that after four such clicks, one switch will be [i]on[/i] and two of them will be [i]off[/i]. Find $m+n$.

1999 AIME Problems, 13

Tags: logarithm , number theory , probability , relatively prime

Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $50 \%$ chance of winning any game it plays. The probability that no two teams win the same number of games is $m/n,$ where $m$ and $n$ are relatively prime positive integers. Find $\log_2 n.$

2011 Iran Team Selection Test, 4

Tags: number theory , relatively prime

Define a finite set $A$ to be 'good' if it satisfies the following conditions: [list][*][b](a)[/b] For every three disjoint element of $A,$ like $a,b,c$ we have $\gcd(a,b,c)=1;$ [*][b](b)[/b] For every two distinct $b,c\in A,$ there exists an $a\in A,$ distinct from $b,c$ such that $bc$ is divisible by $a.$[/list] Find all good sets.

2018 PUMaC Live Round, 7.2

Tags: number theory , relatively prime

Compute the smallest positive integer $n$ that is a multiple of $29$ with the property that for every positive integer that is relatively prime to $n$, $k^{n}\equiv 1\pmod{n}.$

2016 India National Olympiad, P6

Tags: number theory , relatively prime , arithmetic sequence

Consider a nonconstant arithmetic progression $a_1, a_2,\cdots, a_n,\cdots$. Suppose there exist relatively prime positive integers $p>1$ and $q>1$ such that $a_1^2, a_{p+1}^2$ and $a_{q+1}^2$ are also the terms of the same arithmetic progression. Prove that the terms of the arithmetic progression are all integers.

2002 Manhattan Mathematical Olympiad, 1

Tags: relatively prime , prime number , number theory

Famous French mathematician Pierre Fermat believed that all numbers of the form $F_n = 2^{2^n} + 1$ are prime for all non-negative integers $n$. Indeed, one can check that $F_0 = 3$, $F_1 = 5$, $F_2 = 17$, $F_3 = 257$ are all prime. a) Prove that $F_5$ is divisible by $641$. (Hence Fermat was wrong.) b) Prove that if $k \ne n$ then $F_k$ and $F_n$ are relatively prime (i.e. they do not have any common divisor except $1$) (Notice: using b) one can prove that there are infinitely many prime numbers)

2005 USAMO, 1

Tags: induction , relatively prime , number theory , divisor , arrangement , prime number , combinatorics

Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

2007 Pre-Preparation Course Examination, 14

Tags: inequalities , relatively prime , symmetry , number theory

Find all $a,b,c \in \mathbb{N}$ such that \[a^2b|a^3+b^3+c^3,\qquad b^2c|a^3+b^3+c^3, \qquad c^2a|a^3+b^3+c^3.\] [PS: The original problem was this: Find all $a,b,c \in \mathbb{N}$ such that \[a^2b|a^3+b^3+c^3,\qquad b^2c|a^3+b^3+c^3, \qquad \color{red}{c^2b}|a^3+b^3+c^3.\] But I think the author meant $c^2a|a^3+b^3+c^3$, just because of symmetry]