Interesting math problems

[jemidiah]

I recently stumbled upon some math questions and spent the next several hours fiddling with them. My favorite of the set was the following:
Suppose f(n) is the number of 1's in the binary representation of the integer n. Compute the f(1)/(1*2) + f(2)/(2*3) + f(3)/(3*4) + ....

While that question is pitched at advanced undergraduate math majors, here's another that's a bit easier:
Suppose five distinct points are placed on the surface of a sphere. Show that four of them lie on some hemisphere.

One more:
Suppose you are given an ordered sequence of n whole numbers. Show that some consecutive subsequence has sum divisible by n. (Eg. given 1, 4, 2, we see that 4+2 = 6 is divisible by 3.)

Now my question: does anyone else have any similarly interesting problems they'd like to share?

[Lenggries]

Thanks for keeping me from falling asleep this weekend!

#2 is kind of like a trick question. It can seem difficult to prove until one hits upon the trick, at which point the solution is pretty trivial.

#3 this requires some level of familiarity of number theory, or at least abstract algebra. I think this one is much easier to recognize conceptually then it is to formalize, but the key is to understand the modulo operator.

#1 requires a knowledge of modes of convergence. I am WAY too rusty in that department to tackle this problem formally, but I wouldn't be shocked if the answer turned out to be the square root of 2 (highlight over text to see what I wrote).

_______________________________________________________________

While helping a friend with some number theory homework a couple years ago, I accidentally proved this. You may have seen this before, but if not, it may spark some curiosity:

The prime number 3 can be written as n^2-1, where n is a positive integer (in this case 2). What is the next prime number that can be written be written as n^2-1, where n is a positive integer?

[jemidiah]

Heh, yes #2 is really difficult unless you find the trick. (At least, I've been unable to make more than one proof.)

#3 can be done with only a basic knowledge of remainders, though of course a number theory/abstract algebra background in modular arithmetic is helpful there. My proof:

