In a simple graph $G$, we call $t$ pairwise adjacent vertices a $t$[i]-clique[/i]. If a vertex is connected with all other vertices in the graph, we call it a [i]central[/i] vertex. Given are two integers $n,k$ such that $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$. Let $G$ be a graph on $n$ vertices such that [b](1)[/b] $G$ does not contain a $(k+1)$-[i]clique[/i]; [b](2)[/b] if we add an arbitrary edge to $G$, that creates a $(k+1)$-[i]clique[/i]. Find the least possible number of [i]central[/i] vertices in $G$.

Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties: (a) For $i=1, \dots, n$, $a_i \in S$. (b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$. (c) For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$. Prove that $S$ must be equal to the set of all integers.

Starting from a positive integer $n$, we can replace the current number with a multiple of the current number or by deleting one or more zeroes from the decimal representation of the current number. Prove that for all values of $n$, it is possible to obtain a single-digit number by applying the above algorithm a finite number of times. There is a nice solution to this...

We have a machine that has an input and an output. The input is a letter from the finite set $I$ and the output is a lamp that at each moment has one of the colors of the set $C=\{c_1,\dots,c_p\}$. At each moment the machine has an inner state that is one of the $n$ members of finite set $S$. The function $o: S \rightarrow C$ is a surjective function defining that at each state, what color must the lamp be, and the function $t:S \times I \rightarrow S$ is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment. In other words a machine is $M=(S,I,C,o,t)$ such that $S,I,C$ are finite, $t:S \times I \rightarrow S$ , and $o:S \rightarrow C$ is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (a) The machine $M$ has $n$ different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than $n-p$ such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state. (b) Prove that for a machine $M$ with $n$ different inner states, there exists an algorithm with no more than $n^2$ inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known. Can you prove the above claim for $\frac{n^2}{2}$?

In the nation of Onewaynia, certain pairs of cities are connected by roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges). Some roads have a traffic capacity of 1 unit and other roads have a traffic capacity of 2 units. However, on every road, traffic is only allowed to travel in one direction. It is known that for every city, the sum of the capacities of the roads connected to it is always odd. The transportation minister needs to assign a direction to every road. Prove that he can do it in such a way that for every city, the difference between the sum of the capacities of roads entering the city and the sum of the capacities of roads leaving the city is always exactly one. [i]Proposed by Zuming Feng and Yufei Zhao[/i]

What is the greatest common factor of $12345678987654321$ and $12345654321$? [i]Proposed by Evan Chen[/i]

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

The sequence of Fibonnaci's numbers if defined from the two first digits $f_1=f_2=1$ and the formula $f_{n+2}=f_{n+1}+f_n$, $\forall n \in N$. [b](a)[/b] Prove that $f_{2010} $ is divisible by $10$. [b](b)[/b] Is $f_{1005}$ divisible by $4$? Albanian National Mathematical Olympiad 2010---12 GRADE Question 4.

Prove there exists a constant $c$ (independent of $n$) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where a) $f(n)=n\ln{n}$; b) $f(n)=n$. [i]David Yang.[/i]

Let $m$ be a positive integer, and consider a $m\times m$ checkerboard consisting of unit squares. At the centre of some of these unit squares there is an ant. At time $0$, each ant starts moving with speed $1$ parallel to some edge of the checkerboard. When two ants moving in the opposite directions meet, they both turn $90^{\circ}$ clockwise and continue moving with speed $1$. When more than $2$ ants meet, or when two ants moving in perpendicular directions meet, the ants continue moving in the same direction as before they met. When an ant reaches one of the edges of the checkerboard, it falls off and will not re-appear. Considering all possible starting positions, determine the latest possible moment at which the last ant falls off the checkerboard, or prove that such a moment does not necessarily exist. [i]Proposed by Toomas Krips, Estonia[/i]

In a country, there are some cities and the city named [i]Ben Song[/i] is capital. Each cities are connected with others by some two-way roads. One day, the King want to choose $n$ cities to add up with [i]Ben Song[/i] city to establish an [i]expanded capital[/i] such that the two following condition are satisfied: (i) With every two cities in [i]expanded capital[/i], we can always find a road connecting them and this road just belongs to the cities of [i]expanded capital[/i]. (ii) There are exactly $k$ cities which do not belong to [i]expanded capital[/i] have the direct road to at least one city of [i]expanded capital[/i]. Prove that there are at most $\binom{n+k}{k}$ options to expand the capital for the King.

Let $a,b,c>0$ such that $a+b+c=1$. Prove: \[\frac{a^{2}}b+\frac{b^{2}}c+\frac{c^{2}}a \ge 3(a^{2}+b^{2}+c^{2}) \]

A finite set $S$ of unit squares is chosen out of a large grid of unit squares. The squares of $S$ are tiled with isosceles right triangles of hypotenuse $2$ so that the triangles do not overlap each other, do not extend past $S$, and all of $S$ is fully covered by the triangles. Additionally, the hypotenuse of each triangle lies along a grid line, and the vertices of the triangles lie at the corners of the squares. Show that the number of triangles must be a multiple of $4$.

