Day two of that Putnam
by Wolstenholme, Aug 8, 2015, 7:35 AM














solution
Basically try every combination of
except for
and count the number of times
is odd. It's easy to bash out that you get
odd results in total and so by the pigeonhole principle one of your seven choices of
works. Probabilistic method yay!






![\[ \dfrac {\text {gcd}(m, n)}{n} \dbinom {n}{m} \]](http://latex.artofproblemsolving.com/c/0/a/c0a6877cd49e904728b24e7743fe8021efd6d312.png)

solution
What a troll - By Bezout's Theorem there exist integers
such that
so our expression is equal to
![\[ \frac{am + bn}{n}\binom{n}{m} = b\binom{n}{m} + a\binom{n - 1}{m - 1} \]](//latex.artofproblemsolving.com/0/6/d/06d84438ad75704bc64860571133424d4385b0f5.png)
which is clearly an integer.


![\[ \frac{am + bn}{n}\binom{n}{m} = b\binom{n}{m} + a\binom{n - 1}{m - 1} \]](http://latex.artofproblemsolving.com/0/6/d/06d84438ad75704bc64860571133424d4385b0f5.png)
which is clearly an integer.






solution
It's clear that for all
we have that
and so since
is continuous we must have
. Now consider any
. Let
be a number such that
. It's clear that
and iterating we have that if
for any
then
. But numbers of the form
for
are clearly dense in
(since we can make
arbitrarily large) so since
for each of these choices of
by continuity we have that
over the interval
as desired.


















![$[-1, 1]$](http://latex.artofproblemsolving.com/5/c/3/5c3818b9565a33fd3aadba10026d32c5e3eea90f.png)










solution
Generating functions! Let
and let
. Using analogous notation for the generating functions of the other sets it's easy to see that
hence
. Now if
is a power of two by the Frobenius endomorphism we have
which is clearly equivalent to the problem condition so since there are infinitely many powers of two we are done.













solution
Another trivial expected value problem, as a B6 this time! Basically note that if we have a some point
consider the
points (let's call them the
-chipotle points) obtained by switching the sign of one of the coordinates of our point. It's clear that every two such chipotle points have distance
away from each other. Now we note that the expected value of
-chipotle points for a random point
is greater than
so for some
there must be an equilateral triangle among its
-chipotle points.
Essentially the problem boils down to the very deep fact that
.









Essentially the problem boils down to the very deep fact that

Well I'd say I got at least a 101 on this Putnam!!!! The overall first place score in 2000 was 96....darn wish I could take it haha