(highlight for #3 proof)
Suppose the numbers are a1, a2, ..., an. Compute a1; a1+a2; ...; a1+...+an. Divide each by n and suppose the remainders are r1; r2; ...; rn--recall that the remainders are between 0 and n-1, which is n possible values. If any remainder is 0, the corresponding sequence is the one we were looking for, so suppose that no remainder is 0. There are n-1 possible values then for n different numbers, so at least one remainder must be repeated.

Suppose then ri = rj (for i different from j; flip i and j if necessary so that i < j). That is, a1+...+ai and a1+...+ai+a(i+1)+...+aj have the same remainder after division by n. Subtract the first from the second to get a(i+1)+...+aj with remainder 0 since the two remainders cancel--this is the sequence we were looking for. Thus in all cases some such sequence must exist.

#1 actually requires less formal knowledge of series convergence than you might expect. The sum indeed exists, intuitively because the numerator grows at most logarithmally while the denominator is quadratic, so the p-test basically gives it. Since each term is positive the sum converges absolutely and so can be rearranged in whatever manner you like. Similarly some basic theorems allow the sum to be split into multiple (possibly infinite) nested sums, each of which can be done in any order--most any manipulation you'd expect to work will work in this case. That said, my solution used three summation identities, one of them being new to me; see below for details.

(highlight for #1 hints)
For any positive c and positive integer N,
sum of r from 0 to N-1 of 1 / [(c+r)(c+r+1)]
= N / [c(c+N)]

sum of p from 1 to infinity of 1 / [(2p-1)(2p)]
= ln(2)

sum of q from 0 to infinity of 1 / 2^q
= 2

[Final answer: 2 ln2, verified by brute force]

[boops boops]

Suppose five distinct points are placed on the surface of a sphere. Show that four of them lie on some hemisphere.

Are the five points regularly disposed? If not, I think I can prove the assertion is wrong. If it's any five points, then we can ignore the fifth point. The question is whether any four points must lie in the same hemisphere.

Consider the tetrahedron formed by the four points. Suppose it happens to be a regular tetrahedron. The centre of the sphere must lie inside the polyhedron, because its distance from all four corners is the same; if the centre were outside the polyhedron, it would be necessarily nearer the corners of the nearest face than to the apex on the other side.

Alternatively, you could compare the height of a regular tetrahedron of side a to the radius of its exosphere:

height = a * sqrt(2/3)
exoradius = a * sqrt(3/8)

Therefore height > exoradius: the centre of the sphere must lie nearer the apex than the distance between the base and the apex.

Since the centre of the sphere side lies inside the regular tetrahedron, all four apices cannot lie in the same hemisphere. Therefore the assertion is false in the case of a regular tetrahedron, and thus generally false.

Or were the points regularly spaced after all?

BB

EDIT: to come to think of it, the five points can't be regularly spaced in 3 dimensions because there isn't a Platonic solid with 5 apices.

[jemidiah]

@boops boops: Sorry if my question was unclear. It should read "show that some group of four of them lies on some hemisphere"--contrast this version with what I believe you used: "Any group of four of them must lie on some hemisphere". In the version I wished to use, there are five possible groupings, and one of them must work out. (I am completely certain my proof works for that version, by the way.)

[boops boops]

@boops boops: Sorry if my question was unclear. It should read "show that some group of four of them lies on some hemisphere"--contrast this version with what I believe you used: "Any group of four of them must lie on some hemisphere". In the version I wished to use, there are five possible groupings, and one of them must work out. (I am completely certain my proof works for that version, by the way.)

One thing is clear: the original question is unclear, at least to me. I'm still not sure I understand you. What are the five possible groupings, or it that meant to be obvious?
BB

[jemidiah]

Given points A, B, C, D, E positioned arbitrarily on the surface of a sphere, show that either
(A, B, C, D) lie on a hemisphere,
(A, B, C, E) lie on a hemisphere,
(A, B, D, E) lie on a hemisphere,
(A, C, D, E) lie on a hemisphere,
or (B, C, D, E) lie on a hemisphere.

It may well happen that (A, B, C, D) do not lie on a hemisphere (eg. if they form a tetrahedron, as you say), but in that case one of the remaining 4 cases must occur.

[boops boops]

Suppose A and E are the two furthest separated points out of the five. The points B, C and D define a plane which lies between A and E. Plane BCD also slices the sphere into two generally unequal sections (because B, C and D all lie on the surface of the sphere). If the part with A on it is smaller, A, B, C and D all lie in the same hemisphere (because the centre of the sphere is on the other side of plane BCD). Similarly, if the part with E on it is smaller, B, C, D and E all lie in the same hemisphere. If the two halves are equal, points B, C and D lie on a great circle so both ABCD and BCDE lie in single hemispheres.

Edit: oops, I'm not there yet. Points A and E don't necessarily lie on opposite sides of plane BCD.

Edit2: actually it's much easier. Take any two points (A and B) and slice the sphere into two exact hemispheres along the plane formed by A, B and the centre of the sphere. Any point on the rim of a hemisphere counts as being in both hemispheres. Consider these cases:
1. C, D and E all lie on the same hemisphere. All five points lie in the same hemisphere, no problem.
2. Two of the points (say C and D ) lie on one hemisphere and one (E) on the other. In that case, four points (A, B, C and D) lie on the same hemisphere.
3. There isn't a case 3.


BB

[jemidiah]

Heh, yup your second edit is the "trick" I was talking about. I've tried numerous far more complicated alternatives, but nothing else has worked out. It's a cute proof.

[Lenggries]

Yeah, that's the same 'trick' I used as well. The only caveat to using it is the statement "Any point on the rim of a hemisphere counts as being in both hemispheres", which I took to be an assumption. However, it is easy to prove that if the assumption does not hold, then the problem statement does not hold, either:

Assume that points lying on the rim of a hemisphere do not count as lying on the same hemisphere. Choose five equally dispersed points on the rim (such that they would form the vertices of a regular pentagon. In that case, there exists no more than any three points within the same hemisphere, which refutes the problem statement. Thus, the problem statement is true if and only if a point that lies on the rim of a hemisphere counts as being in both hemispheres.

[boops boops]

Since both the points and the great circle which divides the sphere into two halves have zero dimensions, I have no problem with the assumption. In your counterexample, wouldn't there be two and a half points lying in each hemisphere? BB

[jemidiah]

I happened to notice this bit of a previous post I had apparently missed:

While helping a friend with some number theory homework a couple years ago, I accidentally proved this. You may have seen this before, but if not, it may spark some curiosity:

The prime number 3 can be written as n^2-1, where n is a positive integer (in this case 2). What is the next prime number that can be written be written as n^2-1, where n is a positive integer?

Since n^2 - 1 = (n-1)(n+1), this is prime for n positive only possibly when n-1 = 1, so when n=2 (which indeed works).


Edit: Here's another one I find amusing; it's sometimes called the Sophomore's dream (you can google for a proof, though it's not terribly hard to make your own with a little calculus knowledge):

integral from 0 to 1 of x^(-x) dx
= sum from n=1 to infinity of n^(-n)

[jemidiah]

I ran across another interesting one. Using addition, subtraction, multiplication, and grouping symbols, and using "n!" at most once for each value of n=0, 1, 2, 3, ..., is it possible to generate every positive integer?

Examples:
1 = 1!
2 = 0! + 1!
3 = 2! + 1!
4 = 2! * (0! + 1!)
5 = 3! - 1!
6 = 4! - 3! * (2! + 1!)
...

[jcis]

I ran across another interesting one. Using addition, subtraction, multiplication, and grouping symbols, and using "n!" at most once for each value of n=0, 1, 2, 3, ..., is it possible to generate every positive integer?

Examples:
1 = 1!
2 = 0! + 1!
3 = 2! + 1!
4 = 2! * (0! + 1!)
5 = 3! - 1!
6 = 4! - 3! * (2! + 1!)
...

My knowledge on maths is basic, but how could someone show this one? I mean, i see each number needs a different formula, how to show it is true for all? Maybe using a series? looks like in this case F(x) = x

PS: (out of topic) i've always been intrigued by all the mysteries around the prime number series, do you think sombody will ever discover this series? Assuming this series actually exists but hasn't been found, do you think the answer could be found in the field of real numbers?

[Lenggries]

My knowledge on maths is basic, but how could someone show this one? I mean, i see each number needs a different formula, how to show it is true for all? Maybe using a series? looks like in this case F(x) = x

There are many ways to skin a cat, so to speak. Jemidiah likes to make me lose sleep with these puzzles, but I have resisted thinking too much about this one so far. I tend to categorize these kinds of number theory problems into one of several categories:
- easily provable once one arrives at a "trick" kind of like that five points on the surface of a sphere problem in the OP.
- provable by mathematical induction
- provable by contradiction
- provable by construction/derivation
- not provable by any known means (more on that in a moment)
- disprovable
- provable by Google

For this problem, I would first attempt to try induction, since it is a natural fit for the problem formulation. Otherwise, I'll likely try to use contradiction one way or another. Construction is not my strength.

PS: (out of topic) i've always been intrigued by all the mysteries around the prime number series, do you think somebody will ever discover this series? Assuming this series actually exists but hasn't been found, do you think the answer could be found in the field of real numbers?

No. The closest thing going is the Riemann hypothesis, which has been unproven for over a century, and it is possible that the Riemann hypothesis could be in fact one of Godel's unprovable theorems... aka a true statement that can never be proven to be true (don't read about Godel's incompleteness theorems unless you're prepared to see the world in a new way... it's kind of like Einstein's relativity). Time may or may not tell. In any case, if true, the Riemann hypothesis is probably the closest you can come to a method to predict the distribution of primes, but it's not like a simple function that you can input a number n and then the n'th prime pops out. There are functions that can do that, but they take too long to be practical (aka, if you want to find the 1,000,000,000,000,000,000,000,000,000,000,000th prime, prepare to wait a few million years).

[jemidiah]

With the most recent problem I posted, one should keep in mind that it may not be possible to write every positive integer in such a form. Since the constituents are factorials, "most" of the terms will share common factors, leaving "a few" terms to get the remainder right, and it's not immediately clear whether those "few" terms are sufficient for their task in all cases.

[Lenggries]

Well, that goes along the second to last category, of disprovable (or alternatively, (dis)provable by contradiction). In this case, however, that's not a trivial matter. Even if you find a number that is not constructable, it takes some skill to formally prove that it is not constructable (kind of like proving that a compass and straight edge cannot construct every angle in finite time).

I spent some time doodling this problem out last night, and constructed everything from 1-180 to pick up patterns. If there are non-constructable numbers, I suspect the first will be near a value n!/2. For example, 348 is near 6!/2, and that is a number that I haven't been able to construct yet.

[jemidiah]

If you consider the formula mod 6! = 720, each n! goes to 0 for n >= 6. If the proposition is true every remainder from 0 to 719 will then be reachable using formulas with only 0!, 1!, ..., 5!. This horribly inefficient Python code brute forces the calculation by trying all possible formulas of the relevant type. It turns out that 308, 352, 356, 364, 368, and 400 are not reachable--though 308 and 400 are if you allow an overall negative sign, as one should. Thus, these formulas cannot reach any numbers with remainders 352, 356, 364, or 368 after division by 720. In particular those four values cannot be reached, so not every number can be written in this form.

I don't know of a less computational approach. I suspect that as N gets large, there won't be enough truly different formulas considered mod N! to make things work out, thanks to the commutativity and associativity of addition and multiplication, but that computation seems abstractly difficult and it's potentially fruitless.

[Lenggries]

Hey there, you're supposed to print the solution in invisible ink

I'd already figured out that 352 (and thus 368, which is 6! - 352) were strong candidates for non-construction. I was trying to work out a proof using graph and set theory, by graphing out all the endpoints of the combinations of numbers and operations, counting them, and demonstrating that the set grows slower than the set of natural numbers, which would indicate some natural numbers cannot be constructed. However, counting the endpoints is not a simple task, as I couldn't figure out how to account for redundant endpoints.

[jemidiah]

Hehe, sorry, invisible ink next time then.

As for counting, I agree that's probably the way to go, but I'd need some computational evidence before I'd pursue it myself (something like 10% of the remainders being constructable mod 10!; around 99% are constructable mod 6!). The number of parenthesizations is easy to count using the Catalan numbers, and that grows relatively slowly [(2n)! / ((n!) (n+1)!)] compared to n!, slower than 4^n. The number of operator choices, 3^n, also grows slowly compared to n!. However, the number of ways to permute the numbers is n!; one needs to cut that down by a huge amount for the counting argument to work and I'm not sure if that's actually possible. It may be that the numbers just happen to not work out for 6! and do work for other bases. My code doesn't scale up well so I haven't pursued it computationally.

[Lenggries]

Well, it should be possible to count permutations while subtracting trivially equivalent permutations, by which I mean it should be easy to discount b*a given that I am counting a*b. The problem is eliminating instances when a*b+c = d-e. I'm not sure that can be done algorithmically. At best, I would expect an upper limit could be derived, but that limit may or may not exceed the factorial, and would probably be more difficult to prove than the original problem statement, making it kind of a moot point.

[jemidiah]

Given a particular formula like a*(b+c*(d+e*f)), there aren't many "trivially equivalent" permutations. e and f can be swapped in all cases giving 6! / 2 instead of 6! permutations. There's so many other formulas with 6 terms though that one needs to cut down the possibilities immensely for this method to yield the result. One can swap the additions as well though that gives a different formula and makes counting truly distinct expressions more difficult. Actually this does give rise to an interesting sub-problem that I've made another thread about.

[jcis]

When you're done with that one, wanna play find the generic series? i'll start with this one:

For (x_0->n) find F(x), first 30 results are:

27
3,375
1
0,421875
0,216
0,125
0,078717201166
0,052734375
0,037037037037
0,027
0,020285499624
0,015625
0,012289485662
0,009839650146
0,008
0,006591796875
0,005495623855
0,00462962963
0,003936433882
0,003375
0,002915451895
0,002535687453
0,002219117284
0,001953125
0,001728
0,001536185708
0,001371742112
0,001229956268
0,00110705646
0,001
0,000906313987

[jemidiah]

Answer: 27/N^3.

Another:
0
-85/108
-35/27
-7/4
-64/27
-365/108
-5
-805/108
-296/27
-63/4

[The fractions are in lowest terms.]

[jcis]

Answer: 27/N^3

Very good, I see you've even simplified the one i used (answer): (3 / (x + 1)) ^ 3

[jemidiah]

I figured I could start with index 1 or index 0 as I saw fit . Of course I started with 1 there. Mine is neater if you start it at index 0 (as a 0 first term might suggest).

[jcis]

Can't find the pattern in yours just by looking to those numbers , If i make a graph + trial and error i can see Fx = -(1 / 72 * (x ^ 3)) - 1 is close, but i'm not going anywhere by doing this i think.

[jemidiah]

As a hint, try plotting the differences between successive numbers and see if there's a somewhat reasonable pattern.

Edit: those differences are
-85/108
-55/108
-49/108
-67/108
-109/108
-175/108
-265/108
-379/108
-517/108

[jemidiah]

I got to thinking I may have made it a little too hard because of the use of a pair of identities that may be stumbling blocks. So, my solution is below.

Solution: Plotting the successive differences listed in my previous post, one finds they form a parabola. The numerators are formed by the quadratic -(12 n^2 - 66n + 139). Thus we have the relation
f(n) - f(n-1) = -(12 n^2 - 66n + 139)/108

Using a telescoping sum, we can then compute f(n) where n starts at 0 as follows:
f(n) = f(n) - f(0)
= [f(n) - f(n-1)] + [f(n-1) - f(n-2)] + ... + [f(1) - f(0)]
= sum_k=0^(n-1) of f(n-k) - f((n-k)-1)
= -1/108 * sum_k=0^(n-1) of (12 (n-k)^2 - 66 (n-k) + 139)
= -1/108 * sum_k=0^(n-1) of (12 n^2 - 24 nk + 12 k^2 - 66n + 66k + 139)
= -1/108 * [[12 n^2 - 66n + 139] * n
- (24*n - 66) * sum_k=0^(n-1) of k
+ 12 * sum_k=0^(n-1) of k^2]
= -1/108 * [12 n^3 - 66 n^2 + 139 n - (24n - 66) * n * (n-1) / 2 + 12 * (n-1) * n * (2n-1) / 6]
= ... = -n^3 / 27 + n^2 / 4 + -n
= (-n/3)^3 + (-n/2)^2 + (-n/1)

The sums disappeared using the formulas sum_k=0^(n-1) of k = n*(n-1)/2 and sum_k=0^(n-1) of k^2 = (n-1)*n*(2n-1)/6. These are well-known identities and are special cases of Faulhaber's formula. These two can be proven inductively pretty easily (and IIRC I did so on this very forum a while back). The first has a cute geometric proof if you think in terms of triangles (indeed the numbers on the right side are called triangular numbers). The ... steps are just mindless simplification.