Consolidated math problems thread

[Kuroneko]

(With apologies to people who've expected this sooner.) The purpose of this thread is simple: to exchange interesting math problems with others, and it is open to everyone who wants to either post or solve such problems. It's intended as a catch-all thread that would provide some avenue for discussion but isolated enough so as to not spam the rest of the forum.

At first, I wanted to describe this as a thread for "neat" problems--does not necessarily difficult or complicated ones (although some may be), but those with interesting results, or stretching intuition in some way, or simply because one is likely to learn an interesting technique in the process of solving it. However, since such questions are to a large part subjective, that's likely treating this with somewhat more seriousness than it deserves. If a problem looks interesting, or you simply feel stumped by it, feel free to post it. If you have a solution to an already posted problem, or simply a comment, feel free to post that as well. Specialized, esoteric topics are welcome but by no means required.

---

Let's start off with simple things. A good example of two problems that aren't complicated at all might be:
0. (a) In a standard coordinate plane, take four circles of unit radius in each of the quadrants, at centers (±1,±1), and a square S = {(x,y): -2≤x,y≤2}. S clearly contains those circles, and also the circle at the origin that's tangent to each of the unit circles. If this construction is repeated in every dimension n, with circles replaced by spheres of appropriate dimension and a hypercube replacing the square, will S still contain all the spheres?
(b) Suppose your task is to be able to exactly balance any whole number of grams between 1 and 1000 on a standard balance scale. What is the least number of weights for which this is possible?

A good example of a problem that's probably complicated without a specialized tool (or at least, I'm not aware of a truly simple solution), but is likely to use interesting techniques, is the general version of the classic birthday paradox:
(c) Show that in a random sample of 23 people, the probability that at least two share the same birthday (sans year number) is at least 1/2.

1. (Side-Derivative) A real function is convex on [a,b] iff for every p in [0,1], f(px+qy)≤pf(x)+qf(y), where q=1-p. Show that every function convex on an interval around x is side-differentiable at x, i.e., the limits lim[ (f(x+h) - f(x))/h ], h to zero from either right (h>0) or left (h<0), exist.

