Show that a graph with 2n points and $n^2 + 1$ edges necessarily contains a 3-cycle, but that we can find a graph with 2n points and $n^2$ edges without a 3-cycle. please prove it without induction .

Let $A,B,P$ be three points on a circle. Prove that if $a,b$ are the distances from $P$ to the tangents at $A,B$ respectively, and $c$ is the distance from $P$ to the chord $AB$, then $c^2 =ab$.

Let $M$ be the midpoint of the side $AB$ of a triangle $ABC$. A circle through point $C$ that has a point of tangency to the line $AB$ at point $A$ and a circle through point $C$ that has a point of tangency to the line $AB$ at point $B$ intersect the second time at point $N$. Prove that $|CM|^2 + |CN|^2 - |MN|^2 = |CA|^2 + |CB|^2 - |AB|^2$.

For integral $m$, let $p(m)$ be the greatest prime divisor of $m.$ By convention, we set $p(\pm 1) = 1$ and $p(0) = \infty.$ Find all polynomials $f$ with integer coefficients such that the sequence \[ \{p \left( f \left( n^2 \right) \right) - 2n \}_{n \geq 0} \] is bounded above. (In particular, this requires $f \left (n^2 \right ) \neq 0$ for $n \geq 0.$)

Find the sum of the smallest and largest possible values for $x$ which satisfy the following equation. $$9^{x+1} + 2187 = 3^{6x-x^2}.$$

there are $n$ points on the plane,any two vertex are connected by an edge of red,yellow or green,and any triangle with vertex in the graph contains exactly $2$ colours.prove that $n<13$

Prove that for every integer power of 2, there exists a multiple of it with all digits (in decimal expression) not zero.

Let the line $ z\equal{}x, \, y\equal{}0$ rotate at a constant speed about the $ z$-axis; let at the same time the point of intersection of this line with the $ z$-axis be displaced along the $ z$-axis at constant speed. (a) Determine that surface of rotation upon which the resulting helical surface can be developed (i.e. isometrically mapped). (b) Find those lines of the surface of rotation into which the axis and the generators of the helical surface will be mapped by this development.

Square $SEAN$ has side length $2$ and a quarter-circle of radius $1$ around $E$ is cut out. Find the radius of the largest circle that can be inscribed in the remaining figure.

For real numbers $a, b, c$ with $a + b + c = 3$, prove that $$a^2(b - c)^2 + b^2(c - a)^2 + c^2(a - b)^2 \ge \frac9 2 abc(1 - abc)$$ and state when equality is reached.

Prove that there are infinitely many different triangles in coordinate plane satisfying: 1) their vertices are lattice points 2) their side lengths are consecutive integers [b]Remark[/b]: Triangles that can be obtained by rotation or translation or shifting the coordinate system are considered as equal triangles

A railway line is divided into ten sections by the stations $A,B,C,D,E,F, G,H,I,J,K$. The length of each section is an integer number of kilometers and the distacne between $A$ and $K$ is $56$ km. A trip along two successive sections never exceeds $12$ km, but a trip along three successive sections is at least $17$ km. What is the distance between $B$ and $G$? [img]https://cdn.artofproblemsolving.com/attachments/1/f/202ddf633ed6da8692bf4d0b1fc0af59548526.png[/img]

Inside a convex quadrilateral $ABCD$ there is a point $P$ such that the triangles $PAB, PBC, PCD, PDA$ have equal areas. Prove that the area of $ABCD$ is bisected by one of the diagonals.

Suppose that Romeo and Juliet each have a regular tetrahedron to the vertices of which some positive real numbers are assigned. They associate each edge of their tetrahedra with the product of the two numbers assigned to its end points. Then they write on each face of their tetrahedra the sum of the three numbers associated to its three edges. The four numbers written on the faces of Romeo's tetrahedron turn out to coincide with the four numbers written on Juliet's tetrahedron. Does it follow that the four numbers assigned to the vertices of Romeo's tetrahedron are identical to the four numbers assigned to the vertices of Juliet's tetrahedron?

