Number of solutions to modular equation

Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.

Solution

We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.

First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.

Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.

Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).

Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.

In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.

Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.

Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.

a,b,c integers and cubic number

Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.

Solution

We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.

Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.

Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.

If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.

Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.

Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.

Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.

Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.

Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.

For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.

A non-trivial example is $a=1,b=2,c=4$.

Triangle Inequality

Given a triangle $ABC$ and a point $M$ inside the triangle.

Let $\alpha = \angle BMC, \beta = \angle AMC, \gamma = \angle AMB$

Prove that:
$$\frac{AM}{BM.CM} + \frac{BM}{CM.AM} + \frac{CM}{AM.BM} \geq -2 \left( \frac{\cos \alpha}{AM} + \frac{\cos \beta}{BM} + \frac{\cos \gamma}{CM} \right)$$

Solution In Progress

Let
$a = \frac{AM}{\sin \alpha}, b = \frac{BM}{\sin \beta}, c = \frac{CM}{\sin \gamma}$

Because $M$ is in the interior of the triangle, then $0 < \alpha, \beta, \gamma < \pi$ and thus $0 < \sin \alpha, \sin \beta, \sin \gamma \leq 1$. Thus $a,b,c > 0$. Without loss of generality, we may assume that $a \geq b \geq c$.

So we have:
$AM = a \sin \alpha, BM = b \sin \beta, CM = c \sin \gamma$

Substitute it to our inequality, and use the following shorthand:

$C_\alpha = \cos \alpha \sin \beta \sin \gamma$
$C_\beta = \sin \alpha \cos \beta \sin \gamma$
$C_\gamma = \sin \alpha \sin \beta \cos \gamma$

So our inequality becomes
$$ \iff a^2\sin^2 \alpha + b^2 \sin^2 \beta + c^2 \sin^2 \gamma +2 ( bc C_\alpha + ac C_\beta + ab C_\gamma ) \geq 0$$

Note the following identities:
$$C_\beta + C_\gamma = \sin \alpha \cos \beta \sin \gamma + \sin \alpha \sin \beta \cos \gamma = \sin \alpha \sin (\beta + \gamma) = \sin \alpha \sin (2 \pi - (\beta + \gamma)) = - \sin^2 \alpha$$

Similarly,
$$C_\alpha + C_\gamma = - \sin^2 \beta$$
$$C_\alpha + C_\beta = - \sin^2 \gamma$$

So that
$$C_\alpha = (\sin^2 \alpha - \sin^2 \beta - \sin^2 \gamma)/2$$
$$C_\beta = (\sin^2 \beta - \sin^2 \alpha - \sin^2 \gamma)/2$$
$$C_\gamma = (\sin^2 \gamma - \sin^2 \beta - \sin^2 \alpha)/2$$

Substituting back to our inequalities, we have:
$$\iff (a-b)(a-c)\sin^2 \alpha + (b-a)(b-c) \sin^2 \beta + (c-a)(c-b) \sin^2 \gamma \geq 0$$

It's also equivalent to:
$$\iff (a-b)^2 C_\gamma + (a-c)^2 C_\beta + (b-c)^2 C_\alpha \leq 0$$

Happy Saint Math Trick's Day

This problem is inspired by this comic.

Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$

Solution: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html

Osculating Circle, Ellipse, and Cone

An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point

In other words, it is a second-degree approximation circle of the curve at that point.

http://en.wikipedia.org/wiki/Osculating_circle

Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.

If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.

Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.

Solution:
http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html

Second Solution:
http://dharmath.blogspot.com/2010/03/second-solution-osculating-circle.html

Paired cards

A standard deck of 52 cards is shuffled with uniform probability. A "pair" is defined as two numerically identical cards that are adjacent in the stack. What is the probability that the deck contains no pair?

Challenge: Find the probability that the deck contains exactly $n$ pair for $n=1,2,\cdots,26$.

Coupon drawing

Credit for this problem goes to Sander Parawira

A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?

Solution here: http://dharmath.thehendrata.com/2010/01/12/solution-coupon-drawing/

Inequality

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

solution: http://dharmath.thehendrata.com/2009/12/02/solution-inequality/

Solution: Integer Inequality

Original problem: http://dharmath.thehendrata.com/2009/11/27/integer-inequality/

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Integer Inequality

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-integer-inequality/

3 Variable Inequality

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-3-variable-inequality/

Triangle Inequality

Given $n$ right triangles each with sides $a_i, b_i, c_i$, with $c_i$ being the hypotenuse ($i=1,\cdots, n)$. Let $A = \sum a_i, B = \sum b_i, C= \sum c_i$.

Prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{\sqrt{A^2+B^2}}$

Harder version: prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{C}$

3 Sequence Inequality

If $a_i, b_i, c_i$ are sequences of positive numbers for $i = 1,2,\cdots,n$, prove the following inequality:

$\sum (a_i+b_i+c_i) \sum \frac{a_ib_i + b_ic_i+ c_ia_i}{a_i+b_i+c_i} \sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i+ c_ia_i} \leq \sum a_i \sum b_i \sum c_i$

where all summations are taken from $i=1$ to $i=n$. When does equality happen?

ABC String

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

Divide Colored Balls

There are $2n$ balls of each color: red, green, and blue. How many ways are there to divide them into two groups such that each group has $3n$ balls?

First Solution

It is the same as the coefficient of $3n$ in the expansion $(1+x+x^2+x^3+\cdots+x^{2n})^3$. The proof is left to the readers as an exercise.


Note that $(1+x+\cdots+x^{2n})^3 = \frac{(1-x^{2n+1})^3}{(1-x)^3} = (1 - 3x^{2n+1} + 3x^{4n+2} - x^{6n+3})(1-x)^{-3}$

But $(1-x)^{-3} = (1+3x + 6x^2 + 10x^3 + \cdots + \frac{(k+2)(k+1)}{2}x^k + cdots)$

So the coefficient of $3n$ in that expansion is:

$\frac{(3n+2)(3n+1)}{2} - 3\frac{n(n+1)}{2} = 3n^2 + 3n + 1$

Second Solution

We shall prove that there are $3n^2+3n+1 = (n+1)^3 - n^3$ ways, which has striking geometrical interpretations.

Create an equilateral triangle with altitude $3n$, and mark all the points that has integer distance to all the sides. These points will form a triangular lattice

It is a well-known fact that for any point in an equilateral triangle, the sum of distances to the sides is constant. Since the altitude of the triangle is $3n$, then for any point in that triangular lattice, the sum of distance to the sides is $3n$. Furthermore, the distances are integers. Thus, these points represent the number of ways to choose $3n$ balls from 3 colors.

However, the constraint that we only have $2n$ supply of each color is not yet enforced. We examine the points in the lattice whose distance to any of the sides is greater than $2n$, and we eliminate them. So we are left with a hexagonal lattice of side $n+1$. This is the projection of a half-shell of an $n+1$-cube that has $n$-cube carved out of it.

Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

Passengers Boarding Airplane, Part Deux

2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$

Combinatorial Sum Identity

For $m,n > 0$ prove that

$\displaystyle 1 + \sum_{k=1}^{m} \binom{k+n}{k} = \binom{m+n+1}{m}$

Harder version:

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{m+n+1}{n+1} - \binom{n+l}{n+1}$

Boys and Girls around the table

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.