Life In 19x19

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?