A rectangle is partitioned into finitely many small rectangles. We call a point a cross point if it belongs to four different small rectangles. We call a segment on the obtained diagram maximal if there is no other segment containing it. Show that the number of maximal segments plus the number of cross points is $3$ more than the number of small rectangles.

In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied? [i]Proposed by Gerhard Wöginger, Austria[/i]

[b]p1.[/b] Find the largest integer which is a factor of all numbers of the form $n(n +1)(n + 2)$ where $n$ is any positive integer with unit digit $4$. Prove your claims. [b]p2.[/b] Each pair of the towns $A, B, C, D$ is joined by a single one way road. See example. Show that for any such arrangement, a salesman can plan a route starting at an appropriate town that: enables him to call on a customer in each of the towns. Note that it is not required that he return to his starting point. [img]https://cdn.artofproblemsolving.com/attachments/6/5/8c2cda79d2c1b1c859825f3df0163e65da761b.png[/img] [b]p3.[/b] $A$ and $B$ are two points on a circular race track . One runner starts at $A$ running counter clockwise, and, at the same time, a second runner starts from $B$ running clockwise. They meet first $100$ yds from A, measured along the track. They meet a second time at $B$ and the third time at $A$. Assuming constant speeds, now long is the track? [b]p4.[/b] $A$ and $B$ are points on the positive $x$ and positive $y$ axis, respectively, and $C$ is the point $(3,4)$. Prove that the perimeter of $\vartriangle ABC$ is greater than $10$. Suggestion: Reflect!! [b]p5.[/b] Let $A_1,A_2,...,A_8$ be a permutation of the integers $1,2,...,8$ so chosen that the eight sums $9 + A_1$, $10 + A_2$, $...$, $16 + A_8$ and the eight differences $9 -A_1$ , $10 - A_2$, $...$, $16 - A_8$ together comprise $16$ different numbers. Show that the same property holds for the eight numbers in reverse order. That is, show that the $16$ numbers $9 + A_8$, $10 + A_7$, $...$, $16 + A_1$ and $9 -A_8$ , $10 - A_7$, $...$, $16 - A_1$ are also pairwise different. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ and $m$ be positive integers. The daycare nanny uses $n \times m$ square floor mats to construct an $n \times m$ rectangular area, with a baby on each of the mats. Each baby initially faces toward one side of the rectangle. When the nanny claps, all babies crawl one mat forward in the direction it is facing at, and then turn 90 degrees clockwise. If a baby crawls outside of the rectangle, it cries. If two babies simultaneously crawl onto the same mat, they bump into each other and cry. Suppose that it is possible for the nanny to arrange the initial direction of each baby so that, no matter how many times she claps, no baby would cry. Find all possible values of $n$ and $m$. [i]Proposed by Chu-Lan Kao[/i]

A and B plays a game on a pyramid whose base is a $2016$-gon. In each turn, a player colors a side (which was not colored before) of the pyramid using one of the $k$ colors such that none of the sides with a common vertex have the same color. If A starts the game, find the minimal value of $k$ for which $B$ can guarantee that all sides are colored.

Two identical blue blocks, two identical red blocks, two identical green blocks, and two identical purple blocks are placed next to each other in a row. Find the number of distinct arrangements of these blocks where no blue block is placed next to a red block, and no green block is placed next to a purple block.

Consider a binary matrix $M$(all entries are $0$ or $1$) on $r$ rows and $c$ columns, where every row and every column contain at least one entry equal to $1$. Prove that there exists an entry $M(i,j) = 1$, such that the corresponding row-sum $R(i)$ and column-sum $C(j)$ satisfy $r R(i)\ge c C(j)$. (Proposed by Gerhard Woeginger, Austria)

A group of $10$ friends attend an amusement park. Each has visited three different attractions . Leaving the park and talking to each other, they found that any pair of friends visited at least one attraction in common. Determine what could be the minimum number of friends who could walk in the most visited attraction.

Every positive integer is marked with a number from the set $\{ 0,1,2\}$, according to the following rule: $$\text{if a positive integer }k\text{ is marked with }j,\text{ then the integer }k+j\text{ is marked with }0.$$ Let $S$ denote the sum of marks of the first $2019$ positive integers. Determine the maximum possible value of $S$. [i]Proposed by Ivan Novak[/i]

A deck of $ 32$ cards has $ 2$ different jokers each of which is numbered $ 0$. There are $ 10$ red cards numbered $ 1$ through $ 10$ and similarly for blue and green cards. One chooses a number of cards from the deck. If a card in hand is numbered $ k$, then the value of the card is $ 2^k$, and the value of the hand is sum of the values of the cards in hand. Determine the number of hands having the value $ 2004$.

