Let \( G \) be a graph colored using \( k \) colors. We say that a vertex is [b]forced[/b] if it has neighbors in all the other \( k - 1 \) colors. Prove that for any \( 2024 \)-regular graph \( G \) that contains no triangles or quadrilaterals, there exists a coloring using \( 2025 \) colors such that at least \( 1013 \) of the colors have a forced vertex of that color. Note: The graph coloring must be valid, this means no \( 2 \) vertices of the same color may be adjacent.

At a dance there are $12$ men, numbered $1$ to $12$, and $12$ women numbered $1$ to $12$. Each man is assigned a “secret friend” among the $11$ others. They all danced all the pieces. In the first piece each man danced with the woman who has the same number. From then on, each man danced the new piece with the woman who had danced the piece earlier with his secret friend. In the third piece the couples were: [img]https://cdn.artofproblemsolving.com/attachments/c/d/f5ea0931e5751739c1ba556f84ab5736f2d11a.png[/img] Find the number of each man's secret friend.

A and B play tennis. The player to first win at least four points and at least two more than the other player wins. We know that A gets a point each time with probability $p\le \frac12$, independent of the game so far. Prove that the probability that A wins is at most $2p^2$.

Let $n$ be a positive integer and let $\triangle$ be the closed triangular domain with vertices at the lattice points $(0, 0), (n, 0)$ and $(0, n)$. Determine the maximal cardinality a set $S$ of lattice points in $\triangle$ may have, if the line through every pair of distinct points in $S$ is parallel to no side of $\triangle$.

There are villager $0$, villager $1$, . . . , villager $2015$ i.e. $2016$ people in the village. You are villager $0$. Each villager is either honest or liar. You don’t know each villager is honest or liar, but you know you are honest and the number of liar is equal or smaller than integer $T$. The villagers became to write one letter without fail from one day. For integers $1 \le n \le 2015$, there are set integers $1 < k_n < 2015$. The letter villager $i$ wrote in day $n$ of the morning is delivered to villager $i + k_n$ if villager $i$ is honest, or villager $i - k_n$ if villager $i$ is liar in day $n$ of the evening. If $i - j$ is divisible by $2016$, villager $i$ and $j$ point same villager. Villagers don’t know $k_n$, but sender is told when letters are received. Villager can write anything on a letter, and each villager receives letters from any villagers a sufficient number of times after enough time. i.e. there are $n$ satisfying $k = k_n$ infinitely for each integer $1 \le k \le 2015$. You want to know the honest persons of this village. You can gather all villagers just once and instruct in one day of noon. The honest person obeys your instruction but the liar person not always obeys and he or she writes on a letter anything possible. One day from your instruction for a while, you could determine all honest persons of this village. Find the maximum value of $T$ such that it is possible to do this if you instruct appropriate regardless of the villagers who are honest or liar.

In each square of a garden shaped like a $2022 \times 2022$ board, there is initially a tree of height $0$. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn: [list] [*] The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller. [*] The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter. [/list] We say that a tree is [i]majestic[/i] if its height is at least $10^6$. Determine the largest $K$ such that the gardener can ensure there are eventually $K$ majestic trees on the board, no matter how the lumberjack plays.

Let $n \ge 1$ be a positive integer. An $n \times n$ matrix is called [i]good[/i] if each entry is a non-negative integer, the sum of entries in each row and each column is equal. A [i]permutation[/i] matrix is an $n \times n$ matrix consisting of $n$ ones and $n(n-1)$ zeroes such that each row and each column has exactly one non-zero entry. Prove that any [i]good[/i] matrix is a sum of finitely many [i]permutation[/i] matrices.

