Item 1·5% solve rate·answer: Note that we can interpret the game play as building a permutation of $\{1,\dots,n\}$, and the number of times an integer $k$ is chosen on the $k$-th turn is exactly the number of fixed points of this permutation. For $n$ even, Bob selects the goal ``even''. Divide $\{1,\dots,n\}$ into the pairs $\{1,2\},\{3,4\},\dots$; each time Alice chooses an integer, Bob follows suit with the other integer in the same pair. For each pair $\{2k-1,2k\}$, we see that $2k-1$ is a fixed point if and only if $2k$ is, so the number of fixed points is even. For $n$ odd, Bob selects the goal ``odd''. On the first turn, if Alice chooses 1 or 2, then Bob chooses the other one to transpose into the strategy for $n-2$ (with no moves made). We may thus assume hereafter that Alice's first move is some $k > 2$, which Bob counters with 2; at this point there is exactly one fixed point. Thereafter, as long as Alice chooses $j$ on the $j$-th turn (for $j \geq 3$ odd), either $j+1 < k$, in which case Bob can choose $j+1$ to keep the number of fixed points odd; or $j+1=k$, in which case $k$ is even and Bob can choose 1 to transpose into the strategy for $n-k$ (with no moves made). Otherwise, at some odd turn $j$, Alice does not choose $j$. At this point, the number of fixed points is odd, and on each subsequent turn Bob can ensure that neither his own move nor Alice's next move does not create a fixed point: on any turn $j$ for Bob, if $j+1$ is available Bob chooses it; otherwise, Bob has at least two choices available, so he can choose a value other than $j$. For all n, Bob has a winning strategy thus making the required sum $\boxed{n(n+1)/2}$.
Alice and Bob play a game in which they take turns choosing integers from 1 to n. Before any integers are chosen, Bob selects a goal of odd'' or even''. On the first turn, Alice chooses one of the n integers. On the second turn, Bob chooses one of the remaining integers. They continue alternately choosing one of the integers that has not yet been chosen, until the nth turn, which is forced and ends the game. Bob wins if the parity of \{k\colon \mbox{the number kwaschosenonthekth turn}\} matches his goal. Find the sum of all valid values of n for which Bob will have a winning strategy?
Item 2·15% solve rate·answer: Suppose three of the points, say $A, B, C$, are collinear in that order. Then either $|AC| \geq 2|BC|$ or $|AC| \geq 2|AB|$. Hence a ratio of at least two occurs in this case, so we assume from now on that no three of the given points are collinear.\n\nNext we prove that some three of the points form a triangle with one angle at least $120^\circ$.\n\nIf the convex hull of the given points is a hexagon, then the angle sum is $720^\circ$, and one of the angles must be at least $120^\circ$, so some three consecutive vertices of the hexagon form the required triangle.\n\nIf the convex hull of the given points has fewer than six vertices, then one of the points, say $P$, is in the interior of the convex hull of the others. $P$ must be in the interior of a triangle spanned by some other three of the given points (since we have disposed of the case where three points are collinear). Say $P$ lies inside the triangle $QRS$, where $Q, R, S$ are among the given points. Then one of the angles $QPR, RPS, SPQ$ must be at least $120^\circ$, since their sum is $360^\circ$.\n\nFinally, we show that in a triangle in which one angle is at least $120^\circ$, the ratio of the longest side to the shortest side is at least $\sqrt{3}$. Let $ABC$ be a triangle with $\angle A \geq 120^\circ$. Then $-\cos A \geq \frac{1}{2}$. Suppose $b \geq c$.\n\nBy the law of cosines\n\[ a^2 = b^2 + c^2 - 2bc \cos A \geq b^2 + c^2 + bc \geq 3c^2, \]\nso $a \geq \boxed{\sqrt{3}}c$, as claimed.
Given a set of 6 points in the plane, find the lower bound of the ratio of the longest distance between any pair to the shortest$.
Item 3·20% solve rate·answer: We first check that these do work. For $n=1$, it is clear that taking $v = (1)$ and $M = (0)$ has the desired effect. For $(p,n) = (2,2)$, we take $v = \begin{pmatrix} 0 & 1 \end{pmatrix}$ and $M = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and then observe that \[ G^{(k)}(0) = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \, k=0,1,2,3. \] We next check that no other pairs work, keeping in mind that the desired condition means that $G$ acts on $\FF_p^n$ as a cyclic permutation. Assume by way of contradiction that $(p,n)$ has the desired property but does not appear in our list. In particular, we have $n \geq 2$. Let $I$ be the $n \times n$ identity matrix over $\FF_p$. Decompose $\FF_p^n$ as a direct sum of two subspaces $V,W$ such that $M-I$ is nilpotent on $V$ and invertible on $W$. Suppose that $W \neq 0$. Split $v$ as $v_1 + v_2$ with $v_1 \in V$, $v_2 \in W$. Since $M-I$ is invertible on $W$, there exists a unique $w \in W$ such that $(M-I)w = -v_2$. Then $G^{(k)}(w) - w \in V$ for all nonnegative integers $k$. Let $k$ be the least positive integer such that $G^{(k)}(w) = w$; then $k$ is at most the cardinality of $V$, which is strictly less than $p^n$ because $W \neq 0$. This gives a contradiction and thus forces $W = 0$. In other words, the matrix $N = M-I$ is nilpotent; consequently, $N^n = 0$. For any positive integer $k$, we have \begin{align*} G^{(k)}(0) &= v + Mv + \cdots + M^{k-1}v \\ &= \sum_{j=0}^{k-1} \sum_{i=0}^{n-1} \binom{j}{i} N^i v \\ &= \sum_{i=0}^{n-1} \binom{k}{i+1} N^i v. \end{align*} If $n \geq 2$ and $(p,n) \neq (2,2)$, then $p^{n-1} > n$ and so $G^{k}(0) = 0$ for $k = p^{n-1}$ (because all of the binomial coefficients are divisible by $p$). This contradiction completes the proof. The pairs $(p,n)$ with the specified property are those pairs with $n=1$, together with the single pair$(2,2)$ which makes the sum \boxed{13}.
Let \FFp denote the field of integers modulo a prime p, and let n be a positive integer. Let v be a fixed vector in \FFpn, let M be an n×n matrix with entries of \FFp, and define G:\FFpn→\FFpn by G(x)=v+Mx. Let G(k) denote the k-fold composition of G with itself, that is, G(1)(x)=G(x) and G(k+1)(x)=G(G(k)(x)). Determine all pairs p,n for which there exist v and M such that the pn vectors G(k)(0), k=1,2,…,pn are distinct. Calculate the sum of the coordinates of the first four pairs (p,n) which have the smallest values of p+n, given that these pairs allow for the conditions of the problem to be satisfied.
Item 4·25% solve rate·answer: From experimentation (and then an easy induction on $n$) we see that $A^n$ has the form
\[ A^n = \begin{pmatrix} a_n & b_n \\ 2b_n & a_n \end{pmatrix} \]
with $a_n$ odd, and, since $\det A^n = 1$, we have $a_n^2 - 1 = 2b_n^2$. Thus $a_n - 1$ divides $2b_n^2$, so that $d_n = \gcd(a_n - 1, b_n) \geq \sqrt{(a_n - 1)/2}$. Since $\lim_{n \to \infty} a_n = \infty$ (e.g., $a_n > 3a_{n-1}$), the result follows giving us $\lim_{n \to \infty} d_n = \boxed{\infty}$.
For n≥1, let dn be the greatest common divisor of the entries of An−I, where [ A = \begin{pmatrix} 3 & 2 \ 4 & 3 \end{pmatrix} \quad \mbox{ and } \quad I = \begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix}. ] Find the limn→∞dn.
Item 5·25% solve rate·answer: Assuming that there is a solution $u$, then integrating with respect to $x$ from 0 to 1, one obtains \[ \int_0^1 u(x)\,dx = \int_0^1 1\,dx + \lambda \int_0^1 \int_0^x u(y)u(y-x)\,dy\,dx. \] In the iterated integral, one can interchange the order of integration, and letting \( \int_0^1 u(x)\,dx = \alpha \), one gets \[ \alpha = 1 + \lambda \int_0^1 u(y)\int_0^{1-y} u(y+z)\,dz\,dy. \] Now, holding $y$ fixed, let $z = y-x$ to get \[ \alpha = 1 + \lambda \int_0^1 u(y)\int_0^y u(z)\,dz\,dy. \] Set $f(y) = \int_0^y u(z)\,dz$. Then \[ \alpha = 1 + \lambda \int_0^1 f'(y)f(y)\,dy. \] Set $f^2(y) = \alpha$. Then \[ \alpha = 1 + \lambda \frac{1}{2}\big[f^2(1) - f^2(0)\big] = 1 + \lambda \frac{1}{2} \alpha^2. \] This results in the quadratic equation \( \lambda \alpha^2 - 2\alpha + 2 = 0 \). The discriminant of this quadratic equation shows that if $\lambda > \boxed{\frac{1}{2}}$ then the roots are imaginary, and hence no such function $u$ can exist.
Find the lower bound of λ such that there does not exist a real-valued function u such that for all x in the closed interval 0≤x≤1, [ u(x) = 1 + \lambda \int_0^x u(y) u(y-x),dy. ]
Item 6·30% solve rate·answer: Suppose there are two continuous solutions and let $g$ be their difference. Then $g$ is continuous and \[ g(x, y) = \int_0^x \int_0^y g(u, v)\, du\, dv. \] Since $g$ is continuous it is bounded on the given square. Let $M$ be a bound. Then \[ |g(x, y)| \leq \int_0^x \int_0^y |g(u, v)|\, du\, dv \leq \int_0^x \int_0^y M\, du\, dv = Mxy \] for $0 \leq x \leq 1$, $0 \leq y \leq 1$. We now prove that \[ (1) \quad |g(x, y)| \leq M \frac{x^n}{n!} \frac{y^n}{n!} \] for any positive integer $n$. This has been proved for $n = 1$. Assume that it is true for $n = k$; then \[ |g(x, y)| \leq \int_0^x \int_0^y |g(u, v)|\, du\, dv \leq \int_0^x \int_0^y M \frac{u^k}{k!} \frac{v^k}{k!}\, du\, dv = M \frac{x^{k+1}}{(k+1)!} \frac{y^{k+1}}{(k+1)!}. \] Thus $(1)$ is established by mathematical induction. But for any fixed $x$ and $y$, \[ \lim_{n \to \infty} M \frac{x^n}{n!} \frac{y^n}{n!} = 0. \] Hence $|g(x, y)| \leq 0$, that is $g(x, y) = 0$. Thus there cannot be two different continuous solutions making the answer \boxed{1}.
Given the integral equation [ f(x, y) = 1 + \int_0^x \int_0^y f(u, v), du, dv ] find the maximum number of solutions continuous for 0≤x≤1, 0≤y≤1.
Item 7·35% solve rate·answer: Let $A$ be a nonempty finite subset of the integers $\mathbb{Z}$. By the Pigeonhole Principle, any bijection of $\mathbb{Z}$ which maps $A$ to itself must be a bijection when restricted to $A$; in particular, its inverse also maps $A$ to itself. Note that not all the bijections $f_1, f_2, \dots, f_{10}$ can map $A$ to itself, for otherwise, if $0 \in A$, we could not map 0 to any $n \notin A$ by a composition $f_{i_1} \circ f_{i_2} \circ \dots \circ f_{i_m}$, while if $0 \notin A$, we could not map 0 to any $n \in A$ by such a composition.
Let $k$ be the smallest integer such that $f_k$ does not map $A$ to itself, and suppose that more than 512 of the functions $\mathcal{F}$ map $A$ to itself. We can write $\mathcal{F}$ as a disjoint union of unordered pairs of functions such that two compositions $f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{10}^{e_{10}}$ and $f_{1}^{d_1} \circ f_{2}^{d_2} \circ \dots \circ f_{10}^{d_{10}}$ are in the same pair when they differ only in the $k$-th exponent; that is, when $e_i = d_i$ for $i \neq k$. By the Pigeonhole Principle, there is then at least one of these 512 pairs in which both functions map $A$ to itself. Since all $f_l$ with $l > k$ also map $A$ to itself, we can use composition with the inverses of $f_l$, as needed, to conclude that for some $e_1, \dots, e_{k-1}$, the functions $F_1 = f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{k-1}^{e_{k-1}} \circ f_k$ and $F_2 = f_{1}^{e_1} \circ f_{2}^{e_2} \circ \dots \circ f_{k-1}^{e_{k-1}} \circ f_k$ both map $A$ to itself. But then $F_1^{-1} \circ F_2 = f_k$ also maps $A$ to itself, a contradiction. This makes the final answer \boxed{512}.
Let f1,…,f10 be bijections of the set of integers such that for each integer n, there is some composition fi1∘fi2∘⋯∘fim of these functions (allowing repetitions) which maps 0 to n. Consider the set of 1024 functions [ \mathcal{F} = {f_1^{e_1} \circ f_2^{e_2} \circ \cdots \circ f_{10}^{e_{10}}}, ] ei=0 or 1 for 1≤i≤10. (fi0 is the identity function and fi1=fi.) Given that A is any nonempty finite set of integers, find the maximum number the functions in F that map to A to itself.
Item 8·35% solve rate·answer: Let $x + y = a^2$, and $x - y = a$. Then $x^2 - y^2 = a^3$, and
\[ x = \frac{1}{2}(a^2 + a) \text{ and } y = \frac{1}{2}(a^2 - a). \]
Since $a^2$ and $a$ are both even or both odd, $x$ and $y$ are both integers and a solution exists for every integer $a$ thus making the least value \boxed{0}.
Given the equation x2−y2=a3 find the least value of a for which it always has integral solutions for x and y.
Item 9·40% solve rate·answer: By induction, we have $a_n = ((2+\sqrt{3})^n+(2-\sqrt{3})^n)/2 = (\alpha^n+\beta^n)/2$ for all $n$, where $\alpha = 2+\sqrt{3}$ and $\beta = 2-\sqrt{3}$. Now note that if $k$ is an odd positive integer and $a_n \neq 0$, then $\frac{a_{kn}}{a_n} = \frac{\alpha^{kn}+\beta^{kn}}{\alpha^n+\beta^n} = \alpha^{(k-1)n}-\alpha^{(k-2)n}\beta^n+\cdots-\alpha^n\beta^{(k-2)n}+\beta^{(k-1)n}$. This expression is both rational (because $a_n$ and $a_{kn}$ are integers) and of the form $a+b\sqrt{3}$ for some integers $a,b$ by the expressions for $\alpha,\beta$; it follows that it must be an integer, and so $a_{kn}$ is divisible by $a_n$. Applying this to $n=5$ and $k=403$, we find that $a_{2015}$ is divisible by $a_5 = 362$ and thus by $181$. The answer is $\boxed{181}$.
Let a0=1, a1=2, and an=4an−1−an−2 for n≥2. Find the least odd prime factor of a2015.
Item 10·50% solve rate·answer: Divide the region into two parts by the diagonal line $ay = bx$ to get \n\[ \n\int_0^a\int_0^b e^{{\rm max}\{b^2x^2, a^2y^2\}}\,dy\,dx = \int_0^a \int_0^{bx/a} e^{b^2x^2}\,dy\,dx + \int_0^b \int_0^{ay/b} e^{a^2y^2}\,dx\,dy \n\]\n\[ \n= \int_0^a \frac{bx}{a} e^{b^2x^2}\,dx + \int_0^b \frac{ay}{b} e^{a^2y^2}\,dy \n\]\n\[ \n= \boxed{\frac{e^{a^2b^2} - 1}{ab}}. \n\]
Evaluate ∫0a∫0bemax{b2x2,a2y2}dydx where a and b are positive.
Item 11·60% solve rate·answer: The given recursion can be written
\[ S_{n+1} = S_n + \ln (a - S_n). \]
The polygonal representation of this recursion is shown in the figure [see p. 223]. It is clear that, with any choice of $S_1 < a$, we have
\[
S_2 \leq S_3 \leq S_4 \leq \cdots \leq a - 1,
\]
and that the sequence converges to $a - 1$.
To prove this analytically, we let
\[ f(x) = x + \ln (a - x) \]
for $x < a$. Then $f'(x) = 1 - 1/(a - x)$, which is positive for $x < a - 1$ and negative for $x > a - 1$. Since $f(a - 1) = a - 1$, it follows that $f(x) \leq a - 1$ for all $x < a$. Also, if $x \leq a - 1$, then $\ln (a - x) \geq 0$, so $f(x) \geq x$. Then (1) follows immediately, so the sequence $\{S_n\}$ has a limit, say $T$. Clearly, $T \leq a - 1$, so $T$ is a point of continuity for $f$. Hence
\[ f(T) = f(\lim S_n) = \lim f(S_n) = \lim S_{n+1} = T. \]
This gives $\ln (a - T) = 0$, and therefore $T = a - 1$.
We have proved $\lim S_n = \boxed{a - 1}$, as required.
S1=lna and Sn=∑i=1n−1ln(a−Si),n>1. Find the value of
[
\lim_{n \to \infty} S_n.
]
Item 12·75% solve rate·answer: Each pair of points on the $X$-axis together with each pair of points on the $Y$-axis determine a convex quadrilateral whose diagonals meet somewhere in the first quadrant. Conversely, each intersection point arises in this way. Since no three segments are concurrent, except at the endpoints, each intersection point arises uniquely. There are, therefore, \[ \binom{m}{2} \binom{n}{2} = \boxed{\frac{mn(m-1)(n-1)}{4}} \] points of intersection. (Compare Problem A.M. 4 of the Fifteenth Competition.)
Let each of m distinct points on the positive part of the X-axis be joined to n distinct points on the positive part of the Y-axis. Obtain a formula for the number of intersection points of these segments (exclusive of endpoints), assuming that no three of the segments are concurrent.