The "squeezing theorem" applies to limits of functions that are are between two other functions. But we can also squeeze derivatives.
2. (Derivative Squeeze) Show that if f has a bounded second derivative, then in limits of x to infinity, lim[ f(x) ] = 0 implies lim[ f'(x) ] = 0.

3. Show that for any triangle, the sum of the squares of the sides is at least as large as (4sqrt(3)) times the area of the triangle. When does one have equality?
[Edit: 4/sqrt(3) replaced by 4sqrt(3).]

[Terralthra]

To the birthday paradox, the easiest method I've used to show the probability is to first use the pidgeonhole principle to calculate the likelihood that each person has a different birthday.

To wit:

the probability that in a group of n people, they have n different birthdays is shown by:

p(n) = 1 * (1 - 1/365) * (1 - 2/365) * (1 - 3/365)...etc.

!p(n) is simply = 1 - p(n)

Calculating is simply a matter of plugging and chugging. p(23) = .493, !p(n) = .507 = 50.7%.

[Kuroneko]

There are two complications for the general case. The very minor one is that there are 366 possible birthdays, and the more important one is that the assumption of a uniform distribution is unjustified. Luckily, we do not need to know anything about the actual distribution of birthdays to prove that result.

[Terralthra]

There are two complications for the general case. The very minor one is that there are 366 possible birthdays, and the more important one is that the assumption of a uniform distribution is unjustified. Luckily, we do not need to know anything about the actual distribution of birthdays to prove that result.

Without getting too deep into the hairy end of the general case, it would be exceedingly unlikely for an uneven distribution of birthdays to do anything but increase the likelihood of a collision.

[Kuroneko]

Without getting too deep into the hairy end of the general case, it would be exceedingly unlikely for an uneven distribution of birthdays to do anything but increase the likelihood of a collision.

That's exactly what happens. But then, proving than a non-uniformity distribution never decreases this probability (as compared to uniform) is most of the problem.

[fnord]

3. Show that for any triangle, the sum of the squares of the sides is at least as large as (4/sqrt(3)) times the area of the triangle. When does one have equality?

Well, here's my crack at it.

Assume that a, b, c are sides of a triangle in a euclidean plane, real, and non-negative.

So we have to show

a^2 + b^2 + c^2 >= sqrt(16/9) * area of triangle

Heron's formula for the area of a triangle, given semi-perimeter s, s = 0.5 * (a + b + c), is

sqrt(s * (s-a) * (s-b) * (s-c ) )

Substituting, expanding, and collecting like terms gives

area of triangle = sqrt ( 2 * ( a^2b^2 + a^2c^2 + b^2c^2) - (a^4 + b^4 + c^4)) /4

sqrt(16/3) * area = sqrt ( 2 * ( a^2b^2 + a^2c^2 + b^2c^2) - (a^4 + b^4 + c^4)) / sqrt(3)

Squaring,
16 /3 * area^2 =( 2 * ( a^2b^2 + a^2c^2 + b^2c^2) - (a^4 + b^4 + c^4)) / 3

Back over to the LHS

sum of squares of sides = a ^2 + b^2 + c^2

Squaring,
sum of squares, squared = a^4 + b^4 + c^4 + 2(a^2b^2 + a^2c^2 + b^2c^2)

Adding (a^4 + b^4 + c^4)/3 to both sides

LHS: 4/3 (a^4 + b^4 + c^4) + 2*(a^2b^2 + a^2c^2 + b^2c^2)
RHS: 2 * ( a^2b^2 + a^2c^2 + b^2c^2) /3

Subtracting the entirety of the RHS from both sides

LHS: 4/3 (a^4 + b^4 + c^4) + 4/3 (a^2b^2 + a^2c^2 + b^2c^2)
which is always >=
RHS: 0
across entire problem domain.

Equality only occurs when the LHS of the above result is zero, ie, when a, b, c are all zero, namely, the triangle is trivial (a point).

[Kuroneko]

Ack. I had the wrong factor; it should've been 4sqrt(3)--no division. Mea culpa.

In regards to your post, fnord, this would be the corresponding algebra (so you don't have to recalculate on my account):
(a²+b²+c²)² ≥ 3[ (a+b+c)(a+c-b)(a-b+c)(a+b-c) ]
a^4+b^4+c^4 + 2[a²b²+a²c²+b²c²] ≥ 6[a²b²+a²c²+b²c²] - 3[a^4+b^4+c^4]

... although I honestly didn't expect this approach (but the algebra is not too hairy, I suppose).

[Fingolfin_Noldor]

With regard to Question 1, would one way to solve the problem involve letting x = p x' + q y' and solve from that stand point?

With regard to Question 2, would a way to solve it be to take the limit:

lim_{x->\infty} lim_{h\rightarrow 0} \frac{f(x+h) - f(x)}{h}}

?

[Jaepheth]

Here's a fun one:

Bob goes to the store and buys 1 pound of flour every Friday, and Sue goes to the store to buy $1 of flour every Friday.

Over time the price of flour fluctuates. Who gets the better deal? (Pays fewer dollars per pound of flour)

[Jaepheth]

ghetto edit: That should probably read Bob buys 1 kilo of flour and Sue buys $1 worth of flour each Friday. (To better suit an international audience and eliminate possible confusion with British Pounds Sterling)

[Kuroneko]

With regard to Question 1, would one way to solve the problem involve letting x = p x' + q y' and solve from that stand point? With regard to Question 2, would a way to solve it be to take the limit:
lim_{x->\infty} lim_{h\rightarrow 0} \frac{f(x+h) - f(x)}{h}}?

