Suppose that f and g have the same period d. We have:

(1) f(x) + g(x) = x

Replace x by x+d throughout:

(2) f(x+d) + g(x+d) = x+d

But f(x+d) = f(x), g(x+d) = g(x), so (2) simplifies to:

(3) f(x) + g(x) = x+d

Subtracting (1) from (3) gives d = 0 - a contradiction, as we must have d > 0.

So, we conclude that whatever the functions f and g are, they must have different periods.


I'm curious to see the solution. I tried differentiating (1) to give:

f'(x) + g'(x) = 1

...and obvious candidates are f'(x) = sin^2(x) and g'(x) = cos^2(x). Integrating gives (along with additive constants):

f(x) = -1/2 sin(x) cos(x) + x/2
g(x) = 1/2 sin(x) cos(x) + x/2

But these are not periodic (because of the x/2 terms), so this is not a solution. In fact, I am beginning to wonder if the solutions f and g are even differentiable...

I believe you can improve on tundra's comment. If f(x) has period d, and g(x) has period d', then you can't have any l = nd = md' for n,m as natural numbers. Otherwise, (f+g)(x) = (f+g)(x+l).

As a consequence, d/d' must be an irrational number.

My math is not that advanced, I expect that this requires some pretty heavy number theory.

I am certain that the period of at least one of the functions must be an irrational number, probably any irrational number. Otherwise their sum would be periodic at their lease common multiple. The functions are discontinuous, and very strange.

Let's let the period of f be 1, and the period of g be some irrational number d, let's say d = sqrt(2) for convenience. And let's define f(0) = 0. So...

f(0) = f(1) = ... = f(n) = 0
g(0) = g(d) = ... = g(md) = 0
f(d) = f(d+1) = ... = f(d+n) = d
g(d+1) = g(2d+1) = ... = g(md+1) = 1
f(2d+1) = f(2d+2) = ... = f(2d+n) = 2d
g(2d+2) = g(3d+2) = ... = g(md+2) = 2
...
f(md+n) = md
g(md+n) = n

Where m and n are integers.

That's all I've got. It means that f(x) and g(x) for non-integer rational values of x is something weird. And probably most irrational values of x too.

Use the axiom of choice.

You're sick...will anyone really get this without having seen it before?

Look into equivalence classes of some convenient equivalence relation.

It's a trick, really. And I don't recall the right terminology from my college days.

And just for fun, I'll illustrate my solution with clocks...

That is to say, the number system in my solution is signed clock time, from (say) -12:00 to 11:59.99999... So, image a clock with 0:00 at the top, and +/- 12:00 at the bottom. +6:00 is on the right, and -6:00 is on the left.

The only operator in this system is addition. Naturally, adding 01:00 and -01:00 yields 00:00. And, addition is "modulo" the clock face. In other words, when adding two values that exceed 12:00, the result is now negative, and when adding two values that are less than -12:00, the result is positive.

Now, imagine one clock going forward at twice the the "normal" rate, and a second clock going backward at the normal rate. That is, f(x) = x + x, and g(x) = -x. Obviously, these are both periodic functions. Then the sum, f(x) + g(x) is simply x.

Example; let x = 05:00. The clock F shows 10:00, and clock G shows -5:00, the sum is 05:00. Next, let x = 07:00. Now F shows (07:00 + 07:00 = -10:00), and G shows -07:00. the sum is now 07:00.

basically, to add a positive number you advance clockwise on the clock; to add a negative number, move anti-clockwise.

Why did I use clocks? To illustrate the circular nature of my number system.

Is this a cheap trick, or what?

One of the math professors at my university gave a talk on this very subject. He didn't go into the infinite case, though.

Here's the solution for the finite case. Basically, since the hats are Black and White we can number them 0 and 1, respectively. Thus, if there were six people in line, the back person of the line would add up the numerical value of all the hats in front of him mod 2. He then calls out that number. The person in front of him, person 2, would add up the values in front of him and doing some arithmetic would know the color of his hat AND the color of the person's hat behind him.

