# Pi Mu Epsilon Undergraduate Math Society at USC Fall 2009 Semester

Wednesday, September 2. About 25 people showed up.

After a general introduction, talked about using induction to prove various statements. Here are the problems that were discussed:

1. Prove that 1+3+...+(2n-1)=n^2
2. Prove that n(2n^2-3n+1) is divisible by 6 for all n=1,2,3...
3. Prove that n squares can be cut into finitely many pieces so that the pieces can be put together to form a single square.
For the first problem, several solutions were discussed, with or without induction. For the second, the key observation is that 2n^2-3n+1=(n-1)(2n-1), and then, beside induction, one can use the relation 1+2^2+3^2+...+(n-1)^2=n(n-1)(2n-1)/6 or note that n(n-1) is always divisible by 2, while n(n-1)(2n-1) is always divisible by 3. For the last problem, it appears that it is enough to show the result for n=2 (then one can easily use induction: for n+1 squares, cut the first n and make a square, and then cut it, together with the square number n+1 to make one square), but for now making one square out of two remains an open problem. Other topics included basic modula arithmetic and applications of the base 2 representation of a number.

Wednesday, September 9. About 20 people showed up.

With a joint effort, we solved the following problems:
1: let ((k)) denote 1/sqrt(k). Then, prove that ((1))+((2))+((3))+...+((n))<2sqrt(n)
2: prove that 2!4!...(2n)!>=((n+1)!)^n
3: prove that the equation x^2 + y^2 = z^n has a solution in positive integers (x,y,z) for all n=1,2,3...
4: for all x in the interval [0,pi], prove that |sin(nx)| is at most n*sin(x), n a nonnegative integer
5: let ak>=1prove that 2^(n-1)(a1*a2*...*an +1)>=(1+a1)(1+a2)...(1+an)
(these were suggested by Phillip Adkins after our first meeting)

Then we had a short discussion of the Fibonacci numbers, including history and the closed-form expression.

Wednesday, September 16. About 10 people showed up.

With a joint effort, we established the following results about the Fibonacci numbers f_n, n=0,1,2,...:
(*) f_(n+m)=f_{n-1}f_m+f_nf_{m+1} (use induction on m)
(a) if m divides n then f_m divides f_n (hint: write n=mk and do induction on k; use (*))
(b) f_n is even if and only if n is divisible by 3
(c) f_n is divisible by 4 if and only if n is divisible by 6
(d) f_n is divisible by 5 if and only if n is divisible by 5
(e) f_n is divisible by 7 if and only if n is divisible by 8
(f) If n divides a single Fibonacci number then it divides infinitely many Fibonacci numbers
(g) for every integer m, the first m^2-1 Fibonacci numbers contain at least one that is divisible by m.

Note that (b)--(f) all follow from (*).

Next time we will discuss inequalities. You can prepare by reading this. Rearrangement inequality is one of the more popular ones at competitions.

Wednesday, September 23. About 10 people showed up.

I was away. Jerome and Patrick took the lead discussing inequalities and the MAA problems 11446-11452.

Wednesday, September 30. About 10 people showed up.

Continued our discussion of inequalities. Made some progress on MAA number 11448 (by connecting it to the rearrangement inequality) and 11449 (by conjecturing that the numbers should be positive)

Wednesday, October 8. About 10 people showed up.