Depends on the former, and rather dubitable on the latter. (That's not to say they absolutely can't be solved that way, but simply that I don't see how offhand... I do have solutions for every problem I've posted so far, but they're not guaranteed to be unique.)

Here's a fun one:
Bob goes to the store and buys 1 pound of flour every Friday, and Sue goes to the store to buy $1 of flour every Friday. Over time the price of flour fluctuates. Who gets the better deal? (Pays fewer dollars per pound of flour)
ghetto edit: That should probably read Bob buys 1 kilo of flour and Sue buys $1 worth of flour each Friday. (To better suit an international audience and eliminate possible confusion with British Pounds Sterling)

Ooh, that is a fun one. Spoiler:
Let r_k be the price per mass ("specific price") of flour at Friday k, so Bob pays r_k*(1 kg) money each time while Sue gets ($1)/r_k of flour each time. Hence Bob's average price per mass over n weeks is the arithmetic mean of the r_k's, while Sue's is $1 times the harmonic mean. Hence Sue gets a deal that's no worse than Bob's. One way to prove that the harmonic mean is no greater than the arithmetic mean is to observe that the map f(x) = 1/x is convex on x>0 and apply Jensen's inequality. I'll try to find a more elementary proof later.

[fnord]

Ack. I had the wrong factor; it should've been 4sqrt(3)--no division. Mea culpa.

In regards to your post, fnord, this would be the corresponding algebra (so you don't have to recalculate on my account):
(a²+b²+c²)² ≥ 3[ (a+b+c)(a+c-b)(a-b+c)(a+b-c) ]
a^4+b^4+c^4 + 2[a²b²+a²c²+b²c²] ≥ 6[a²b²+a²c²+b²c²] - 3[a^4+b^4+c^4]

... although I honestly didn't expect this approach (but the algebra is not too hairy, I suppose).

Out of curiosity, what were you expecting? I had a first crack trying to use the sine rule and 0.5absinC, but that crashed and/or burned.

Sans your error, you'd also have equality when a^4 + b^4 + c^4 = a^2b^2 + a^2c^2 + b^2c^2, ie, when a = b = c, or when the triangle is equilateral.

[Kuroneko]

Out of curiosity, what were you expecting? I had a first crack trying to use the sine rule and 0.5absinC, but that crashed and/or burned.

Well, no approach was exactly expected since that inequality has a lot of proofs; it's simply that I didn't think of Heron's formula for some reason (although it is very natural in retrospect). Call it an oversight. For example, one can make the sine formula work for us by observing something about the reciprocal of the sine function (same approach as I used Jaepheth's problem, if you want to spoil yourself on that one), combined with the inequality below, which, by the way, still needs to be proven to complete your approach. There are other approaches.

Sans your error, you'd also have equality when a^4 + b^4 + c^4 = a^2b^2 + a^2c^2 + b^2c^2, ie, when a = b = c, or when the triangle is equilateral.

That's true, but what guarantees a^4+b^4+c^4 ≥ a²b² + a²c² + b²c²? For 4/sqrt(3), the difference was plainly always positive because every term had an even power and a non-negative coefficient, but now, that is no longer the case.

[Grog]

It is well known that the sum of two stochastic variables with binomial distributions with the same "p-value" (I'm not sure what the correct term is here) is a stochastic variable with binomial distribution with the same "p-value". Prove the converse, that is that if a sum of two stocastic variables gives a binomial distribution then the two stochastic variables have a binomial distribution. I thought this was kind of cool.

[fnord]

Sans your error, you'd also have equality when a^4 + b^4 + c^4 = a^2b^2 + a^2c^2 + b^2c^2, ie, when a = b = c, or when the triangle is equilateral.

That's true, but what guarantees a^4+b^4+c^4 ≥ a²b² + a²c² + b²c²? For 4/sqrt(3), the difference was plainly always positive because every term had an even power and a non-negative coefficient, but now, that is no longer the case.

At the moment, I'm playing around with imposing a >= b >= c and scaling a, b and c by a.

Thus reducing guaranteeing

a^4 + b^4 + c^4 >= a^2b^2 + a^2c^2 + b^2c^2
to
1 + b^4 + c^4 >= b^2 + c^2 + b^2c^2 - does have benefit of reducing problem from the positive octant of R^3 to the positive quadrant of the unit square in R^2.

[fnord]

Need to show
1 + b^4 + c^4 >= b^2 + c^2 + b^2c^2 (1)

Proceed by noting that b >= c, thus for

Need to show
1 + b^4 + b^4 >= b^2 + b^2 + b^4 (2)

1 + b^4 is greater than or equal to 2b^2 for all b on range [0..1].

LHS of 2 >= LHS of 1
RHS of 2 >= RHS of 1

delta LHS = b^4 - c^4
delta RHS = (b^2 - c^2) + (b^4 - b^2c^2)
Observe that the b^4 term is common to the delta of both the LHS and RHS, and thus does not affect their relative inequality

delta LHS = -c^4
delta RHS = b^2 - c^2 - b^2c^2

Adding c^2 to both deltas
delta LHS = c^2 - c^4 = c^2(1-c^2)
delta RHS = b^2 - b^2c^2 = b^2 (1 - c^2)

Case c = 1
delta LHS = 0
delta RHS = 0 (since b >= c and b <= 1)

Case c < 1
Divide both deltas by (1 - c^2)
delta LHS = c^2
delta RHS = b^2

implying original delta RHS >= original delta LHS for all 0 <= c <= 1. Label original delta RHS say, R, similarly for LHS, L.

Thus (2) becomes

LHS of (1) + L >= RHS of (1) + R , R >= L, or
LHS of (1) >= RHS of (1) + S , S = R - L >= 0.

This implies (1) is at least a great an inequality as (2), shown to hold over all 0 <= b <= 1. (Is this where you put QED? Never could quite figure that out. Apologies for the linguistic and notational looseness.)

[Kuroneko]

Fnord, your approach looks valid (for anyone else interested, the logic is essentially to establish (1) A≥B, first establish (2) C≥D and C-A≤D-B separately, and then conclude (1)), but it is substantially more complicated than it needs to be. Trust me--this inequality can be done in a single line if a certain basic result is known and maybe three more lines to reproduce said result if it's not known. [Edit: inequality direction.]

It is well known that the sum of two stochastic variables with binomial distributions with the same "p-value" (I'm not sure what the correct term is here) is a stochastic variable with binomial distribution with the same "p-value". Prove the converse, that is that if a sum of two stocastic variables gives a binomial distribution then the two stochastic variables have a binomial distribution. I thought this was kind of cool.

That's excellent. Actually, I don't think it's true without the assumption that the probability of either of the two variables not being a non-negative integer is zero. Otherwise, it's not hard to 'shift' binomial distributions in that manner and thus get a counter-example (although not a very interesting one). But with that assumption, spoiler:
If X can only take on non-negative integer values, then the probability distribution must have a moment-generating function of M(t) = <exp(tX)> = Sum_X[ Pr(X) exp(tX) ] is a polynomial in e^t. By hypothesis, the mgf that is a polynomial in e^t with exactly one root. Hence the mgfs of the two variables, which must themselves be polynomials in e^t, must have only that root.

[fnord]

Figured as much. Haven't looked at this stuff in 3 or so years.

[Glass Pearl Player]

Those problems are sure nice ones! Spoilers ahead for those who haven't solved those from the OP (if didn't make any errors, that is):

0a) Surpisingly (for me) no. The radius of the inner sphere is sqrt(n)-1, and it exactly touches the hypercube for n=9.
0b) 9, if you are only allowed to place weights at one side. Then they will be powers of 2, ranging from 1g to 512g.
7, if you are allowed to place them at both sides. Then they will be powers of 3, from 1 g to 723g.
2) Sketch of proof by contradiction: Let m:=max(|f''(x)). By hypothesis, f' is continuous. Assume that f converges, but f' does not. Thus there is an e>0 such that for any x one can find an x1>x with |f'(x1)| >e. On an intervall [x1,x1+d], one therefore has |f'(x1)|>e/2. Estimating f(x1+d)-f(x1) by an integral then gives
|f(x1+d)-f(x1)|>e/2*d. Using boundedness of f'', we can estimate that d>e/(2*m). Therefore |f(x1+d)-f(x)|>e*e/(4*m), so either |f(x1)|>e*e/(8*m) or the same for f(x1+d). Either way, f does not converge towards zero.

