Math puzzles

[flOvermind]

Judging from the trolling thread, it seems there are several people on this board that are interested in math puzzles.
So here is a thread where people can post math puzzles, and try to solve them

To get things going, here is an interesting puzzle that I stumbled upon some time ago:

Puzzle 1:
Find two periodic functions f and g, such that their sum is the identity function (that is, f(x) + g(x) = x).
(A function is periodic iff there exists a d > 0, such that for all x: f(x+d) = f(x).)

EDIT: Corrected the definition of "periodic function". In the original version, the puzzle would have been a bit too easy

[DrStraw]

I think you mean "there exists a d > 0"

[flOvermind]

I think you mean "there exists a d > 0"

Of course. Stupid me, otherwise every function would be periodic
I edited the original post.

[tundra]

Not a solution, just an observation:

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...

[hyperpape]

A constraint, but nothing near a solution:

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.

[fwiffo]

I think you've just trolled my brain.

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.

[Redundant]

Another problem to think about

A countably infinite number of people are given black or white hats. Each is then asked what the color of their own hat is. They are allowed to discuss strategy beforehand, but not allowed to see their own hat, or exchange information after the hats are distributed. Find a strategy with which only finitely many people will be incorrect in their guesses.

Hint:

Use the axiom of choice.

[hyperpape]

Don't you need to specify that they're ordered, and that they can see the hats of people after them in the line?

@Redundant:

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

[Marcus]

I love this thread, despite having no formal training in Math beyond first year
Uni (and a few 2nd and 3rd year applied physics courses).

Putting some ideas together, we'll see how far I get.

In regards to Red's problem, I've heard the paragraph before, but never the solution. Should be interesting.

[Redundant]

I don't assign the people given hats any order, but if the people decide to number themselves, that's ok. They can see everyone else. Also, they have infinite memory and computing power.

The previous hint gives very little away, so here's a bigger one if anyone is still interested:

Look into equivalence classes of some convenient equivalence relation.

Also, one can consider the finite case, where a greater than fifty percent average success rate is impossible. Try to find a strategy that maximizes the worst case success rate. It doesn't help at all in the infinite case, but is interesting.

[GoCat]

I'm no mathematician... but maybe I can convince someone this is a solution.

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?

[Redundant]

flOvermind:

What exactly are the domain and codomain for these functions?

[Suji]

Here's a possible solution to Redundant's problem:

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.

@Redundant: In the finite case, all but one can be guaranteed to go free.

[Redundant]

Interesting solution, suji. In fact, I misstated the problem, but you solved my poorly worded one very nicely.

I should add that the people are taken off into seclusion for their guess, so they have no information on the guesses of the other people.

[GoCat]

.... They are allowed to discuss strategy beforehand, but not allowed to see their own hat, or exchange information after the hats are distributed.

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?