Determine the largest number of steps for $\gcd(k,76)$ to terminate over all choices of $0 < k < 76$, using the following algorithm for gcd. Give your answer in the form $(n,k)$ where $n$ is the maximal number of steps and $k$ is the $k$ which achieves this. If multiple $k$ work, submit the smallest one. \begin{tabular}{l} 1: \textbf{FUNCTION} $\text{gcd}(a,b)$: \\ 2: $\qquad$ \textbf{IF} $a = 0$ \textbf{RETURN} $b$ \\ 3: $\qquad$ \textbf{ELSE RETURN} $\text{gcd}(b \bmod a,a)$ \end{tabular}

Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, \[n = a_1 + a_2 + \cdots a_k\] with $k$ an arbitrary positive integer and $a_1 \le a_2 \le \cdots \le a_k \le a_1 + 1$? For example, with $n = 4$, there are four ways: $4$, $2 + 2$, $1 + 1 + 2$, $1 + 1 + 1 + 1$.

Let $n$  be a positive integer. A row of $n+ 1$ squares is written from left to right, numbered $0, 1, 2, \cdots, n$ Two frogs, named Alphonse and Beryl, begin a race starting at square 0. For each second that passes, Alphonse and Beryl make a jump to the right according to the following rules: if there are at least eight squares to the right of Alphonse, then Alphonse jumps eight squares to the right. Otherwise, Alphonse jumps one square to the right. If there are at least seven squares to the right of Beryl, then Beryl jumps seven squares to the right. Otherwise, Beryl jumps one square to the right. Let A(n) and B(n) respectively denote the number of seconds for Alphonse and Beryl to reach square n. For example, A(40) = 5 and B(40) = 10. (a) Determine an integer n>200 for which $B(n) <A(n)$. (b) Determine the largest integer n for which$ B(n) \le A(n)$.

Let $\mathbb{Q^+}$ denote the set of positive rational numbers. Determine all functions $f: \mathbb{Q^+} \to \mathbb{Q^+}$ that satisfy the conditions \[ f \left( \frac{x}{x+1}\right) = \frac{f(x)}{x+1} \qquad \text{and} \qquad f \left(\frac{1}{x}\right)=\frac{f(x)}{x^3}\] for all $x \in \mathbb{Q^+}.$

Given a table $m\times n$, in each cell of which a number $+1$ or $-1$ is written. It is known that initially exactly one $-1$ is in the table, all the other numbers being $+1$. During a move, it is allowed to chose any cell containing $-1$, replace this $-1$ by $0$, and simultaneously multiply all the numbers in the neighbouring cells by $-1$ (we say that two cells are neighbouring if they have a common side). Find all $(m,n)$ for which using such moves one can obtain the table containing zeros only, regardless of the cell in which the initial $-1$ stands.

A magician intends to perform the following trick. She announces a positive integer $n$, along with $2n$ real numbers $x_1 < \dots < x_{2n}$, to the audience. A member of the audience then secretly chooses a polynomial $P(x)$ of degree $n$ with real coefficients, computes the $2n$ values $P(x_1), \dots , P(x_{2n})$, and writes down these $2n$ values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience. Can the magician find a strategy to perform such a trick?

A year is a leap year if and only if the year number is divisible by $400$ (such as $2000$) or is divisible by $4$ but not by $100$ (such as $2012$). The $200\text{th}$ anniversary of the birth of novelist Charles Dickens was celebrated on February $7$, $2012$, a Tuesday. On what day of the week was Dickens born? $ \textbf{(A)}\ \text{Friday} \qquad\textbf{(B)}\ \text{Saturday} \qquad\textbf{(C)}\ \text{Sunday} \qquad\textbf{(D)}\ \text{Monday} \qquad\textbf{(E)}\ \text{Tuesday} $

A rectangular array of numbers is given. In each row and each column, the sum of all numbers is an integer. Prove that each nonintegral number $x$ in the array can be changed into either $\lceil x\rceil $ or $\lfloor x\rfloor $ so that the row-sums and column-sums remain unchanged. (Note that $\lceil x\rceil $ is the least integer greater than or equal to $x$, while $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$.)

On Christmas Eve, 1983, Dean Jixon, the famous seer who had made startling predictions of the events of the preceding year that the volcanic and seismic activities of $1980$ and $1981$ were connected with mathematics. The diminishing of this geological activity depended upon the existence of an elementary proof of the irreducibility of the polynomial \[P(x)=x^{1981}+x^{1980}+12x^{2}+24x+1983.\] Is there such a proof?

Each rational number is painted either white or red. Call such a coloring of the rationals [i]sanferminera[/i] if for any distinct rationals numbers $x$ and $y$ satisfying one of the following three conditions: [list=1][*]$xy=1$, [*]$x+y=0$, [*]$x+y=1$,[/list]we have $x$ and $y$ painted different colors. How many sanferminera colorings are there?

A year is a leap year if and only if the year number is divisible by $400$ (such as $2000$) or is divisible by $4$ but not by $100$ (such as $2012$). The $200\text{th}$ anniversary of the birth of novelist Charles Dickens was celebrated on February $7$, $2012$, a Tuesday. On what day of the week was Dickens born? $ \textbf{(A)}\ \text{Friday} \qquad\textbf{(B)}\ \text{Saturday} \qquad\textbf{(C)}\ \text{Sunday} \qquad\textbf{(D)}\ \text{Monday} \qquad\textbf{(E)}\ \text{Tuesday} $

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.