Difference between revisions of "2013 TSTST Problems"

(Created page with "==Day 1== ===Problem 1=== Let <math>ABC</math> be a triangle and <math>D</math>, <math>E</math>, <math>F</math> be the midpoints of arcs <math>BC</math>, <math>CA</math>, <mat...")
 
Line 7: Line 7:
 
===Problem 2===
 
===Problem 2===
  
A finite sequence of integers <math>a_1, a_2, \dots, a_n</math> is called regular if there exists a real number <math>x</math> satisfying<cmath> \left\lfloor kx \right\rfloor = a_k \quad \text{for } 1 \le k \le n. </cmath>Given a regular sequence <math>a_1, a_2, \dots, a_n</math>, for <math>1 \le k \le n</math> we say that the term <math>a_k</math> is forced if the following condition is satisfied: the sequence<cmath> a_1, a_2, \dots, a_{k-1}, b </cmath>is regular if and only if <math>b = a_k</math>. Find the maximum possible number of forced terms in a regular sequence with <math>1000</math> terms.
+
A finite sequence of integers <math>a_1, a_2, \dots, a_n</math> is called regular if there exists a real number <math>x</math> satisfying<cmath> \left\lfloor kx \right\rfloor = a_k \quad \text{for } 1 \le k \le n. </cmath>Given a regular sequence <math>a_1, a_2, \dots, a_n</math>, for <math>1 \le k \le n</math> we say that the term <math>a_k</math> is forced if the following condition is satisfied: the sequence<cmath> a_1, a_2, \dots, a_{k-1}, b </cmath>is regular if and only if <math>b = a_k</math>. Find the maximum possible number of forced terms in a regular sequence with <math>1000</math> terms.
 +
 
[[2013 TSTST Problems/Problem 2|Solution]]
 
[[2013 TSTST Problems/Problem 2|Solution]]
  
Line 13: Line 14:
  
 
Divide the plane into an infinite square grid by drawing all the lines <math>x=m</math> and <math>y=n</math> for <math>m,n \in \mathbb Z</math>. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly <math>1/4</math> of the squares are black and no two black squares are adjacent). Let <math>r</math> and <math>s</math> be odd integers, and let <math>(x,y)</math> be a point in the interior of any white square such that <math>rx-sy</math> is irrational. Shoot a laser out of this point with slope <math>r/s</math>; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.
 
Divide the plane into an infinite square grid by drawing all the lines <math>x=m</math> and <math>y=n</math> for <math>m,n \in \mathbb Z</math>. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly <math>1/4</math> of the squares are black and no two black squares are adjacent). Let <math>r</math> and <math>s</math> be odd integers, and let <math>(x,y)</math> be a point in the interior of any white square such that <math>rx-sy</math> is irrational. Shoot a laser out of this point with slope <math>r/s</math>; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.
 +
 
[[2013 TSTST Problems/Problem 3|Solution]]
 
[[2013 TSTST Problems/Problem 3|Solution]]
 
==Day 2==
 
==Day 2==
Line 32: Line 34:
 
for all <math>a,b,c \ge 2</math>.
 
for all <math>a,b,c \ge 2</math>.
 
(Here <math>f^1(n) = f(n)</math> and <math>f^k(n) = f(f^{k-1}(n))</math> for every integer <math>k</math> greater than <math>1</math>.)
 
(Here <math>f^1(n) = f(n)</math> and <math>f^k(n) = f(f^{k-1}(n))</math> for every integer <math>k</math> greater than <math>1</math>.)
 +
 
[[2013 TSTST Problems/Problem 6|Solution]]
 
[[2013 TSTST Problems/Problem 6|Solution]]
 
 
Line 39: Line 42:
 
(a) For all odd <math>n</math>, prove that <math>T_n</math> is divisible by <math>n</math>.
 
(a) For all odd <math>n</math>, prove that <math>T_n</math> is divisible by <math>n</math>.
 
(b) For all even <math>n</math>, prove that <math>T_n</math> is divisible by <math>n/2</math>.
 
(b) For all even <math>n</math>, prove that <math>T_n</math> is divisible by <math>n/2</math>.
 +
 
[[2013 TSTST Problems/Problem 7|Solution]]
 
[[2013 TSTST Problems/Problem 7|Solution]]
 
 
Line 44: Line 48:
  
 
Define a function <math>f: \mathbb N \to \mathbb N</math> by <math>f(1) = 1</math>, <math>f(n+1) = f(n) + 2^{f(n)}</math> for every positive integer <math>n</math>. Prove that <math>f(1), f(2), \dots, f(3^{2013})</math> leave distinct remainders when divided by <math>3^{2013}</math>.
 
Define a function <math>f: \mathbb N \to \mathbb N</math> by <math>f(1) = 1</math>, <math>f(n+1) = f(n) + 2^{f(n)}</math> for every positive integer <math>n</math>. Prove that <math>f(1), f(2), \dots, f(3^{2013})</math> leave distinct remainders when divided by <math>3^{2013}</math>.
 +
 
[[2013 TSTST Problems/Problem 8|Solution]]
 
