Austin Math Circle

All six sides of the convex hexagon ABCDEF are equal. In addition, AD = BE = CF. Prove that a circle can be inscribed in the hexagon.

Find the largest positive integer N such that there are integers x 1 ,...,x N such that x i 2 - x i x j is not divisible by 1111 for any i,j, i=/=j. Edited to add solution : We have x i 2 - x i x j = x i (x i - x j ) is not 0 mod 1111. Thus x i and x j have different remainders mod 1111. Since 1111 = 101 * 11, we also need to make sure we don't have x i be 0 mod 11 and x i - x j be 0 mod 101, or vice versa. We thus start with a list of 1111 integers, one for each remainder mod 1111, and then remove those which are 0 mod 11 and those which are 0 mod 101. That leaves 1000 integers on the list. (Some remaining clean-up work: show that that list of 1000 is maximal.) (Problem source: 2016 Benelux Mathematical Olympiad #1.)

A magical castle has n identical rooms, each of which contains m distinguishable doors arranged in a line. In each room i<n, there is one door that takes you to room i+1, and all other doors take you back to room 1. In room n, there is one door that takes you out of the castle, and all other doors take you back to room 1. When you go through a door into a room, you are unable to tell which room of the castle is is (and there is no way of marking rooms). You also cannot tell which doors have been opened before. Determine for which pairs (n,m) there is a strategy that guarantees escape from the castle, and explain the strategy. Edited to add solution: Here's a starting thought: if we could reliably know when we are in room 1, we could solve the problem easily for any n and m. We would then: 1. Enumerate all length n sequences from the alphabet {1,...,m}. 2. For each sequence in that list, (i) get to room 1, and (ii) then follow that sequence. Eventually we'd get to the c...

Alphonse and Beryl play a game involving safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects of the safes (where ) , and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these safes and tries to use these keys to open up the other safes. If he can open a safe with one of the keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let be the probability that Alphonse can eventually open all safes starting from his initial selection of keys. Find (with proof) a general formula for . Edited to add solution : We prove by induction that Pm(n) = m/n. Note first that the initial distribution of the keys in the n ...

For which positive integers m does the equation (ab) 2015 =(a 2 + b 2 ) m have positive integer solutions? Edited to add solution : The combination of a product of a and b on one side and a sum of a and b on the other side immediately suggests two approaches: (i) AM-GM, and (ii) looking for common factors. We'll make use of both ideas. Suppose p is a prime factor of a. Then p is also a factor of (ab) 2015 ,and thus must be a factor of (a 2 + b 2 ) m . Thus p is also a factor of a 2 + b 2 . Since p is a factor of a 2 , it must also be a factor of b 2 , and hence also a factor of b. By symmetry, the same applies to b. Thus a and b have exactly the same prime factors. That's almost enough to conclude a=b (which would make the problem much easier), but not quite enough -- a and b might have the same prime factor but to different powers. So suppose a=cp A and b=dp B where c and d are relatively prime to p, and B>A. Then we have p 2015(A+B) (cd) 2015 = p 2AM (c 2 +p...

Let f be a function on the reals so that for every x,y we have f(xf(y))=yf(x). Prove that f is odd. Edited to add solution : (This solution combines ideas from Nir's and Saskia's solutions -- it starts using Nir's proof of involutivity, then uses Saskia's proof of multiplicative distribution, and then follows both of them in calculating f(-1).) Step 1: f is involutive. We have f(xf(y))=yf(x). Applying f to both sides, we have f(f(xf(y)) = f(yf(x)). But f(yf(x))=xf(y), from our original condition swapping x and y. Thus f(f(xf(y))=xf(y), so f is involutive (that is, f is its own inverse). Involutive is a powerful condition worth looking out for in functional equation problems. Involutive functions are always bijective, and this fact is frequently what we use to go forward. Step 2: f distributives over multiplication. Substituting f(x) for x we have f(f(x)f(y)) = yf(f(x) = xy (by involutivity). Now take f of both sides, and we have f(f(f(x)f(y)) = f(xy). Applying i...

Find all positive integers x, y, and z satisfying x 2 + y 2 + z 2 = 2xyz. (As usual, give solutions in comments to this post. On Friday I'll post some combination of my own solution and the most elegant approaches suggested by others.) Edited to add solution : If x 2 + y 2 + z 2 = 2xyz, then x 2 + y 2 + z 2 must be even. Thus there are two cases to consider: 1. One of x, y, z is even and two are odd. 2. All three of x, y, and z are even. Start with case 1. Assume (without loss of generality) that x is even, so x = 2a. Then we have 4a 2 + y 2 + z 2 = 4ayz. But then y 2 + z 2 must be a multiple of 4. But odd numbers are always 1 mod 4, so this is impossible. Thus case 1 can't be achieved. Now consider case 2. We have x=2a, y=2b, and z=2c. Thus 4a 2 + 4b 2 + 4c 2 = 16abc, or a 2 + b 2 + c 2 = 4abc. So let's now focus on this new equation. Again we  need the sum to be even, so we need either one or three even numbers. But one even and two odd...

Luke and Andrew play a game on a square board consisting of nxn white tiles, where n >=2. Luke moves first, and the players alternate taking turns. A move consists of picking a square consisting of 2x2 or 3x3 white tiles and coloring all those tiles black. The first player who cannot find any such squares loses. Show that for all n, Luke has a winning strategy for the game. (Give solutions in comments to this post. On Wednesday I'll post some combination of my own solution and the most elegant approaches suggested by others.) Edited to add solution: Two approaches that are often helpful in tackling "winning strategy" problems are: 1. Strategy stealing 2. Mirroring strategies Strategy stealing is a bit tempting here because there is no possibility of a draw, which means that if strategy stealing shows that Andrew can't have a winning strategy (because Luke could steal it), Luke then must have a winning strategy. On the other hand, it's hard to see what t...