The topic was the pigeonhole principle. Discussed several problems involving divisability (e.g. in any collection of n+1 integers, there are always two whose difference is divisible by n) The following problems are suggested for the next meeting.
1. Show that, in every group of n people, there are two who know the same number (at least one) of people in the group.
2. Each of 500 boxes contains at most 240 apples, and none is empty. Show that at least three boxes contain the same number of apples.
3. There are 17 participants in an international conference. Each participant knows not more than three languages and every two participants have a language in common. Show that at least three participants know the same language.
4. Several circles, with total length 10 are inside a unit square. Show that there exists a line passing through at least four circles.
5. Five points are inside an equilateral triangle with side 1. Show that two of those points are less than 1/2 unit apart.
6. There are 25 points in the plane, and any two points out of every three are less than 1 unit apart. Show that there exists a unit disk containing at least 13 of those points.
7. m^3+1 points are inside the unit cube. Show that there are two points less than \sqrt{3}/m units apart.
8. Show that every convex 2n-gon contains a diagonal that is not parallel to any of the sides.
9. Show that every nine-gon has two diagonals such that the angle between them is less than 7 degrees.
10. Show that every set of 2^{n+1}-1 integers contains a subset of size 2^n such that the sum of its elements is divisible by 2^n.
11. 30 teams are playing in a soccer tournament. Show that, at every moment, there are two teams with the same number of games played.
12. Let n_1, n_2, n_3 be three prime numbers, all bigger than 3. Show that either the sum or the difference of two of them is divisible by 12.

Wednesday, October 14. About 10 people showed up.

We discussed problems 3,4,5,11,12 from the above list.

Wednesday, October 21. About 5 people showed up (Mid-term season...).

We discussed two classes of Diophantine equations for which a complete theory exists: equations in one variable and linear equations. The rational roots of the equation $a_0+a_1x+\ldots+a_nx^n=0$ can only be of the form $x=p/q$, where $p$ is a divisor of constant term $a_0$ and $q>0$ is a divisor of the highest order coefficient $a_n$; $p$ can be either positive or negative; $p$ and $q$ should be relatively prime; $p$ can be $\pm 1$ and $\pm a_0$; $q$ can be $1$ and $a_n$. For integer solutions, consider only $q=1$. The integer roots of $a_1x_1+\ldots +a_nx_n=b$ exist if and only if the greatest common divisor of $a_1, \ldots, a_n$ divides $b$. In that case, we always have an $n-1$-parameter family of solutions. To get the family, transform the equation to get one of the coefficients $a_i$ equal to $\pm 1$. Then all the other variables become parameters. The correctness of the answer is usually easy to check; many different parameterizations of the same answer exist. Note that the corresponding homogeneous equations is always solvable and has an $n-1$-parameter family of solutions. Thus, an inhomogeneous equation either has no solutions or has infinitely many. As a practice before the next meeting, find the integer solutions of the following equations:
$x^8+x^7+x+1=0.$
$x^3+(x+1)^3+(x+2)^3=(x+3)^3.$
$x^4-4x^3-13x^2+28x+12=0.$
$127x-52y+1=0.$
$6x+10y-7z=11.$

Wednesday, October 28. 4 people showed up

Jerome lead the discussion about Pell's equation x^2-ny^2=1, where n is not a perfect square. The summary is as follows: the equation has infinitely many integer solutions (x_k,y_k), all generated by the fundamental solution (x_1,y_1) either by writing x_k+\sqrt{n}y_k=(x_1+\sqrt{n}y_1)^k or by multiplying suitable 2-by-2 matrices; the fundamental solution is obtained from the continued fraction expansion of \sqrt{n}. Also, Pell had little, if anything, to do with the equation: the name was assigned by Euler by mistake.

Wednesday, October 28. 5 people showed up

We finished with the Diophantine equations. Some of the tricks that can help to solve them are (1) Factoring the equation (2) Using parity and similar arguments, in particular, to run infinite ascent or descent (3) Using inequalities to reduce the number of possibilities.

Here are some problems for practice (suggested by Richard Mu):

prove that there exists no integer triples $(x,y,z)$ such that $x^4 + y^4 = z^2$.
How many distinct pairs of positive integers $(x,y)$ with y bigger than x satisfy $\sqrt{1984} = \sqrt{x} + \sqrt{y}$?
Solve the equation $1! + 2! + 3! +...+ x! = y^2$ for integer pairs $(x,y)$
Show that $14x^2 + 15y^2 = 7^{1990}$ has no solution in non-negative integers $x$ and $y$.

Next time we will start functional equations. The discussion will be based on the following notes: