<p>I'm trying to work through the 400 or so math problems posted on Math</a> Problem of the Day this summer. So I thought what the hell, might as well share my progress with you guys, in case any of you want to give this a try. I'm starting from the latest set and working backwards. As far as I can tell, they're all pretty much really difficult.</p>
Sohail is tinkering around with a function f. Suddenly, he realizes that his function satisfies the equation f(x + y) + f(xy) = f(x)f(y) + 1 for all pairs of integer values x and y. Find all possible values of f(2012).
<p>Interestingly enough, there seems to also be a counting argument that can justify the expected number of rolls for the complete k-sequence on a k-sided die is k^k.</p>
<p>Unlike the other find the value of function f problem, this one only has a single unique solution so it actually is a reasonable algebraic problem.</p>
<p>This was the first combinatorial problem that you can just pigeonhole your way through. At first I got tripped up on enumerating the edges that connects nodes that are two apart because I didn’t realize there are more than one way of creating a cycle of length four within the ordered scheme. Overall this puzzle was a lot funner and less time consuming that the other ones, I highly recommend people try this out for themselves.</p>
<p>This one stumped me for a while since I wasn’t sure whether the equivalence classes under {~ if f(x) = f(y)} generated by x[n+1] = x[n]^2 + 2012 were disjoint or not, until I applied the strictly increasing argument on it. (The flop in the question numbers is because I wanted to work on an algebraic problem next)</p>
<p>Damn, this one was hard as hell. I had a hunch of what the solutions were after enumerating the possible cube pairs using some similar enumeration as the rationals</p>
<p>
def pairs(n):
for i in range(1,n):
yield i<strong>3,(n-i)</strong>3</p>
<p>def generator(n):
for i in range(2,n+1):
for x in pairs(i):
yield x
</p>
<p>However proving that no other pairs can be solutions was no small feat</p>
<p>Ah yes, functional equations for #409 and #405. Usually I just plug in a bunch of random stuff and see if I can find interesting info or prove injectivity/surjectivity.</p>
<h1>404 seems easy, it seems like you can just find the maximum k such that there is no cycle of length 4, then add 1 (due to Pigeonhole principle). To find the maximal k, note that for every four cities, at most four paths are required for there to be no cycle (5 would guarantee a cycle).</h1>
<p>You’re pretty much there, except you’re switching maximum with minimum. For example, if I can find a graph with 5 edges that contains a cycle of 4, then I’ve shown that k must be at least 6, which contradicts the claim that the maximum k can be is 5.</p>