[Grog]

That's excellent. Actually, I don't think it's true without the assumption that the probability of either of the two variables not being a non-negative integer is zero. Otherwise, it's not hard to 'shift' binomial distributions in that manner and thus get a counter-example (although not a very interesting one). But with that assumption, spoiler:
If X can only take on non-negative integer values, then the probability distribution must have a moment-generating function of M(t) = <exp(tX)> = Sum_X[ Pr(X) exp(tX) ] is a polynomial in e^t. By hypothesis, the mgf that is a polynomial in e^t with exactly one root. Hence the mgfs of the two variables, which must themselves be polynomials in e^t, must have only that root.

Yes your assumptions are correct, I didn't think it trough and made a mistake. The Stochastic variables can take any value in [n] and [m] respectively.

[Surlethe]

As I think about problem 0, it seems that the inner sphere will be growing while the spheres centered at (±1,...,±1), keeping constant radius 1, will shrink in volume because the unit radius 'doesn't go as far' in n-dimensions. According to mathworld, the volume of a unit hypersphere is S_n/n, where S_n, the volume of the surface, is given by [2π^{n/2}]/[Γ(n/2)]. So, as a function of n, the volume V(n) = 2π^{n/2}/[nΓ(n/2)].

As a sanity check, n = 1 gives Γ(1/2) = π^{1/2}, so V(1) = 2. Letting n = 2 gives Γ(1) = 1, so V(2) = π. Letting n = 3 gives Γ(3/2) = π^{1/2}/2, which implies that V(3) = [4π^{3/2}]/[3π^{1/2}] = [4/3]π, as we expect.

