Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

Click for solution Here is my candidate for the solution with the most overkill. We will use the following results from graph theory. Dirac's Condition: Let $G$ be a graph with $v \ge 3$ vertices. If every vertex has degree at least $\frac{v}{2}$, then $G$ has a Hamiltonian cycle. Chvatal's Condition: Let $G$ be a graph with $v$ vertices ($v$ odd). If every vertex has degree at least $\frac{v-1}{2}$, and at most $\frac{v-1}{2}$ vertices have degree exactly $\frac{v-1}{2}$, then $G$ has a Hamiltonian cycle. We can check that the divisor graph obeys one of these two conditions, provided that $n$ is not the product of two distinct primes. Can you find a solution with more overkill?

Prove that the system \begin{align*} x^6+x^3+x^3y+y & = 147^{157} \\ x^3+x^3y+y^2+y+z^9 & = 157^{147} \end{align*} has no solutions in integers $x$, $y$, and $z$.

Click for solution Here's a solution. First, add and subtract the equations to get $(x^3+y+1)^2-1+z^9=147^{157}-157^{147}$ $(x^3-y)(x^3+y)-z^9=147^{157}-157^{147}$ Now, assume that $x,y,z$ are a solution and work mod 19. $147^{157}\equiv2$ and $157^{147}\equiv11,$ so $(x^3+y+1)^2+z^9\equiv14$, Since 9th powers are congruent to $\pm1$, either $(x^3+y+1)^2\equiv13$ or $(x^3+y+1)^2\equiv15$. Neither of these values is a square mod 19, so there is no solution and we are done. Edit- I'm having trouble calculating. My previous argument used the wrong value for $147^{157}$. Since it worked, I didn't realize it was wrong at the time.

Let $ABC$ be an acute-angled triangle, and let $P$ and $Q$ be two points on its side $BC$. Construct a point $C_{1}$ in such a way that the convex quadrilateral $APBC_{1}$ is cyclic, $QC_{1}\parallel CA$, and $C_{1}$ and $Q$ lie on opposite sides of line $AB$. Construct a point $B_{1}$ in such a way that the convex quadrilateral $APCB_{1}$ is cyclic, $QB_{1}\parallel BA$, and $B_{1}$ and $Q$ lie on opposite sides of line $AC$. Prove that the points $B_{1}$, $C_{1}$, $P$, and $Q$ lie on a circle.

Click for solution Myth has already solved some of them, so I guess that if there's any harm to be done here then it's already done . Assume we have shown that $A,B_1,C_1$ are collinear. Then the result would follow, since $\angle B_1C_1P=\angle AC_1P=\angle ABP=\angle B_1QC=\pi-\angle B_1QP$. Now, in order to show that $A,B_1,C_1$ are collinear, we can work in reverse: given $B_1,C_1$ on the circles s.t. $B_1,A,C_1$ are collinear, we construct the paralleles through $C_1$ to $AC$ and through $B_1$ to $AB$ so that they cut $AB,AC$ respectively. Let these intersect at $Q$. From a quick angle chase we find $BC_1\|CB_1$, so the hexagon $ABC_1QB_1C$ is isncribed in a conic. Since this conic passes through $A,B_1,C_1$ which are collinear, and also through $B,C$, it must be the union of $B_1,C_1,BC$, so $Q\in BC$. Now, if we make $B_1C_1$ the tangent to $(APB)$, then $Q=B$, and if we make it the tangent to $(APC)$, then $Q=C$, so $Q$ will go along the entire edge $BC$.

Legs $L_1, L_2, L_3, L_4$ of a square table each have length $n$, where $n$ is a positive integer. For how many ordered 4-tuples $(k_1, k_2, k_3, k_4)$ of nonnegative integers can we cut a piece of length $k_i$ from the end of leg $L_i \; (i=1,2,3,4)$ and still have a stable table? (The table is stable if it can be placed so that all four of the leg ends touch the floor. Note that a cut leg of length 0 is permitted.)

Click for solution here's how i did number 4, it's essentially the same as everyone else's method: let Lx be the length of leg x, and Px be the endpoint of leg x. say that L1 is directly across from L3(diagonally). in order for the table to be stable, the line that passes through P1 and P2 must be paralell to the line that passes through P3 and P4. the condition L2 - L1 = L3 - L4 ensures that the 4 points are coplanar let the difference L2 - L1 = m since the problem states that each leg can either be cut entirely, not cut, or cut integrally, m must be an integer on the domain [0,n] if there are two adjacents legs with length n, then there are (1+n-m) different cuts that will produce this difference. the pair of legs opposite these two must have the same difference, but can still be cut in any of the (1+n-m) ways. thus we take the following sum: sum of (1+n-m)^2 from m=0 to m=n since we have restricted m to be greater than or equal to zero, we have neglected to count the cases in which L1 is greater than L2. thus we multiply the sum by two, for there are just as many cases in which L2>L1 as those in which L1>L2. but what about when m=0? at m=0 the expression only needs to be counted once, thus to avoid overcounting, we subtract the number of cases in which m=0 (there are (1+n)^2 such cases. if we examine the sum of (1+n-m)^2 from m=0 to m=n, we note that the first term will be (1+n)^2 and the last term 1^2. so this is essentially the same as the sum of the first (1+n) squares. plugging into the formula x(x+1)(2x+1)/6 and performing the said process to count accurately, we have: 2*(n+1)(n+2)(2n+3)/6 - (1+n)^2 = (n+1)(n+2)(2n+3)/3 - (1+n)2 =[(n^2+3n+2)(2n+3)-3(n^2+2n+1)]/3 =(2n^3+3n^2+6n^2+9n+4n+6-3n^2-6n-3)/3 =(2n^3 + 6n^2 +7n + 3)/3

Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a balancing line if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side. Prove that there exist at least two balancing lines.

Click for solution Hmm... A strange problem. Consider a convex hull of the whole set. If it contains red and blue points then, obviously, we are done. Therefore suppose the convex hull consists of blue points only. Take $A,B,C$ three consecutive vertices on the convex hull. We state there is a balancing $A$ through $A$. Indeed, consider the leftmost line $k$ through $A$ s.t. the right open halfplane contains the same number of red and blue points . The line $k$ exists due to discrete continuity arguments (just rotate $k$ from $AB$ towards to $AC$). We know that $k$ contains a point $D$ from our set. If $D$ is a red point then we are done. If $D$ is a blue point, then there is another line between $AB$ and $k$ satisfying the condition . Contradiction. Since the convex hull contains at least three points we conclude that there are at least three balancing lines for this case. Please, someone read it! I think I missed something

For $m$ a positive integer, let $s(m)$ be the sum of the digits of $m$. For $n\ge 2$, let $f(n)$ be the minimal $k$ for which there exists a set $S$ of $n$ positive integers such that $s\left(\sum_{x\in X} x\right)=k$ for any nonempty subset $X\subset S$. Prove that there are constants $0<C_1<C_2$ with \[C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n.\]

These problems are copyright $\copyright$ Mathematical Association of America.