A regular $1997$-gon is divided into triangles by non-intersecting diagonals. Prove that exactly one of them is acute-angled.

Let $k$ be a natural number. Determine the number of non-congruent triangles with the vertices at vertices of a given regular $6k$-gon.

Given positive integers $n_1<n_2<...<n_{2000}<10^{100}$. Prove that we can choose from the set $\{n_1,...,n_{2000}\}$ nonempty, disjont sets $A$ and $B$ which have the same number of elements, the same sum and the same sum of squares.

Given is a square of sides $3\sqrt7 \times 3\sqrt7$. Find the minimal positive integer $n$ such that no matter how we put $n$ unit disks inside the given square, without overlapping, there exists a line that intersects $4$ disks.

Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).

All the squares of a $2022 \times 2022$ board will be colored white or black. Chips will be placed in several of these boxes, at most one per box. We say that two tokens attack each other, when the following two conditions are met: a) There is a path of squares that joins the squares where the pieces were placed. This path can have a horizontal, vertical, or diagonal direction. b) All the squares in this path, including the squares where the pieces are, are of the same color. For example, the following figure shows a small example of a possible coloring of a $6 \times 6$ board with $A, B, C, D$, and $E$ tiles placed. The pairs of checkers that attack each other are $(D, E)$, $(C, D)$, and $(B, E)$. [img]https://cdn.artofproblemsolving.com/attachments/2/0/52ec7b7d1c02e266b666e4f8b25e87c58f0c89.png[/img] What is the maximum value of $k$ such that it is possible to color the board and place $k$ tiles without any two of them attacking each other?

Find the number of the connected graphs with 6 vertices. (Vertices are considered to be different)

Find the minimal positive integer $n$ such that no matter what $n$ distinct numbers from $1$ to $1000$ you choose, such that no two are divisible by a square of the same prime, one of the chosen numbers is a square of prime. [i]D. Zmiaikou[/i]

In the plane, construct as many lines in general position as possible, with any two of them intersecting in a point with integer coordinates.

Let $n \geq 3$ be a positive integer. Find the smallest positive real $k$, satisfying the following condition: if $G$ is a connected graph with $n$ vertices and $m$ edges, then it is always possible to delete at most $k(m-\lfloor \frac{n} {2} \rfloor)$ edges, so that the resulting graph has a proper vertex coloring with two colors.

Let $G$ be an arbitrarily chosen finite simple graph. We write non-negative integers on the vertices of the graph such that for each vertex $v$ in $G,$ the number written on $v$ is equal to the number of vertices adjacent to $v$ where an even number is written. Prove that the number of ways to achieve this is a power of $2$.

Juhan wants to order by weight five balls of pairwise different weight, using only a balance scale. First, he labels the balls with numbers 1 to 5 and creates a list of weighings, such that each element in the list is a pair of two balls. Then, for every pair in the list, he weighs the two balls against each other. Can Juhan sort the balls by weight, using a list with less than 10 pairs?

Is it possible to arrange a permutation of Integers on the integer lattice infinite from both sides such that each row is increasing from left to right and each column increasing from up to bottom?

$n_1<n_2<\ldots<n_k$ are all positive integer numbers $n$, that have the following property: In a square $n \times n$ one can mark $50$ cells so that in any square $3 \times 3$ an odd number of cells are marked. Find $n_{k-2}$

There is a tiger (which is treated as a point) in the plane that is trying to escape. It starts at the origin at time $t = 0$, and moves continuously at some speed $k$. At every positive integer time $t$, you can place one closed unit disk anywhere in the plane, so long as the disk does not intersect the tiger's current position. The tiger is not allowed to move into any previously placed disks (i.e. the disks block the tiger from moving). Note that when you place the disks, you can "see" the tiger (i.e. know where the tiger currently is). Your goal is to prevent the tiger from escaping to infinity. In other words, you must show there is some radius $R(k)$ such that, using your algorithm, it is impossible for a tiger with speed $k$ to reach a distance larger than $R(k)$ from the origin (where it started). Find an algorithm for placing disks such that there exists some finite real $R(k)$ such that the tiger will never be a distance more than $R(k)$ away from the origin. An algorithm that can trap a tiger of speed $k$ will be awarded: 1 pt for $k<0.05$ 10 pts for $k=0.05$ 20 pts for $k=0.2$ 30 pts for $k=0.3$ 50 pts for $k=1$ 70 pts for $k=2$ 80 pts for $k=2.3$ 85 pts for $k=2.6$ 90 pts for $k=2.9$ 100 pts for $k=3.9$