Mathcamp 2009 Qualifying Quiz

http://www.mathcamp.org/quiz/quiz09.php

by wallflower • 17 years ago

9 6 17 years ago

lacker2• 17 years ago

Here's some hints. Don't read if you don't want spoilers!

1. Forget the "continuous" and break it into half-hour units.

2. Consider what color is the integer a = 7x + 11y. Imagine coloring an infinite 2d grid where each lattice point (x, y) is labeled with 7x + 11y.

3. Let S(n, k) be the number of size-k subsets of [1..n] that contain k.

4. Ask yourself the same question but restrict yourself to only adding powers of 2.

5. Write out the formula for, if a and b are two sides of a triangle, what's the minimum and maximum that the third side can be.

6. Kind of an ugly one. Try writing out the answers for the first few dozen numbers and looking for the patterns. Look at the binary representations.

7. "product" is just a tricky way of obscuring what's going on here. A simpler sequence that obeys this is element n = the log of the nth Fibonacci number. Then you have to know about generating functions or perhaps just Lucas numbers plus cleverness.

8. "10" is relevant because it's (18 / 2) + 1. Try first solving the easier problem where all the lines are restricted to being either vertical or horizontal.

lpolovets• 17 years ago

Thanks for the hints. Another hint for 4a: thinking in terms of the binary/bit representation helped me a lot as well.

hawk• 17 years ago

for 7, not sure what you mean by your "simpler sequence" obeying this - i don't see how that's the case. you can do this problem with elementary knowledge, however. as you imply, first transform it into an addition problem from a multiplicative one by taking logs. then just write out the sequence: a, b, a+b, a+2b, 2a+3b, 3a+5b,... and note that the ratio between the coefficients tends to phi alternating above and below.

lacker2• 17 years ago

Yeah I got that backwards, the hint should have been "element n = e^(nth fibonacci number)".

jacobolus• 17 years ago

Why is 6 "ugly"? Each number k for which the player playing at that point will win leads to 2k being a loss, meaning that 2k + 1 is a win. Whereas if k is a loss, then both 2k and 2k + 1 are wins. So part a) is really easy, because we can just repeatedly halve the numbers to figure out what the values should be, and part b) is also easy, because our proportion of wins to losses in the limit is described by a simple markov chain.

[edit: another minute's thought... actually, the obvious implication of the above is that every odd number is a win, and therefore losses are only those numbers with odd numbers of 2s in their prime factorizations]

In any case, I don't see why these questions belong on Hacker News. They're the sort of fun puzzles that make for a good high school math camp quiz (a clever high school student should figure most of them out in an afternoon), but none of them contains any deeper insight or relevance, as far as I can tell.

wallflower• 17 years ago

My friend's son is an aspiring MathCamper so I thought I'd post the type of questions they use to winnow the applicants, in case anyone was curious and/or wanted to exercise their proof muscles.

Mathcamp 2009 Qualifying Quiz

Related Stories