[b]p1.[/b] Arrange the whole numbers $1$ through $15$ in a row so that the sum of any two adjacent numbers is a perfect square. In how many ways this can be done? [b]p2.[/b] Prove that if $p$ and $q$ are prime numbers which are greater than $3$ then $p^2 - q^2$ is divisible by $24$. [b]p3.[/b] If a polyleg has even number of legs he always tells truth. If he has an odd number of legs he always lies. Once a green polyleg told a dark-blue polyleg ”- I have $8$ legs. And you have only $6$ legs!” The offended dark-blue polyleg replied ”-It is me who has $8$ legs, and you have only $7$ legs!” A violet polyleg added ”-The dark-blue polyleg indeed has $8$ legs. But I have $9$ legs!” Then a stripped polyleg started ”None of you has $8$ legs. Only I have $8$ legs!” Which polyleg has exactly $8$ legs? [b][b]p4.[/b][/b] There is a small puncture (a point) in the wall (as shown in the figure below to the right). The housekeeper has a small flag of the following form (see the figure left). Show on the figure all the points of the wall where you can hammer in a nail such that if you hang the flag it will close up the puncture. [img]https://cdn.artofproblemsolving.com/attachments/a/f/8bb55a3fdfb0aff8e62bc4cf20a2d3436f5d90.png[/img] [b]p5.[/b] Assume $ a, b, c$ are odd integers. Show that the quadratic equation $ax^2 + bx + c = 0$ has no rational solutions. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Prove that among $20$ consecutive positive integers there is an integer $d$ such that for every positive integer $n$ the following inequality holds $$n \sqrt{d} \left\{n \sqrt {d} \right \} > \dfrac{5}{2}$$ where by $\left \{x \right \}$ denotes the fractional part of the real number $x$. The fractional part of the real number $x$ is defined as the difference between the largest integer that is less than or equal to $x$ to the actual number $x$. [i](Serbia)[/i]

There are $n > 2022$ cities in the country. Some pairs of cities are connected with straight two-ways airlines. Call the set of the cities {\it unlucky}, if it is impossible to color the airlines between them in two colors without monochromatic triangle (i.e. three cities $A$, $B$, $C$ with the airlines $AB$, $AC$ and $BC$ of the same color). The set containing all the cities is unlucky. Is there always an unlucky set containing exactly 2022 cities?

The number devil has coloured the integer numbers: every integer is coloured either black or white. The number $1$ is coloured white. For every two white numbers $a$ and $b$ ($a$ and $b$ are allowed to be equal) the numbers $a-b$ and $a + $b have different colours. Prove that $2011$ is coloured white.

Petrică, Vasile and Tudor participated at a math contest. At the contest $ 5$ problems where proposed, each worth distinct integer numbers of points. Petrică solved $4$ problems completely and got $21$ points and Vasile solved $3 $ problems completely and got $22$ points. Tudor solved all problems completely. What are the lowest and highest possible scores of Tudor?

In a word of more than $10$ letters, any two consecutive letters are different. Prove that one can change places of two consecutive letters so that the resulting word is not [i]periodic[/i], that is, cannot be divided into equal subwords.

[b]p1.[/b] A light beam shines from the origin into the unit square at an angle of $\theta$ to one of the sides such that $\tan \theta = \frac{13}{17}$ . The light beam is reflected by the sides of the square. How many times does the light beam hit a side of the square before hitting a vertex of the square? [img]https://cdn.artofproblemsolving.com/attachments/5/7/1db0aad33ed9bf82bee3303c7fbbe0b7c2574f.png[/img] [b]p2.[/b] Alex is given points $A_1,A_2,...,A_{150}$ in the plane such that no three are collinear and $A_1$, $A_2$, $...$, $A_{100}$ are the vertices of a convex polygon $P$ containing $A_{101}$, $A_{102}$, $ ...$, $A_{150}$ in its interior. He proceeds to draw edges $A_iA_j$ such that no two edges intersect (except possibly at their endpoints), eventually dividing $P$ up into triangles. How many triangles are there? [img]https://cdn.artofproblemsolving.com/attachments/d/5/12c757077e87809837d16128b018895a8bcc94.png[/img] [b]p3. [/b]The polynomial P(x) has the property that $P(1)$, $P(2)$, $P(3)$, $P(4)$, and $P(5)$ are equal to $1$, $2$, $3$, $4$,$5$ in some order. How many possibilities are there for the polynomial $P$, given that the degree of $P$ is strictly less than $4$? PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A square $ (n \minus{} 1) \times (n \minus{} 1)$ is divided into $ (n \minus{} 1)^2$ unit squares in the usual manner. Each of the $ n^2$ vertices of these squares is to be coloured red or blue. Find the number of different colourings such that each unit square has exactly two red vertices. (Two colouring schemse are regarded as different if at least one vertex is coloured differently in the two schemes.)

