A knight is placed on each square of the first column of a $2017 \times 2017$ board. A [i]move[/i] consists in choosing two different knights and moving each of them to a square which is one knight-step away. Find all integers $k$ with $1 \leq k \leq 2017$ such that it is possible for each square in the $k$-th column to contain one knight after a finite number of moves. Note: Two squares are a knight-step away if they are opposite corners of a $2 \times 3$ or $3 \times 2$ board.

Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1. [b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.

In a party, each person knew exactly $ 22$ other persons. For each two persons $ X$ and $ Y$, if $ X$ and $ Y$ knew each other, there is no other person who knew both of them, and if $ X$ and $ Y$ did not know each other, there are exactly $ 6$ persons who knew both of them. Assume that $ X$ knew $ Y$ iff $ Y$ knew $ X$. How many people did attend the party? [i]Yudi Satria, Jakarta[/i]

Some of $n$ towns are connected by two-way airlines. There are $m$ airlines in total. For $i = 1, 2, \cdots, n$, let $d_i$ be the number of airlines going from town $i$. If $1\le d_i \le 2010$ for each $i = 1, 2,\cdots, 2010$, prove that \[\displaystyle\sum_{i=1}^n d_i^2\le 4022m- 2010n\] Find all $n$ for which equality can be attained. [i]Proposed by Aleksandar Ilic[/i]

A game of solitaire strats of with $25$ cards. Some are facing up and sum are facing down. In each move a card that's facing up should me choosen, taken away, and turning over the cards next to it (if there are cards next to it). The game is won when you have accomplished to take all the $25$ cards from the table. If you initially start with $n$ cards facing up, find all the values of $n$ such that the game can be won. Explain how to win the game, independently from the initial placement of the cards facing up, justify your answer for why it is impossible to win with other values of $n$. Two cards are neighboring when one is immediately next to the other, to the left or right. Example: The card marked $A$ has two neighboring cards and the one marked with only a $B$ has only one neighboring card. After taking a card there is a hole left, such that the card marked $C$ has only one neighboring card, and the one marked $D$ does'nt have any.

Each one of 2006 students makes a list with 12 schools among 2006. If we take any 6 students, there are two schools which at least one of them is included in each of 6 lists. A list which includes at least one school from all lists is a good list. a) Prove that we can always find a good list with 12 elements, whatever the lists are; b) Prove that students can make lists such that no shorter list is good.

A cricket wants to move across a $2n \times 2n$ board that is entirely covered by dominoes, with no overlap. He jumps along the vertical lines of the board, always going from the midpoint of the vertical segment of a $1 \times 1$ square to another midpoint of the vertical segment, according to the rules: $(i)$ When the domino is horizontal, the cricket jumps to the opposite vertical segment (such as from $P_2$ to $P_3$); $(ii)$ When the domino is vertical downwards in relation to its position, the cricket jumps diagonally downwards (such as from $P_1$ to $P_2$); $(iii)$ When the domino is vertically upwards relative to its position, the cricket jumps diagonally upwards (such as from $P_3$ to $P_4$). The image illustrates a possible covering and path on the $4 \times 4$ board. Considering that the starting point is on the first vertical line and the finishing point is on the last vertical line, prove that, regardless of the covering of the board and the height at which the cricket starts its path, the path ends at the same initial height.

One hundred points are marked in the plane, with no three in a line. Is it always possible to connect the points in pairs such that all fifty segments intersect one another?

A prefrosh is participating in Caltech’s “Rotation.” They must rank Caltech’s $8$ houses, which are Avery, Page, Lloyd, Venerable, Ricketts, Blacker, Dabney, and Fleming, each a distinct integer rating from $1$ to $8$ inclusive. The conditions are that the rating $x$ they give to Fleming is at most the average rating $y$ given to Ricketts, Blacker, and Dabney, which is in turn at most the average rating $z$ given to Avery, Page, Lloyd, and Venerable. Moreover $x, y, z$ are all integers. How many such rankings can the prefrosh provide?

Let $n$ be an integer greater than $1$. For a positive integer $m$, let $S_{m}= \{ 1,2,\ldots, mn\}$. Suppose that there exists a $2n$-element set $T$ such that (a) each element of $T$ is an $m$-element subset of $S_{m}$; (b) each pair of elements of $T$ shares at most one common element; and (c) each element of $S_{m}$ is contained in exactly two elements of $T$. Determine the maximum possible value of $m$ in terms of $n$.

King Albrecht founded a family. In the family everyone has exactly $ 8$ children. The only, but really important rule is that among the grandchildren of any person at most $x$ can be named Bela. (None of Albrecht’s children is called Bela.) For which $x$ is it possible that after a certain time each newborn in the family has at least one direct ancestor in the Royal family called Bela. No two of Albrecht’s descendants (including himself) have a common child.

There are 20 students in a high school class, and each student has exactly three close friends in the class. Five of the students have bought tickets to an upcoming concert. If any student sees that at least two of their close friends have bought tickets, then they will buy a ticket too. Is it possible that the entire class buys tickets to the concert? (Assume that friendship is mutual; if student $A$ is close friends with student $B$, then $B$ is close friends with $A$.)

$37$ points are arbitrarily marked on the plane. Prove that among them there must be either two points at a distance greater than $6$, or two points at a distance less than $1.5$.

Let $K$ denote the set $\{a, b, c, d, e\}$. $F$ is a collection of $16$ different subsets of $K$, and it is known that any three members of $F$ have at least one element in common. Show that all $16$ members of $F$ have exactly one element in common.

Let $S$ be a set of in $3-$ space such that each of the points in $S$ has integer coordinates $(x,y,z)$ with $1 \le x,y,z \le n $. Suppose the pairwise distances between these points are all distinct. Prove that $$|S| \le min \{(n+2)\sqrt{\frac{n}{3}},n\sqrt{6} \}$$