Mathworld, linked above, points out that S_n reaches a maximum and then decreases toward 0 as n grows. In some sense, this is because factorials grow faster than exponentials.

In ℝ^n, the maximum coordinate in any direction of the unit spheres will be (0,0,...,0,2,0,...,0); the unit spheres will all be contained in the hypercube, while, as glasspearlplayer notes, the inner sphere will extend beyond the box for n≥9.

Edit: Also, consider with regards to the 'derivative squeeze' problem this example: f:[2,∞)→ℝ given by f(x) = sin(x²)/log(x). This derivative actually does not go to 0, even though it's bounded.

[Glass Pearl Player]

Also, consider with regards to the 'derivative squeeze' problem this example: f:[2,∞)→ℝ given by f(x) = sin(x²)/log(x). This derivative actually does not go to 0, even though it's bounded.

I'm afraid you lost me here. For the first derivative I get cos(x^2)*2x/log(x) - sin(x^2)/(x*log(x)^2). The second term vanishes at infinity, the second one diverges due to x/log(x). Online Differentiation
The problem assumed a bound on the second derivative, which in your example diverges too.

[Surlethe]

Also, consider with regards to the 'derivative squeeze' problem this example: f:[2,∞)→ℝ given by f(x) = sin(x²)/log(x). This derivative actually does not go to 0, even though it's bounded.

I'm afraid you lost me here. For the first derivative I get cos(x^2)*2x/log(x) - sin(x^2)/(x*log(x)^2). The second term vanishes at infinity, the second one diverges due to x/log(x). Online Differentiation
The problem assumed a bound on the second derivative, which in your example diverges too.

