Found problems: 698
Let $ k > 1$ be an integer, and consider the in finite array given by the integer lattice in the first quadrant of the plane, filled with real numbers. The array is said to be constant if all its elements are equal in value. The array is said to be $ k$-balanced if it is non-constant, and the sums of the elements of any $ k\times k$ sub-square have a constant value $ v_k$. An array which is both $ p$-balanced and $ q$-balanced will be said to be $ (p, q)$-balanced, or just doubly-balanced, if there is no confusion as to which $ p$ and $ q$ are meant. If $p, q$ are relatively prime, the array is said to be co-prime. We will call $ (M\times N)$-seed a $ M \times N$ array, anchored with its lower left corner in the origin of the plane, which extended through periodicity in both dimensions in the plane results into a $ (p, q)$-balanced array; more precisely, if we denote the numbers in the array by $ a_{ij}$ , where $ i, j$ are the coordinates of the lower left corner of the unit square they lie in, we have, for all non-negative integers $ i, j$
\[ a_{i \plus{} M,j} \equal{} a_{i,j} \equal{} a_{i,j \plus{} N}\]
(a) Prove that $ q^2v_p \equal{} p^2v_q$ for a $ (p, q)$-balanced array.
(b) Prove that more than two different values are used in a co-prime $ (p,q)$-balanced array. Show that this is no longer true if $ (p, q) > 1$.
(c) Prove that any co-prime $ (p, q)$-balanced array originates from a seed.
(d) Show there exist $ (p, q)$-balanced arrays (using only three different values) for arbitrary values $ p, q$.
(e) Show that neither a $ k$-balanced array, nor a $ (p, q)$-balanced array if $ (p, q) > 1$, need originate from a seed.
(f) Determine the minimal possible value $ T$ for a square $ (T\times T)$-seed resulting in a co-prime $ (p, q)$-balanced array, when $p,q$ are both prime.
(g) Show that for any relatively prime $ p, q$ there must exist a co-prime $ (p, q)$-balanced array originating from a square $ (T\times T)$-seed, with no lesser $ (M\times N)$-seed available ($ M\leq T, N\leq T$ and $MN< T^2$).
[i]Dan Schwarz[/i]
Find all natural numbers $n < 1978$ with the following property: If $m$ is a natural number, $1 < m < n$, and $(m, n) = 1$ (i.e., $m$ and $n$ are relatively prime), then $m$ is a prime number.
An integer $x$ is selected at random between 1 and $2011!$ inclusive. The probability that $x^x - 1$ is divisible by $2011$ can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$.
[i]Author: Alex Zhu[/i]
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?
Erick stands in the square in the 2nd row and 2nd column of a 5 by 5 chessboard. There are \$1 bills in the top left and bottom right squares, and there are \$5 bills in the top right and bottom left squares, as shown below.
\[\begin{tabular}{|p{1em}|p{1em}|p{1em}|p{1em}|p{1em}|}
\hline
\$1 & & & & \$5 \\
\hline
& E & & &\\
\hline
& & & &\\
\hline
& & & &\\
\hline
\$5 & & & & \$1 \\
\hline \end{tabular}\]
Every second, Erick randomly chooses a square adjacent to the one he currently stands in (that is, a square sharing an edge with the one he currently stands in) and moves to that square. When Erick reaches a square with money on it, he takes it and quits. The expected value of Erick's winnings in dollars is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
The following sequence lists all the positive rational numbers that do not exceed $\frac12$ by first listing the fraction with denominator 2, followed by the one with denominator 3, followed by the two fractions with denominator 4 in increasing order, and so forth so that the sequence is
\[
\frac12,\frac13,\frac14,\frac24,\frac15,\frac25,\frac16,\frac26,\frac36,\frac17,\frac27,\frac37,\cdots.
\]
Let $m$ and $n$ be relatively prime positive integers so that the $2012^{\text{th}}$ fraction in the list is equal to $\frac{m}{n}$. Find $m+n$.
Ten identical crates each of dimensions $ 3$ ft $ \times$ $ 4$ ft $ \times$ $ 6$ ft. The first crate is placed flat on the floor. Each of the remaining nine crates is placed, in turn, flat on top of the previous crate, and the orientation of each crate is chosen at random. Let $ \frac{m}{n}$ be the probability that the stack of crates is exactly $ 41$ ft tall, where $ m$ and $ n$ are relatively prime positive integers. Find $ m$.
Let $m\geq 2$ be an integer. A positive integer $n$ has the property that for any positive integer $a$ coprime with $n$, we have $a^m - 1\equiv 0 \pmod n$.
Prove that $n \leq 4m(2^m-1)$.
Created by Harazi, modified by Marian Andronache.
How many positive integers less than $1998$ are relatively prime to $1547$? (Two integers are relatively prime if they have no common factors besides 1.)
A snowman is built on a level plane by placing a ball radius $6$ on top of a ball radius $8$ on top of a ball radius $10$ as shown. If the average height above the plane of a point in the snowman is $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers, find $m + n$.
[asy]
size(150);
draw(circle((0,0),24));
draw(ellipse((0,0),24,9));
draw(circle((0,-56),32));
draw(ellipse((0,-56),32,12));
draw(circle((0,-128),40));
draw(ellipse((0,-128),40,15));
[/asy]
Let $ n, k$ be positive integers and suppose that the polynomial $ x^{2k}\minus{}x^k\plus{}1$ divides $ x^{2n}\plus{}x^n\plus{}1$. Prove that $ x^{2k}\plus{}x^k\plus{}1$ divides $ x^{2n}\plus{}x^n\plus{}1$.
Let $ c$ be a positive integer. The sequence $ a_1,a_2,\ldots$ is defined as follows $ a_1\equal{}c$, $ a_{n\plus{}1}\equal{}a_n^2\plus{}a_n\plus{}c^3$ for all positive integers $ n$. Find all $ c$ so that there are integers $ k\ge1$ and $ m\ge2$ so that $ a_k^2\plus{}c^3$ is the $ m$th power of some integer.
Let $\varphi(n)$ denote the number of positive integers less than $n$ that are relatively prime to $n$. Prove that there exists a positive integer $m$ for which the equation $\varphi(n)=m$ has at least $2015$ solutions in $n$.
[i]Proposed by Iurie Boreico[/i]
Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$?
Do there exist any three relatively prime natural numbers so that the square of each of them is divisible by the sum of the two remaining numbers?
Let $n$ and $k$ be given relatively prime natural numbers, $k<n.$ Each number in the set $M=\{1,2,...,n-1\}$ is colored either blue or white. It is given that [list] [*] for each $i\in M,$ both $i$ and $n-i$ have the same color, [*] for each $i\in M,i\ne k,$ both $i$ and $\left \vert i-k \right \vert $ have the same color. [/list] Prove that all numbers in $M$ have the same color.
Let $m_1,m_2,...,m_{2013} > 1$ be 2013 pairwise relatively prime positive integers and $A_1,A_2,...,A_{2013}$ be 2013 (possibly empty) sets with $A_i\subseteq \{1,2,...,m_i-1\}$ for $i=1,2,...,2013$. Prove that there is a positive integer $N$ such that
\[ N \le \left( 2\left\lvert A_1 \right\rvert + 1 \right)\left( 2\left\lvert A_2 \right\rvert + 1 \right)\cdots\left( 2\left\lvert A_{2013} \right\rvert + 1 \right) \]
and for each $i = 1, 2, ..., 2013$, there does [i]not[/i] exist $a \in A_i$ such that $m_i$ divides $N-a$.
[i]Proposed by Victor Wang[/i]
For each $n\in \mathbb{N}$, let $S(n)$ be the sum of all numbers in the set $\{ 1, 2, 3, \cdots , n \}$ which are relatively prime to $n$.
$(a)$ Show that $2 \cdot S(n)$ is not a perfect square for any $n$.
$(b)$ Given positive integers $m, n$, with odd $n$, show that the equation $2 \cdot S(x) = y^n$ has at least one solution $(x, y)$ among positive integers such that $m|x$.
The polynomial $P$ is a quadratic with integer coefficients. For every positive integer $n$, the integers $P(n)$ and $P(P(n))$ are relatively prime to $n$. If $P(3) = 89$, what is the value of $P(10)$?
Suppose that $m$ and $n$ are relatively prime positive integers with $A = \tfrac mn$, where
\[ A = \frac{2+4+6+\dots+2014}{1+3+5+\dots+2013} - \frac{1+3+5+\dots+2013}{2+4+6+\dots+2014}. \] Find $m$. In other words, find the numerator of $A$ when $A$ is written as a fraction in simplest form.
[i]Proposed by Evan Chen[/i]
Let $\phi(n)$ be the number of positive integers less than $n$ that are relatively prime to $n$, where $n$ is a positive integer. Find all pairs of positive integers $(m,n)$ such that \[2^n + (n-\phi(n)-1)! = n^m+1.\]
Dragon selects three positive real numbers with sum $100$, uniformly at random. He asks Cat to copy them down, but Cat gets lazy and rounds them all to the nearest tenth during transcription. If the probability the three new numbers still sum to $100$ is $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers, compute $100m+n$.
[i]Proposed by Aaron Lin[/i]
Define a sequence by $a_0=1$, together with the rules $a_{2n+1}=a_n$ and $a_{2n+2}=a_n+a_{n+1}$ for each integer $n\ge0$. Prove that every positive rational number appears in the set $ \left\{ \tfrac {a_{n-1}}{a_n}: n \ge 1 \right\} = \left\{ \tfrac {1}{1}, \tfrac {1}{2}, \tfrac {2}{1}, \tfrac {1}{3}, \tfrac {3}{2}, \cdots \right\} $.
It is known that subsets $A_1,A_2, \cdots , A_n$ of set $I=\{1,2,\cdots ,101\}$ satisfy the following condition
$$\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1$$
Determine the maximum positive integer $n$.
*$(a,b)$ means $\gcd (a,b)$
Let $a$ and $b$ be positive integers with $\gcd(a, b)=1$. Show that every integer greater than $ab-a-b$ can be expressed in the form $ax+by$, where $x, y \in \mathbb{N}_{0}$.