Consolidated math problems thread

[Grog]

Grog, your answer is simple, but is it possible to phrase it in terms of Fourier series and make it simpler?

Spoiler

We can integrate f(x+a)-f(x) over a period and see that it has mean value 0, I'm not sure if you think this is simpler.

[Kuroneko]

Problems without posted solution (so far): [1], [4], [6], [10]. Solutions to already-solved problems are also welcome.
---

Yay, great thread!
Hopefully I can come up with some interesting problems this time around.

The inequality was quite nice.

Spoiler

f is continuous and periodic so it has a global maximum at x_1 and a global minimum at x_2.
f(x_1+a)-f(x_1)<0 and f(x_2+a)-f(x_2)>0
f(x+a)-f(x) is continous for all a so the there is a solution for all a.

Nice and clean. One might add for clarity that the second line follows if x_1, x_2 are not already solutions.
---

8. (Fractional derivative) Assuming that [(d/dx)^ν][exp(ax)] = a^ν exp(ax) holds even for noninteger ν, show that the derivates of sine and cosine are phase shifts by νπ/2, i.e., [(d/dt)^ν][sin(t)] = sin(t+νπ/2), etc.

Spoiler

Use sin(x) = (1/2i)[exp(ix)-exp(-ix)] and i^v=exp[ivπ/2]. Cosine is similar.

Alright, let's have part (b), then:
8. (b) What is the -1/2th derivative of exp(ax), according to the assumption in part (a)? What about according to this definition of fractional derivative? Explain the apparent contradiction, and in what sense non-negative integer derivatives are "special".
---
I'd like to modify this problem (to be clear, n is the number of questions--unfortunately, I did not state this explicitly), particularly part (a).

10. Kuroneko is forced to take an organic chemistry exam, part of which is involves matching questions (1,2,...,n) to a list of answers (A,B,...), each being right for exactly one question. Knowing nothing about the subject matter, he decides to mark them completely at random and use the extra time to doodle some math instead. (a) If n = 10, what is the probability that he got exactly one question right? Assume all valid answer-sequences have the same probability. (b) His doodles led him to believe that no matter what n is, the expected number of correctly answered questions is always 1. Is he right?

I have a pure conjecture about that I almost posted as part (c), but I'd rather not propose a problem I haven't solved. (Although of course anyone is welcome to post unsolved problems.)

[Glass Pearl Player]

10. Kuroneko is forced to take an organic chemistry exam, part of which is involves matching questions (1,2,...) to a list of answers (A,B,...), each being right for exactly one question. Knowing nothing about the subject matter, he decides to mark them completely at random and use the extra time to doodle some math instead. (a) If n = 10, what is the probability that he got at least eight questions right? Assume all valid answer-sequences have the same probability. (b) His doodles led him to believe that no matter what n is, the expected number of correctly answered questions is always 1. Is he right?

This is basically a question about permutations and the number of their fixed points. Spoiler

asks for the number of permutations of 10 elements with at least 8 fixed points. There is exactly one with ten (the identity) and none with nine. A permutation with 8=10-2 fixed points simply swaps two elements, so there are 10*9/2 = 45 of them. This adds up to 46 out of 10!=3628800 permutations, or 0.00001267636684

[Glass Pearl Player]

Spoiler

Yes, the expectation value is always 1. Quick sketch of unimaginative proof: Using the Subfactorial, one can compute the probability that a permutation has exactly k fixpoints: One can choose the k fixpoints and a permutation of n-k elements without fixpoints.
P(k)=1/n! (n over k) !(n-k)
From that and the formula for !(n-k), one gets for the expectation value:
E(n)=sum_{k=0}^{n} k/k! sum_{m=0}^{n-k} (-1)^m / m!
Using a binomial identity one can show that E(n)=E(n-1). E(1) is trivially 1, and one has all ingredients for a proof by induction.

[Surlethe]

Here's a fun little construction problem.

Consider the disk {(u,v):u^2+v^2<4}. Conformally distort it so that the inner product is given by <v_p,w_p> = v_p.w_p/[1-||p||^2/4]^2, where x.y is the usual dot product. Prove that the Gaussian curvature on the disk with this new geometry is uniformly -1, and find the geodesics.

[lordofFNORD]

10. Kuroneko is forced to take an organic chemistry exam, part of which is involves matching questions (1,2,...) to a list of answers (A,B,...), each being right for exactly one question. Knowing nothing about the subject matter, he decides to mark them completely at random and use the extra time to doodle some math instead. (a) If n = 10, what is the probability that he got at least eight questions right? Assume all valid answer-sequences have the same probability. (b) His doodles led him to believe that no matter what n is, the expected number of correctly answered questions is always 1. Is he right?

Ok, my statistics is a little rusty, but I'll give it a shot.
a) Spoiler