It is allowed to perform the following transformations in the plane with any integers $a$: (1) Transform every point $(x, y)$ to the corresponding point $(x + ay, y)$, (2) Transform every point $(x, y)$ to the corresponding point $(x, y + ax)$. Does there exist a non-square rhombus whose all vertices have integer coordinates and which can be transformed to: a) Vertices of a square, b) Vertices of a rectangle with unequal side lengths?

Determine for which $m$ there exist exactly $2^{15}$ subsets $X$ of $\{1,2,...,47\}$ with the following property: $m$ is the smallest element of $X$, and for every $x \in X$, either $x+m \in X$ or $x+m > 47$.

[b]p1.[/b] How many subsets of $\{D,U,K,E\}$ have an odd number of elements? [b]p2.[/b] Find the coefficient of $x^{12}$ in $(1 + x^2 + x^4 +... + x^{28})(1 + x + x^2 + ...+ x^{14})^2$. [b]p3.[/b] How many $4$-digit numbers have their digits in non-decreasing order from left to right? [b]p4.[/b] A dodecahedron (a polyhedron with $12$ faces, each a regular pentagon) is projected orthogonally onto a plane parallel to one of its faces to form a polygon. Find the measure (in degrees) of the largest interior angle of this polygon. [b]p5.[/b] Justin is back with a $6\times 6$ grid made of $36$ colorless squares. Dr. Kraines wants him to color some squares such that $\bullet$ Each row and column of the grid must have at least one colored square $\bullet$ For each colored square, there must be another colored square on the same row or column What is the minimum number of squares that Justin will have to color? [b]p6.[/b] Inside a circle $C$, we have three equal circles $C_1$, $C_2$, $C_3$, which are pairwise externally tangent to each other and all internally tangent to $C$. What is the ratio of the area of $C_1$ to the area of $C$? [b]p7.[/b] There are $3$ different paths between the Duke Chapel and the Physics building. $6$ students are heading towards the Physics building for a class, so they split into $3$ pairs and each pair takes a separate path from the Chapel. After class, they again split into $3$ pairs and take separate paths back. Find the number of possible scenarios where each student's companion on the way there is different from their companion on the way back. [b]p8.[/b] Let $a_n$ be a sequence that satisfies the recurrence relation $$a_na_{n+2} =\frac{\cos (3a_{n+1})}{\cos (a_{n+1})[2 \cos(2a_{n+1}) - 1]}a_{n+1}$$ with $a_1 = 2$ and $a_2 = 3$. Find the value of $2018a_{2017}$. [b]p9.[/b] Let $f(x)$ be a polynomial with minimum degree, integer coefficients, and leading coefficient of $1$ that satisfies $f(\sqrt7 +\sqrt{13})= 0$. What is the value of $f(10)$? [b]p10.[/b] $1024$ Duke students, indexed $1$ to $1024$, are having a chat. For each $1 \le i \le 1023$, student $i$ claims that student $2^{\lfloor \log_2 i\rfloor +1}$ has a girlfriend. ($\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.) Given that exactly $201$ people are lying, find the index of the $61$st liar (ordered by index from smallest to largest). PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A [i]synogon [/i] is a convex $2n$-gon with all sides of the same length and all opposite sides are parallel. Show that every synogon can be broken down into a finite number of rhombuses.

Find the number of $5$-digit $n$, s.t. every digit of $n$ is either $0$, $1$, $3$, or $4$, and $n$ is divisible by $15$.

There are $ 11$ coins, which are indistinguishable by sight. Nevertheless, among them there are $ 10$ geniune coins ( of weight $ 20$ g each) and one counterfeit (of weight $ 21$ g). You have a two-pan scale which is blanced when the weight in the left-hand pan is twice as much as the weight in the right-hand one. Using this scale only, find the false coin by three weighings.

There are $n \ge 2$ coins, each with a different positive integer value. Call an integer $m$ [i]sticky [/i] if some subset of these $n$ coins have total value $m$. We call the entire set of coins a stick if all the sticky numbers form a consecutive range of integers. Compute the minimum total value of a stick across all sticks containing a coin of value $100$.

Let $a_1<a_2 \dots <a_n$ be positive integers, with $n\geq 2$. An invisible frog lies on the real line, at a positive integer point. Initially, the hunter chooses a number $k$, and then, once every minute, he can check if the frog currently lies in one of $k$ points of his choosing, after which the frog goes from its point $x$ to one of the points $x+a_1, x+a_2 \dots x+a_n$. Based on the values of $a_1, a_2 \dots a_n$, what is the smallest value of $k$ such that the hunter can guarantee to find the frog within a finite number of minutes, no matter where it initially started? [i]Proposed by David Anghel[/i]

There is a token in one of the nodes of a hexagon with side $n$, divided into regular triangles (see figure). Two players take turns moving it to one of the neighboring nodes, and it is forbidden to go to a node that the token has already visited. The one who loses who can't make a move. Who wins with the right game? [img]https://cdn.artofproblemsolving.com/attachments/2/f/18314fe7f9f4cd8e783037a8e5642e17f4e1be.png[/img]

A square $2n\times 2n$ grid is given. Let us consider all possible paths along grid lines, going from the centre of the grid to the border, such that (1) no point of the grid is reached more than once, and (2) each of the squares homothetic to the grid having its centre at the grid centre is passed through only once. (a) Prove that the number of all such paths is equal to $4\prod_{i=2}^n(16i-9)$. (b) Find the number of pairs of such paths that divide the grid into two congruent figures. (c) How many quadruples of such paths are there that divide the grid into four congruent parts?