Alice and Bob are each secretly given a real number between 0 and 1 uniformly at random. Alice states, “My number is probably greater than yours.” Bob repudiates, saying, “No, my number is probably greater than yours!” Alice concedes, muttering, “Fine, your number is probably greater than mine.” If Bob and Alice are perfectly reasonable and logical, what is the probability that Bob’s number is actually greater than Alice’s?

Students in a class consisting of $m$ boys and $n$ girls line up. Over all possible ways of lining up, compute the average number of pairs of two boys or two girls who are next to each other.

$k$ and $n$ are positive integers that are greater than $1$. $N$ is the set of positive integers. $A_1, A_2, \cdots A_k$ are pairwise not-intersecting subsets of $N$ and $A_1 \cup A_2 \cup \cdots \cup A_k = N$. Prove that for some $i \in \{ 1,2,\cdots,k \}$, there exsits infinity many non-factorable n-th degree polynomials so that coefficients of one polynomial are pairwise distinct and all the coeficients are in $A_i$.

A pair of standard 6-sided fair dice is rolled once. The sum of the numbers rolled determines the diameter of a circle. What is the probability that the numerical value of the area of the circle is less than the numerical value of the circle's circumference? $\textbf{(A)}\,\frac{1}{36} \qquad\textbf{(B)}\,\frac{1}{12} \qquad\textbf{(C)}\,\frac{1}{6} \qquad\textbf{(D)}\,\frac{1}{4} \qquad\textbf{(E)}\,\frac{5}{18}$

Circles $\Omega $ and $\omega $ are tangent at a point $P$ ($\omega $ lies inside $\Omega $). A chord $AB$ of $\Omega $ is tangent to $\omega $ at $C;$ the line $PC$ meets $\Omega $ again at $Q.$ Chords $QR$ and $QS$ of $ \Omega $ are tangent to $\omega .$ Let $I,X,$ and $Y$ be the incenters of the triangles $APB,$ $ARB,$ and $ASB,$ respectively. Prove that $\angle PXI+\angle PYI=90^{\circ }.$

Suppose $(a_n)$, $(b_n)$, $(c_n)$ are arithmetic progressions. Given that $a_1+b_1+c_1 = 0$ and $a_2+b_2+c_2 = 1$, compute $a_{2014}+b_{2014}+c_{2014}$. [i]Proposed by Evan Chen[/i]

Given two concentric circles and a pair of parallel lines. Find the locus of the fourth vertices of all rectangles with three vertices on the concentric circles, two vertices on one circle and the third on the other and with sides parallel to the given lines.

Real numbers $a, b, c$ are not equal $0$ and are solution of the system: $\begin{cases} a^2 + a = b^2 \\ b^2 + b = c^2 \\ c^2 +c = a^2 \end{cases}$ Prove that $(a - b)(b - c)(c - a) = 1$.

Let $A$ be one of the two points where the circles whose centers are the points $M$ and $N$ intersect. The tangents in $A$ to such circles intersect them again in $B$ and $C$, respectively. Let $P$ be a point such that the quadrilateral $AMPN$ is a parallelogram. Show that $P$ is the circumcenter of triangle $ABC$.

Let $l$ be the tangent line at the point $P(s,\ t)$ on a circle $C:x^2+y^2=1$. Denote by $m$ the line passing through the point $(1,\ 0)$, parallel to $l$. Let the line $m$ intersects the circle $C$ at $P'$ other than the point $(1,\ 0)$. Note : if $m$ is the line $x=1$, then $P'$ is considered as $(1,\ 0)$. Call $T$ the operation such that the point $P'(s',\ t')$ is obtained from the point $P(s,\ t)$ on $C$. (1) Express $s',\ t'$ as the polynomials of $s$ and $t$ respectively. (2) Let $P_n$ be the point obtained by $n$ operations of $T$ for $P$. For $P\left(\frac{\sqrt{3}}{2},\ \frac{1}{2}\right)$, plot the points $P_1,\ P_2$ and $P_3$. (3) For a positive integer $n$, find the number of $P$ such that $P_n=P$.

Let $x_1=y_1=x_2=y_2=1$, then for $n\geq 3$ let $x_n=x_{n-1}y_{n-2}+x_{n-2}y_{n-1}$ and $y_n=y_{n-1}y_{n-2}-x_{n-1}x_{n-2}$. What are the last two digits of $|x_{2012}|?$