Determine the number of ten-digit positive integers with the following properties: $\bullet$ Each of the digits $0, 1, 2, . . . , 8$ and $9$ is contained exactly once. $\bullet$ Each digit, except $9$, has a neighbouring digit that is larger than it. (Note. For example, in the number $1230$, the digits $1$ and $3$ are the neighbouring digits of $2$ while $2$ and $0$ are the neighbouring digits of $3$. The digits $1$ and $0$ have only one neighbouring digit.) [i](Karl Czakler)[/i]

Let $k$ be a positive integer. A sequence of integers $a_1, a_2, \cdots$ is called $k$-pop if the following holds: for every $n \in \mathbb{N}$, $a_n$ is equal to the number of distinct elements in the set $\{a_1, \cdots , a_{n+k} \}$. Determine, as a function of $k$, how many $k$-pop sequences there are. [i]Proposed by Sutanay Bhattacharya[/i]

Identical rectangular cardboard pieces are handed out to $30$ students, one to each. Each student cuts (parallel to the edges) his or her piece into equally large squares. Two different students’ squares do not necessarily have the same size. After all the cutting it turns out that the total number of squares is a prime. Prove that the original cardboard pieces must have been quadratic.

Let $A$ be the subset of $\{1, 2, ..., 16\}$ that has $6$ elements. Prove that there exist $2$ subsets of $A$ that are disjoint, and the sum of their elements are the same.

In how many ways can the number $2000$ be written as a sum of three positive, not necessarily different integers? (Sums like $1 + 2 + 3$ and $3 + 1 + 2$ etc. are the same.)

Let $ABCD$ be a square with side $20$ and $T_1, T_2, ..., T_{2000}$ are points in $ABCD$ such that no $3$ points in the set $S = \{A, B, C, D, T_1, T_2, ..., T_{2000}\}$ are collinear. Prove that there exists a triangle with vertices in $S$, such that the area is less than $1/10$.

Let $1 \leq n \leq 2021$ be a positive integer. Jack has $2021$ coins arranged in a line where each coin has an $H$ on one side and a $T$ on the other. At the beginning, all coins show $H$ except the nth coin. Jack can repeatedly perform the following operation: he chooses a coin showing $T$, and turns over the coins next to it to the left and to the right (if any). Determine all $n$ such that Jack can make all coins show $T$ after a finite number of operations.

Let $ABCD$ be a square with side length $1$. How many points $P$ inside the square (not on its sides) have the property that the square can be cut into $10$ triangles of equal area such that all of them have $P$ as a vertex? [i]Proposed by Josef Tkadlec - Czech Republic[/i]

Let $ABC$ be a triangle. Take $n$ point lying on the side $AB$ (different from $A$ and $B$) and connect all of them by straight lines to the vertex $C$. Similarly, take $n$ points on the side $AC$ and connect them to $B$. Into how many regions is the triangle $ABC$ partitioned by these lines? Further, take $n$ points on the side $BC$ also and join them with $A$. Assume that no three straight lines meet at a point other than $A,B$ and $C$. Into how many regions is the triangle $ABC$ partitioned now?

Given $n$ numbers different from $0$, ($n \in \mathbb{N}$) which are arranged randomly. We do the following operation: Choose some consecutive numbers in the given order and change their sign (i.e. $x \rightarrow -x$). What is the minimum number of operations needed, in order to make all the numbers positive for any given initial configuration of the $n$ numbers?