Various Putnam Seminar Problems
by djmathman, Sep 15, 2016, 3:22 PM
Week 1 (Introduction) Problem 4 wrote:
, 
, 
are points of a fixed ellipse 
. Show that the area of 
is maximized when the centroid of is at the center of .Solution
Consider a linear transformation which sends the ellipse 
to a circle 
. Let 
denote the image of 
under this transformation, and define 
and 
similarly. Note that ratios of areas are preserved, so in particular ![$[A'B'C']/[\Omega] = [ABC]/[E]$](//latex.artofproblemsolving.com/f/9/5/f9593a5224c12d2ef6945318c9dd6c1c98984757.png)
. Hence, it suffices to consider what happens when the ellipse is a circle and then adjust accordingly.
I claim that the maximum area of
occurs when it is equilateral. To prove this, use standard triangle notation, and recall that by the Extended Law of Sines 
, and similarly for 
and 
. Thus, ![\[\dfrac{abc}{\sin A\sin B\sin C} = 8R^3 \quad\implies\quad 2R^2\sin A\sin B\sin C = \dfrac{abc}{4R} = K.\]](//latex.artofproblemsolving.com/f/8/5/f8553866284ead9be716d9bf4f35dd4a5637ea37.png)
Hence it suffices to maximize 
. Let 
denote the value of this expression, and note that 
. Now recall that ![\[\dfrac{d}{dx}(\ln \sin x) = \dfrac{\cos x}{\sin x} = \cot x\quad\text{and}\quad \dfrac{d^2}{dx^2}(\ln\sin x) = -\csc^2 x,\]](//latex.artofproblemsolving.com/8/e/1/8e108ce6d8ad83ad923901186ccdac722dc64721.png)
so 
is concave down in the interval 
. Thus, we may apply Jensen's Inequality to get that ![\[\dfrac{\ln\sin A + \ln\sin B + \ln\sin C}3\leq\ln\sin\left(\dfrac{A+B+C}3\right) = \ln\sin\dfrac{\pi}3 = \ln \dfrac{\sqrt 3}2,\]](//latex.artofproblemsolving.com/e/0/4/e04f2fb6e2ec1d09c811913fd614296c9c12d3ad.png)
from which 
. Equality is achieved when the triangle is equilateral, so we're good.
Now perform the transformation back to the original ellipse. I claim that the centroid of is taken to the centroid of 
under this tranformation. To prove this, let 
be a linear transformation, and just note that ![\[f\left(\dfrac{A+B+C}3\right) = \dfrac{f(A) + f(B) + f(C)}3.\]](//latex.artofproblemsolving.com/3/1/5/3153dbd7826cc7009f84b70bb6b2acfbda07ed6d.png)
Now just note that the center of the circle is taken to the center of the ellipse, so indeed the centroid of the triangle lies on the center of the ellipse as desired.
to a circle 
. Let 
denote the image of under this transformation, and define 
and 
similarly. Note that ratios of areas are preserved, so in particular ![$[A'B'C']/[\Omega] = [ABC]/[E]$](http://latex.artofproblemsolving.com/f/9/5/f9593a5224c12d2ef6945318c9dd6c1c98984757.png)
. Hence, it suffices to consider what happens when the ellipse is a circle and then adjust accordingly.I claim that the maximum area of
occurs when it is equilateral. To prove this, use standard triangle notation, and recall that by the Extended Law of Sines 
, and similarly for 
and 
. Thus, ![\[\dfrac{abc}{\sin A\sin B\sin C} = 8R^3 \quad\implies\quad 2R^2\sin A\sin B\sin C = \dfrac{abc}{4R} = K.\]](http://latex.artofproblemsolving.com/f/8/5/f8553866284ead9be716d9bf4f35dd4a5637ea37.png)
Hence it suffices to maximize 
. Let 
denote the value of this expression, and note that 
. Now recall that ![\[\dfrac{d}{dx}(\ln \sin x) = \dfrac{\cos x}{\sin x} = \cot x\quad\text{and}\quad \dfrac{d^2}{dx^2}(\ln\sin x) = -\csc^2 x,\]](http://latex.artofproblemsolving.com/8/e/1/8e108ce6d8ad83ad923901186ccdac722dc64721.png)
so 
is concave down in the interval 
. Thus, we may apply Jensen's Inequality to get that ![\[\dfrac{\ln\sin A + \ln\sin B + \ln\sin C}3\leq\ln\sin\left(\dfrac{A+B+C}3\right) = \ln\sin\dfrac{\pi}3 = \ln \dfrac{\sqrt 3}2,\]](http://latex.artofproblemsolving.com/e/0/4/e04f2fb6e2ec1d09c811913fd614296c9c12d3ad.png)
from which 
. Equality is achieved when the triangle is equilateral, so we're good.Now perform the transformation back to the original ellipse
. I claim that the centroid of is taken to the centroid of 
under this tranformation. To prove this, let 
be a linear transformation, and just note that ![\[f\left(\dfrac{A+B+C}3\right) = \dfrac{f(A) + f(B) + f(C)}3.\]](http://latex.artofproblemsolving.com/3/1/5/3153dbd7826cc7009f84b70bb6b2acfbda07ed6d.png)
Now just note that the center of the circle is taken to the center of the ellipse, so indeed the centroid of the triangle lies on the center of the ellipse as desired.Week 2 (Polynomials) Problem 5 wrote:
The polynomial 
has complex coefficients, and is such that 
whenever 
. Show that 
.
has complex coefficients, and is such that 
whenever 
. Show that 
.Suppose that 
whenever . Note that since 
, we may also say that 
. Now recall that for any two complex numbers 
and 
we have 
. This means that 
As a result, we know that 
is constant for all points 
on the unit circle, which is to say that 
is constant for all points on the unit circle.
Now choose three points on the unit circle, say
, 
, and 
. The circumcenter of 
is the origin. As a result, the circumcenter of 
, where 
for 
, is the complex number . But we know that 
, and so the circumcenter of this triangle is also the origin. Since the circumcenter of any triangle is unique, we obtain 
.
This means that![\[|z^2+az+b| = |z^2+az| =|z|\cdot|z+a| = |z+a| = 1\quad\text{for all }z.\]](//latex.artofproblemsolving.com/8/4/4/8440e29925b8270d959c92f1dab36961614dadc2.png)
A similar argument shows that 
as well, and we're done.
whenever . Note that since 
, we may also say that 
. Now recall that for any two complex numbers 
and 
we have 
. This means that 
As a result, we know that 
is constant for all points 
on the unit circle, which is to say that 
is constant for all points on the unit circle.Now choose three points on the unit circle, say
, 
, and 
. The circumcenter of 
is the origin. As a result, the circumcenter of 
, where 
for 
, is the complex number . But we know that 
, and so the circumcenter of this triangle is also the origin. Since the circumcenter of any triangle is unique, we obtain 
.This means that
![\[|z^2+az+b| = |z^2+az| =|z|\cdot|z+a| = |z+a| = 1\quad\text{for all }z.\]](http://latex.artofproblemsolving.com/8/4/4/8440e29925b8270d959c92f1dab36961614dadc2.png)
A similar argument shows that 
as well, and we're done.1998 Putnam B4 wrote:
Find necessary and sufficient conditions on positive integers 
and 
so that ![\[\sum_{i=0}^{mn-1}(-1)^{\lfloor i/m\rfloor+\lfloor i/n\rfloor}=0.\]](//latex.artofproblemsolving.com/4/6/3/4639037fefe4eb32ec2fde811d7d108f8bf18b20.png)
and 
so that ![\[\sum_{i=0}^{mn-1}(-1)^{\lfloor i/m\rfloor+\lfloor i/n\rfloor}=0.\]](http://latex.artofproblemsolving.com/4/6/3/4639037fefe4eb32ec2fde811d7d108f8bf18b20.png)
I posted this on the fora two weeks ago but w/e
This is more of a sketch rather than a full-on rigorous proof; some of the parts toward the end are very difficult to explain formally, and I doubt I would get full credit on this if it showed up on the actual exam.
I claim that the sum is equal to zero iff
is even.
Let
denote the set of integers 
for which 
is odd, and 
denote the set of integers for which is even. For this sum to equal zero, we need 
. This means that the number of elements in the sum must be even, so 
is even.
First tackle the case where
. WLOG let be even and be odd (although this is not really important). Consider the sequence of integers 
consisting of all integer multiples of or . For example, if 
and 
, the sequence would go ![\[0,4,7,8,12,14,16,20,21,24,28.\]](//latex.artofproblemsolving.com/1/5/6/15601468cc719d610ab1c24b604436912fdad08b.png)
For 
define 
. I claim that 
is the number of integers 
such that 
. This is not hard to see, since 
for all 
(from the fact that and are relatively prime).
Note that there must be an even number of terms in this sequence. To see this, remark that the only number in that list which is both a multiple of and a multiple of is , and so it follows that the number of elements in the list is 
. Since is even and is odd, is even.
Now I claim that this sequence is palindromic, i.e.
for all 
. Note that in fact the sequence of 
is symmetric about 
, since is a multiple of iff 
is a multiple of , and likewise for . Hence for any , ![\[a_i+a_{k-i} = a_{i+1} + a_{k-i-1}\implies a_{i+1}-a_i = a_{k-i} - a_{k-i-1} \implies b_i=b_{k-i}.\]](//latex.artofproblemsolving.com/5/1/6/5166853ee2bac4c5f7a7f08ef9d6f6fac5da732d.png)
Now just note that ![\[|\mathcal{A}| = b_1+b_3+\cdots+b_k\]](//latex.artofproblemsolving.com/a/5/d/a5d28c5fbd49f600cac0ce66ae0c848176343d0c.png)
and ![\[|\mathcal{B}| = b_0+b_2+\cdots+b_{k-1}.\]](//latex.artofproblemsolving.com/f/a/2/fa2a9efb8efe6cbb8b74f6d8f3a970f59301a04d.png)
By the above two paragraphs, these sums are equal. Thus, in the case, the sum is zero iff at least one of or is even, i.e. 
is even.
Now with this case under our belt, what happens when the two numbers share a common factor? This case is trickier; after all, the value of
will increase by 
whenever passes a multiple of 
. To tackle this, note that the only way the sum of floors can change value is when the input passes over a multiple of 
(since otherwise doesn't share any prime factors with either or ). Scaling down by (or in other words taking every group of consective integers and collecting them into one guy), we see that this sequence is equivalent to the first case for 
and 
respectively, repeated times.
If either one of these ratios is even, we're good, since the sum is zero in this subinterval and hence it'll be zero all the way from
to 
. If both of them are odd, we know that the sum can't be zero in each of the subsequences. But this does not immediately imply that the whole sum is zero! It's possible that each time the sequence of parities will alternate and in essence cancel each other out to get a zero sum at the end. In order for this to not happen, the sequence must both start and end with an even number; this way, the next sequence will start off being even and the discrepencies can compound rather than cancel. This is equivalent to showing that ![\[\left\lfloor\frac{\text{lcm}(m,n)}{m}\right\rfloor+\left\lfloor\frac{\text{lcm}(m,n)}{n}\right\rfloor=\frac{\text{lcm}(m,n)}{m}+\frac{\text{lcm}(m,n)}{n}\]](//latex.artofproblemsolving.com/7/e/1/7e137d77f576213df8f0bc4c8083b9141c27410d.png)
is even. This is actually not so bad! Recall that ![\[mn=\gcd(m,n)\text{lcm}(m,n)\quad\implies\quad \dfrac{m}{\gcd(m,n)} = \dfrac{\text{lcm}(m,n)}{n}.\]](//latex.artofproblemsolving.com/e/d/a/eda7c43d4a5e9b35600fdf14eb65b47576b362e9.png)
Since we assumed that 
is odd, 
must also be odd. Similarly, 
is odd. Hence the sum is even as desired.
As a result, we get that the sum is zero iff and are both even, which is equivalent to saying that ![\[\dfrac{mn}{\gcd(m,n)^2} = \dfrac{\gcd(m,n)\text{lcm}(m,n)}{\gcd(m,n)^2} = \dfrac{\text{lcm}(m,n)}{\gcd(m,n)}\]](//latex.artofproblemsolving.com/7/4/5/74534b8dfb3a05e0af3326d0b4996bb73909672f.png)
is even. 
I claim that the sum is equal to zero iff
is even.Let
denote the set of integers 
for which 
is odd, and 
denote the set of integers for which is even. For this sum to equal zero, we need 
. This means that the number of elements in the sum must be even, so 
is even.First tackle the case where
. WLOG let be even and be odd (although this is not really important). Consider the sequence of integers 
consisting of all integer multiples of or . For example, if 
and 
, the sequence would go ![\[0,4,7,8,12,14,16,20,21,24,28.\]](http://latex.artofproblemsolving.com/1/5/6/15601468cc719d610ab1c24b604436912fdad08b.png)
For 
define 
. I claim that 
is the number of integers 
such that 
. This is not hard to see, since 
for all 
(from the fact that and are relatively prime).Note that there must be an even number of terms in this sequence. To see this, remark that the only number in that list which is both a multiple of
and a multiple of is , and so it follows that the number of elements in the list is 
. Since is even and is odd, is even.Now I claim that this sequence is palindromic, i.e.
for all 
. Note that in fact the sequence of 
is symmetric about 
, since is a multiple of iff 
is a multiple of , and likewise for . Hence for any , ![\[a_i+a_{k-i} = a_{i+1} + a_{k-i-1}\implies a_{i+1}-a_i = a_{k-i} - a_{k-i-1} \implies b_i=b_{k-i}.\]](http://latex.artofproblemsolving.com/5/1/6/5166853ee2bac4c5f7a7f08ef9d6f6fac5da732d.png)
Now just note that ![\[|\mathcal{A}| = b_1+b_3+\cdots+b_k\]](http://latex.artofproblemsolving.com/a/5/d/a5d28c5fbd49f600cac0ce66ae0c848176343d0c.png)
and ![\[|\mathcal{B}| = b_0+b_2+\cdots+b_{k-1}.\]](http://latex.artofproblemsolving.com/f/a/2/fa2a9efb8efe6cbb8b74f6d8f3a970f59301a04d.png)
By the above two paragraphs, these sums are equal. Thus, in the case, the sum is zero iff at least one of or is even, i.e. 
is even.Now with this case under our belt, what happens when the two numbers share a common factor? This case is trickier; after all, the value of
will increase by 
whenever passes a multiple of 
. To tackle this, note that the only way the sum of floors can change value is when the input passes over a multiple of 
(since otherwise doesn't share any prime factors with either or ). Scaling down by (or in other words taking every group of consective integers and collecting them into one guy), we see that this sequence is equivalent to the first case for 
and 
respectively, repeated times.If either one of these ratios is even, we're good, since the sum is zero in this subinterval and hence it'll be zero all the way from
to 
. If both of them are odd, we know that the sum can't be zero in each of the subsequences. But this does not immediately imply that the whole sum is zero! It's possible that each time the sequence of parities will alternate and in essence cancel each other out to get a zero sum at the end. In order for this to not happen, the sequence must both start and end with an even number; this way, the next sequence will start off being even and the discrepencies can compound rather than cancel. This is equivalent to showing that ![\[\left\lfloor\frac{\text{lcm}(m,n)}{m}\right\rfloor+\left\lfloor\frac{\text{lcm}(m,n)}{n}\right\rfloor=\frac{\text{lcm}(m,n)}{m}+\frac{\text{lcm}(m,n)}{n}\]](http://latex.artofproblemsolving.com/7/e/1/7e137d77f576213df8f0bc4c8083b9141c27410d.png)
is even. This is actually not so bad! Recall that ![\[mn=\gcd(m,n)\text{lcm}(m,n)\quad\implies\quad \dfrac{m}{\gcd(m,n)} = \dfrac{\text{lcm}(m,n)}{n}.\]](http://latex.artofproblemsolving.com/e/d/a/eda7c43d4a5e9b35600fdf14eb65b47576b362e9.png)
Since we assumed that 
is odd, 
must also be odd. Similarly, 
is odd. Hence the sum is even as desired.As a result, we get that the sum is zero iff
and are both even, which is equivalent to saying that ![\[\dfrac{mn}{\gcd(m,n)^2} = \dfrac{\gcd(m,n)\text{lcm}(m,n)}{\gcd(m,n)^2} = \dfrac{\text{lcm}(m,n)}{\gcd(m,n)}\]](http://latex.artofproblemsolving.com/7/4/5/74534b8dfb3a05e0af3326d0b4996bb73909672f.png)
is even. 
April 2025
November 2024