Day 2 had a bunch of really nice problems with more advanced techniques required to solve them. Problem 6 is also hard and I will be writing it up at a later time.
Problem 4: A site is any point in the plane such that and are both positive integers less than or equal to .
Initially, each of the sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to . On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance fromany other occupied site.) They stop as soon as a player cannot place a stone.
Find the greatest such that Amy can ensure that she places at least red stones, no matter how Ben places his blue stones.
Solution 4: The given condition is equivalent to placing knights on a chessboard, with one party blocking a space every other turn. It is well known that on a chessboard, you can place knights by placing knights in the black squares in the rows, and this is easily discoverable by playing around with placements a for a bit. Thus, if Ben blocks a placement every other turn, we can only place pieces on half of the squares described above, so for the case in a board, we conjecture that .
It remains to show that is indeed impossible. To do this, we show that , or that Ben can play in a way such that Amy can only place at most stones. To do this, we study the grid (tiled times) as distinct -cycles as follows:
If Amy places a stone in , Ben will place his stone in the opposite corner of . This ensures that Amy can no longer place any more stones in . Since there are regions per grid, Amy can only place stones per grid. Thus, Amy can place at maximum of stones if Bob plays in this manner and we are done.
Problem 5: Let be an infinite sequence of positive integers. Suppose that there is an integer such that for each , the number
is an integer. Prove that there is a positive integer such that for all .
Solution 5: The key to this problem is to use a size argument on -adic valuations to guarantee convergence of the . We consider two consecutive sums, whose difference
must be an integer because the two sums are integers. Let where are defined as but . This is the standard -adic valuation. Note that because this difference is an integer, its -adic valuation must be non-negative. This is a fact that will used repeatedly.
Now for all primes , consider
- . Then for all . Else the difference cannot be integral, which can be seen from the inequality . We have equality when the two things inside the are unequal, and the second element is most definitely non-negative whereas if the first element is negative then they are clearly not equal.
. In this case we claim eventually becomes constant. There are a few cases to consider here.
Suppose for some . We claim that for all , or that is eventually non-increasing and bounded below by so it must eventually be constant.
For this case, we have , meaning that the remaining terms in the difference must also satisfy
The trick here is to figure out where goes. If , then which is bad because . Else if , then which is also bad because . We start at the base case and inductively go onwards to show this for all .
Suppose the opposite and that for all . Then for any , we have
We also wish to rank somewhere between and to get eventual constant-ness. We claim that
Clearly is impossible by assumption, so we wish to invalidate the case . In this case, we have so in order for the of the difference to be non-negative, the of the other two terms must agree, or
a contradiction. Thus by induction (again) we have shown that is eventually constant.
Combining both these claims yields the desired result. For each of the finitely many primes dividing , eventually becomes constant. That COMBINED WITH the fact for all implies for all eventually and because of this, must be constant.
A caveat as noted by v_Enhance, we need the non-increasing condition in the first claim because otherwise setting where is a good sequence and is the -th prime causes a contradiction!
- Suppose for some . We claim that for all , or that is eventually non-increasing and bounded below by so it must eventually be constant.