The total number of possible ways to answer is 10! (10 element permutation). This is our denominator.
The chance of answering a given question right is 9!, as the rest of the questions form a 9 element permutation, and the correct answer has exactly one state. There are 10 questions, so the chance of answering AT LEAST one question correctly is 1-((1-9!/10!)^10)=1-.9^10~=.3487
The chance of answering 2 given questions right is 8!, 3 given questions 7!, etc. Note that these are all "at least" not "exactly".
There are [10 choose 2] sets of 2 questions, [10 choose 3] sets of 3 questions, etc. The choose function, irc, for [n choose k] is n!/(k!(n-k)!).
So, for at least 8 questions, we have: P=1-(1-(2!/10!)^X), where X = 10!/(8!2!)= 45
Ballpark:
P=1-(1-5.5115e-7)^45=2.48e-5
Kuroneko's odds of a B are slim. On the plus side, if he gets at least 8 right, he has a 50% chance of getting a perfect score .

b) Spoiler

No, for n=0, the expected value is 0

attempted real answer Spoiler

As established above (sort of), the chance of getting at least m questions on a n question test right is:
P(m, at least)=1-((1-(n-m)!/n!)^nCm)
Further: P(m, exact)= P(m, at least) - P(m+1, at least)
Now, the expectation value is:
Sum(m=0 to m=n: m * P(m, exact)) = Sum(m=0 to m=n: m * [P(m, at least) - P(m+1, at least)])
Now, the m * (-P(m+1, at least)) mostly cancels with the m+1*P(m+1, at least) from the next term. Except for the nth term, but P(n+1, at least) = 0.
So we have:
Sum(m=0 to m=n: P(m, at least)).

[Surlethe]

Would anyone be interested in seeing this year's Putnam questions? I have solutions to three or four of them.

[Surlethe]

No replies is good replies, I guess, so here are six of this year's Putnam questions.

[P1]: Let f be a function from the plane to the real line such that f(x,y)+f(y,z)+f(z,x)=0 for all real numbers x, y, and z. Prove that there exists a function g from the reals to the reals such that f(x,y)=g(x)-g(y) for all real numbers x, y.

[P2]: Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008x2008 array. Alan plays first. At each turn, a player chooses a real number* and places it in a vacant entry. The game ends when all the entires are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

*This problem works for any field, not just the reals.

[P3]: Start with a finite sequence a_1, a_2, a_3, ..., a_n of positive integers. If possible, choose two indices j<k such that a_j does not divide a_k, and replace a_j and a_k by gcd(a_j, a_k) and lcm(a_j,a_k), respectively. Prove that if this process is repeated, it must eventually stop and the final sequence does not depend on the choices made. (Note: gcd means greatest common divisor and lcm means least common multiple.)

[P4]: Define f from R to R by f(x) = x if x<= e and f(x) = xf(lnx) if x>e. Does \sum_{n=1}^\infty 1/f(n) converge?

[P5]: Let n>2 be an integer. Let f(x) and g(x) be polynomials with real coefficients such that the points (f(1),g(1)), (f(2),g(2)), ..., (f(n),g(n)) in the plane are the vertices of a regular n-gon in counterclockwise order. Prove that at least one of the f(x) and g(x) has degree greater than or equal to n-1.

[P6]: Prove that there exists a constant c>0 such that in every nontrivial finite group G there exists a sequence of length at most cln|G| with the property that each element of G equals the product of some subsequence. (The elements of G in the sequence are not required to be distinct.)

[Surlethe]

Here is the second set of Putnam problems:

[P7]: What is the maximum number of rational points that can lie on a circle in R^2 whose center is not a rational point?

[P8]: Let F_0(x) = ln(x). For n>=0 and x>0, let F_[n+1](x) = Int_0^x F_n(t)dt. Evaluate lim_{n -> \infty} n!F_n(1)/ln(n).

[P9]: What is the largest possible radius of a circle contained in a 4-dimensional hypercube?

Extra credit opportunity: generalize the result to n dimensions.

[P10]: Let p be prime. Let h(x) be a polynomial with integer coefficients such that h(0), h(1), ..., h(p^2-1) are distinct modulo p^2. Show that h(0), h(1), ..., h(p^3-1) are distinct modulo p^3.

[P11]: Find all continuously differentiable functions f: R-> R such that for every rational number q, f(q) is rational and has the same denominator as q. (The denominator of q is the unique positive integer b such that q = a/b for some integer a with gcd(a,b)=1.)

[P12]: Let n and k be positive integers. Say that a permutation \sigma of {1,2,...,n} is k-limited if |\sigma(i)-1|<=k for all i. Prove that the number of k-limited permutations of {1,2,...n} is odd iff n = 0 or 1 (mod 2k+1).

[Kuroneko]

I owe Surlethe an apology, since I promised to take a look at these nearly a week ago, but circumstances forced this week to be a even more hectic than expected. I spent quite a bit of time today going over the problems, but unfortunately I've only managed half of them.