[[2013 TSTST Problems/Problem 8|Solution]]
 
 
Line 49: Line 54:
  
 
Let <math>r</math> be a rational number in the interval <math>[-1,1]</math> and let <math>\theta = \cos^{-1} r</math>. Call a subset <math>S</math> of the plane good if <math>S</math> is unchanged upon rotation by <math>\theta</math> around any point of <math>S</math> (in both clockwise and counterclockwise directions). Determine all values of <math>r</math> satisfying the following property: The midpoint of any two points in a good set also lies in the set.
 
Let <math>r</math> be a rational number in the interval <math>[-1,1]</math> and let <math>\theta = \cos^{-1} r</math>. Call a subset <math>S</math> of the plane good if <math>S</math> is unchanged upon rotation by <math>\theta</math> around any point of <math>S</math> (in both clockwise and counterclockwise directions). Determine all values of <math>r</math> satisfying the following property: The midpoint of any two points in a good set also lies in the set.
 +
 
[[2013 TSTST Problems/Problem 9|Solution]]
 
[[2013 TSTST Problems/Problem 9|Solution]]

Revision as of 07:44, 24 February 2023

Day 1

Problem 1

Let $ABC$ be a triangle and $D$, $E$, $F$ be the midpoints of arcs $BC$, $CA$, $AB$ on the circumcircle. Line $\ell_a$ passes through the feet of the perpendiculars from $A$ to $DB$ and $DC$. Line $m_a$ passes through the feet of the perpendiculars from $D$ to $AB$ and $AC$. Let $A_1$ denote the intersection of lines $\ell_a$ and $m_a$. Define points $B_1$ and $C_1$ similarly. Prove that triangle $DEF$ and $A_1B_1C_1$ are similar to each other.

Solution

Problem 2

A finite sequence of integers $a_1, a_2, \dots, a_n$ is called regular if there exists a real number $x$ satisfying\[\left\lfloor kx \right\rfloor = a_k \quad \text{for } 1 \le k \le n.\]Given a regular sequence $a_1, a_2, \dots, a_n$, for $1 \le k \le n$ we say that the term $a_k$ is forced if the following condition is satisfied: the sequence\[a_1, a_2, \dots, a_{k-1}, b\]is regular if and only if $b = a_k$. Find the maximum possible number of forced terms in a regular sequence with $1000$ terms.

Solution

Problem 3

Divide the plane into an infinite square grid by drawing all the lines $x=m$ and $y=n$ for $m,n \in \mathbb Z$. Next, if a square's upper-right corner has both coordinates even, color it black; otherwise, color it white (in this way, exactly $1/4$ of the squares are black and no two black squares are adjacent). Let $r$ and $s$ be odd integers, and let $(x,y)$ be a point in the interior of any white square such that $rx-sy$ is irrational. Shoot a laser out of this point with slope $r/s$; lasers pass through white squares and reflect off black squares. Prove that the path of this laser will form a closed loop.

Solution

Day 2

Problem 4

Circle $\omega$, centered at $X$, is internally tangent to circle $\Omega$, centered at $Y$, at $T$. Let $P$ and $S$ be variable points on $\Omega$ and $\omega$, respectively, such that line $PS$ is tangent to $\omega$ (at $S$). Determine the locus of $O$ -- the circumcenter of triangle $PST$.

Solution

Problem 5

Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$.

Solution

Problem 6

Let $\mathbb N$ be the set of positive integers. Find all functions $f: \mathbb N \to \mathbb N$ that satisfy the equation \[f^{abc-a}(abc) + f^{abc-b}(abc) + f^{abc-c}(abc) = a + b + c\] for all $a,b,c \ge 2$. (Here $f^1(n) = f(n)$ and $f^k(n) = f(f^{k-1}(n))$ for every integer $k$ greater than $1$.)

Solution

Problem 7

A country has $n$ cities, labelled $1,2,3,\dots,n$. It wants to build exactly $n-1$ roads between certain pairs of cities so that every city is reachable from every other city via some sequence of roads. However, it is not permitted to put roads between pairs of cities that have labels differing by exactly $1$, and it is also not permitted to put a road between cities $1$ and $n$. Let $T_n$ be the total number of possible ways to build these roads. (a) For all odd $n$, prove that $T_n$ is divisible by $n$. (b) For all even $n$, prove that $T_n$ is divisible by $n/2$.

Solution

Problem 8

Define a function $f: \mathbb N \to \mathbb N$ by $f(1) = 1$, $f(n+1) = f(n) + 2^{f(n)}$ for every positive integer $n$. Prove that $f(1), f(2), \dots, f(3^{2013})$ leave distinct remainders when divided by $3^{2013}$.

Solution

Problem 9

Let $r$ be a rational number in the interval $[-1,1]$ and let $\theta = \cos^{-1} r$. Call a subset $S$ of the plane good if $S$ is unchanged upon rotation by $\theta$ around any point of $S$ (in both clockwise and counterclockwise directions). Determine all values of $r$ satisfying the following property: The midpoint of any two points in a good set also lies in the set.

Solution