Person 3, however, has to keep track of both numbers called out do some arithmetic, figure out the color of his hat and call out the correct color of his hat, also. So on and so forth.

This method will guarantee that 5 out of the 6 people go free. The person in back has a 50% chance of going free.

Can I extend this to the infinite case? I think so.

I believe that the infinite case is still solvable, and there has to be another piece of information given out. Let's also assume that since there are a countably infinite number of people, there is a one-to-one relationship from the number of people to the natural numbers. The person in the back of the line is person 1, the person in front of him is person 2, the person in front of person 2 is person 3, and so forth.

Also, let Black hats correspond to the number 0, and let White hats correspond to the number 1, again as in the finite case. Since the people are allowed to discuss a strategy before hand, they decide to stick with modular arithmetic as in the finite case. However, here is where they must decide on something.

In the finite case, we had a stopping point, namely the end of the line. However, in the infinite case, no such end of the line exists. Therefore the people have to decide on an arbitrarily large number 'N' that person 1, person N+1, person 2N+1, person 3N+1, and so forth will be the start of a "new" line, so to speak. So you have an infinite number of lines the original is broken up into. There is only a finite number of people in each new line so the finite case applies to each new line. Thus you have a countably infinite M number of people that had a 50% choice of being either correct or incorrect, so M/2 is the expected number of people that get it correct. So, really you only have at most M/2 being incorrect.

But, M/2 is an infinite number, so it doesn't help us. Hopefully, I'm on the right track, and someone can fix this.

In Suji's solution, aren't the people exchanging information after the hats are distributed? (When the person at the end of the line calls out a number.) What am I misunderstanding, here?

fwiffo has already found most of what I have. I prefer to simplify things a little and think of the problem as being about finding only one function f - this determines g uniquely since we know that g(x)=x-f(x). So the function f has the properties that there exist positive real numbers d and e such that f(x+d)=f(x) and f(x+e)=f(x)+e for all x. As in fwiffo's post, it then follows easily that, for any integers a and b, f(x+ad+be)=f(x)+be.

The only observation I can really add at the moment is that, since we already know that d and e must be incommensurable (another way of saying that d/e is rational), I'm pretty sure that it follows that those reals of the form ad+be are dense in the reals. In other words, given any interval, no matter how small, there exists at least one - and hence in fact infinitely many - numbers of this form inside the interval.

Combining this with what we know about the behaviour of f, I'm pretty certain that this will mean that f can't possibly be continuous - although I can't come up with a totally convincing proof just yet.

But of course, there are far more non-continuous functions that there are continuous ones, so even if I'm right, it doesn't rule out there being a solution. It just means it'll be something pretty weird...

I have not tried to prove this, but I'm pretty sure they are not differentiable or even continuous, and also certainly not Riemann-integratable. I'm not really sure about Lebesgue-integratable


Good observation. Note that you have only shown that *one of* d and d' must be irrational. But that's not so important I think.


Correct so far


Correct, too.

You need the axiom of choice to actually construct a function with these properties.

As some people have already figured out, the periods of the two functions can not be commensurable. Therefore, it won't work with rationals.

Actually, one of the functions in my solution is from the reals to the rationals.

Neither f(x) nor g(x) can be finite at any point in their periodic cycle.

Proof (sloppy, I know. I'm a physicist, not a mathematician):
Since f(x)+g(x) == x, and x runs from negative infinity to positive infinity, the sum of the two must also go to negative infinity for x -> neg. inf. and to positive infinity for x -> pos. inf. Therefore, as x goes to infinity, either f(x) or g(x) must always also go to infinity. But because of periodicity, this means that for ALL x, one of the two functions must be infinite. If only one of the two functions would be infinite, the sum of the two would be infinite as well. Thus, both must be infinite.

Maybe one can also conclude that one function must be always positive infinity, and the other always negative. My math is a little bit too shaky to be sure of that, but it does feel like a reasonable idea.

I suppose we now have to do some smart trick using the phase difference of the two functions. I'll have to think about that a bit further.