Right. It's not supposed to be a counterexample; it just seemed to illustrate why you need a bounded second derivative.

[Kuroneko]

0a) Surpisingly (for me) no. The radius of the inner sphere is sqrt(n)-1, and it exactly touches the hypercube for n=9.
0b) 9, if you are only allowed to place weights at one side. Then they will be powers of 2, ranging from 1g to 512g.
7, if you are allowed to place them at both sides. Then they will be powers of 3, from 1 g to 723g.

Right on all counts. It may be added that the "balanced ternary" number base (ternary with digits {-1,0,+1}) not only has the obvious connection with this problem, but three is also the most efficient out of all integer bases, as measured by (number length [digits in number])*(base [total allowed digits]), with at most finitely many exceptions for each base.

2) Sketch of proof by contradiction: Let m:=max(|f''(x)). By hypothesis, f' is continuous. Assume that f converges, but f' does not. Thus there is an e>0 such that for any x one can find an x1>x with |f'(x1)| >e. On an intervall [x1,x1+d], one therefore has |f'(x1)|>e/2. Estimating f(x1+d)-f(x1) by an integral then gives
|f(x1+d)-f(x1)|>e/2*d. Using boundedness of f'', we can estimate that d>e/(2*m). Therefore |f(x1+d)-f(x)|>e*e/(4*m), so either |f(x1)|>e*e/(8*m) or the same for f(x1+d). Either way, f does not converge towards zero.

It is possible to refine it to be ε²/2m instead, although of course it doesn't make any difference for proof purposes. But this makes me curious as to the details on how you got the lower bound for d, since I do believe that it can be made tighter. [Edit: Oh, I think I see... but if you got it the way I'm thinking of, a similar kind of approach can be used to remove the necessity of the ε/2 condition from f'.] (Very minor nit: m should be supremum instead of maximum.)

In ℝ^n, the maximum coordinate in any direction of the unit spheres will be (0,0,...,0,2,0,...,0); the unit spheres will all be contained in the hypercube, while, as glasspearlplayer notes, the inner sphere will extend beyond the box for n≥9.

For n≥10.

Edit: Also, consider with regards to the 'derivative squeeze' problem this example: f:[2,∞)→ℝ given by f(x) = sin(x²)/log(x). This derivative actually does not go to 0, even though it's bounded.

Nice.

[Zadius]

OK, here's my attempt at solving problem 3:

To Prove: a² + b² + c² ≥ 4S√3 ,where a, b, c are the lengths of the sides of a triangle, and S is the area of the triangle.

Take the Law of Cosines: c² = a² + b² - 2abcos(C), and the sine formula for the area of a triangle: S = ½absin(C). Substituting these in gives us:

a² + b² + [a² + b² - 2abcos(C)] ≥ 2absin(C)√3; or
a² + b² ≥ ab[sin(C)√3 + cos(C)]

Now, 1 ≥ sin(x) and 1 ≥ cos(x), therefore;
1 + √3 ≥ sin(C)√3 + cos(C)
But this inequality is too weak, it can be improved upon by taking the derivative of f(x) = sin(x)√3 + cos(x) and setting it equal to zero.

0 = cos(x)√3 - sin(x)
sin(x) = cos(x)√3
sin²(x) = 3cos²(x)
1 - cos²(x) = 3cos²(x)
1/2 = cos(x)
x = π/3 ± nπ
These are the global extrema, the maxima can be easily shown to be π/3 ± 2nπ, one of which falls within the interval x = (0, π), namely x = π/3, which we need because the angle C can not be greater than π radians or less than 0 radians.

2 = sin(π/3)√3 + cos(π/3), therefore 2 ≥ sin(C)√3 + cos(C).
Hence: a² + b² ≥ 2ab; or
(a - b)² ≥ 0;
QED.