Consider the disk {(u,v):u^2+v^2<4}. Conformally distort it so that the inner product is given by <v_p,w_p> = v_p.w_p/[1-||p||^2/4]^2, where x.y is the usual dot product. Prove that the Gaussian curvature on the disk with this new geometry is uniformly -1, and find the geodesics.

The last part is a significant hint, since the surface of constant positive curvature is just a sphere. Spoiler

In a plane, consider a circle of radius 2 with center at the origin O, and let ψ be the angle OAB, where A is (0,2) and B is (x,0), so that tan ψ = x/2. Then the arc from C(0,-2) to D, the intersection of AB and the circle, has length 4ψ, and therefore the the circle carries the metric ds² = (4dψ)² = 4 dx² / [ 1 + x²/4 ]². Wick rotating to tanh ψ = x/2 introduces a minus sign in the denominator, and distorting to get rid of the four in the numerator is easy.

Spoiler

If graphed on a flat (u,v) plane, should be circles orthogonal to u²+v²=4 or its diameters, but I haven't checked this explicitly.

---

[P1]: Let f be a function from the plane to the real line such that f(x,y)+f(y,z)+f(z,x)=0 for all real numbers x, y, and z. Prove that there exists a function g from the reals to the reals such that f(x,y)=g(x)-g(y) for all real numbers x, y.

Spoiler

Letting y = z = x, we have f(x,x) = 0, and subsequently z = x gives f(x,y) + f(y,x) = 0. Finally, letting z = 0 gives f(x,y) = -f(y,0) - f(0,x) = f(x,0) - f(y,0). Therefore, f(x,y) is fully determined by g(x) = f(x,0).

[P2]: Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008x2008 array. Alan plays first. At each turn, a player chooses a real number* and places it in a vacant entry. The game ends when all the entires are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

Spoiler

If Alan moves at (n,m), Barbara copies at (n,2009-m), assuming the indices start at 1, or similar schemes.

I thought I solved P3, but I found a mistake as I was typing this.

[P4]: Define f from R to R by f(x) = x if x<= e and f(x) = xf(lnx) if x>e. Does \sum_{n=1}^\infty 1/f(n) converge?

I knew beforehand (from one of Hardy's books) than the sum of the reciprocals of n ln(n) ln(ln(n)) ... ln^m(n) diverges for any finite, fixed m, and my first instinct was to just try to generalize it to the problem at hand, but that's much more complicated than this problem requires. Spoiler

A series with terms 1/f(n) for monotonic f(x) is convergent iff the corresponding integral is convergent. Define e_0 = 1, e_{m+1} = exp(e_m), so that for every natural n, e_m ≤ x < e_{m+1} implies f(x) = x ln(x) ln(ln(x)) ... ln^m(x). In this form, it is easy to see that f(x) is nondecreasing, by considering each interval (e_m,e_{m+1}), on which it is even differentiable, and then what happens across the boundary points. Let E_m = \int_{e_m}^{e_{m+1}} dx/f(x). Substitute f(x) = xf(ln(x)), y = ln x to see that E_m = E_{m-1}. This proves divergence, although it might be noted that E_m = 1 for all m.

[P7]: What is the maximum number of rational points that can lie on a circle in R^2 whose center is not a rational point?

Spoiler

Let the center be (h,k). Assuming that there exist three rational points on the circle, draw the three lines between them and show that h+mk is rational for each of the three slopes m. Hence there cannot be more than two rational points on such a circle.

12. Consider a unit circle with center at the origin. Prove or disprove that a stereographic projection from (0,1) to the x-axis define a bijection between rational points on the circle and the rational points on the x-axis.
(This was actually my first instinct at approaching P7, but that very quickly became a quagmire of no useful results.)

[P8]: Let F_0(x) = ln(x). For n>=0 and x>0, let F_[n+1](x) = Int_0^x F_n(t)dt. Evaluate lim_{n -> \infty} n!F_n(1)/ln(n).

I'll pose a different question that makes the answer to P8 obvious:
13. Let F_0(x) = ln(x). For n>=0 and x>0, let F_[n+1](x) = Int_0^x F_n(t)dt. Show that lim{n->\infty}[ n!F_n(1) - ln(n) ] exists (finitely).
This reduces to fairly famous result, actually.

[P9]: What is the largest possible radius of a circle contained in a 4-dimensional hypercube? Extra credit opportunity: generalize the result to n dimensions.

Spoiler

Given an orthonormal {u,v}, the circle (u,v) = (r cos θ, r sin θ) corresponds to ru cos θ + rv sin θ. In R^n with even n, (cos θ, ... , cos θ, sin θ, ..., sin θ), where there are n/2 cosines and n/2 sines, is trivially contained in [-1,1]^n, as every coordinate is in [-1,1]. Hence for even n, a circle of radius sqrt(n)/2 exists in [-1,1]^n. To show that this is maximal, use orthonormality to get u_k² + v_k² ≤ 1/r².

For the general case I've no solution:
14. (Unknown) What is the largest possible radius of an m-sphere in [-1,1]^n?