Math puzzles

[Redundant]

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

Nothing, I just forgot how I'd stated the problem . These problems are very difficult to state correctly, as even slight miswordings can make the problems much easier or harder.

[gaius]

Redundant, I've seen variations of the problem before, but get the impression that, following your specification, it must be unsolveable. If anyone sees a mistake in the reasoning below, I'd be interested!

First, you give no distribution of the colour of hats (maybe it's fifty-fifty, maybe it's only black hats? who knows). Therefore, there is absolutely no correlation between the colour of the hats that one can see and the colour of one's own hat. Then you say that there is no information exchange possible. Therefore, all that an individual can see is the colour of a bunch of hats, which is completely unrelated to the colour of his own hat and, therefore, useless information. Whatever any individual guesses, there will always be a chance that he's wrong. Since that holds for all individuals, there is no minimum on the number of people that guess wrongly. They just don't have any information!

One question: in what order are people are taken to the secluded room to guess their colour? I presume this is either completely random or fixed beforehand? Otherwise, the timing of walking away and stating your guess would be a form of information exchange.

[robinz]

Some further thoughts on flOvermind's original problem:

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

[flOvermind]

First a general comment: I think it would be a good idea to number the problems, and also number the answers, so everyone can see at first glance what problem a post is directed at

Now a few comments regarding Problem 1:

Answers to some attempts:

In fact, I am beginning to wonder if the solutions f and g are even differentiable...

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

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

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.

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

Correct so far

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.

Correct, too.

Hint:

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

What exactly are the domain and codomain for these functions?

I didn't specify that on purpose, to see what you come up with
But since most people are concentrating on real functions anyway: My solutions are functions from the reals to the reals.

Trivial observation:

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

Another hint:

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

[gaius]

Further observation on Problem #1:

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.

[Shaddy]

problem 2:

Take the equivalence on infinite sequences of 0s and 1s that two sequences are equal iff they differ in finitely many places. Each person knows all of the equivalence classes and they agree on a specific sequence for each equivalence class. By the axiom of choice, they can do this. When the hats are distributed, the people line up and this is one of the equivalence classes - (since each person is only one person, it will not change the finiteness of how the sequence differs from the others in the class) so each person recites whether there is a 0 or 1 in that place in the memorized sequence. This differs in at most finitely many places from the memorized sequence, so only finitely many people can get it wrong.

[hyperpape]

@gaius The original statement of Redundant's problem is solveable, however much it looks like it isn't.

[gaius]

Shaddy, your "proof" sounds like it comes from a textbook somewhere, but all my mathematical intuition screams that there must be a flaw in this logic. As I said before, I'm not a mathematician but a physicist - I like to think in terms of concrete stuff.

My first thought was that the whole conclusion seems to conflict with information theory; you generate information where there is none. Can you disprove this line of reasoning? Thinking further though, your "proof" does not do anything for finite sets except for the trivial observation that, with a finite set of people, the number of errors is also finite. You are not really boosting the accuracy rate, you're only making sure the amount of errors is not infinite (right?). Maybe that could lift my objection, though my math is not good enough to really be certain.

After thinking a bit more, I have far greater problems with the following paradox. You imply that, for every infinite sequence of ones and zeroes, it is possible to find a uniquely defined equivalence set. Accepting that, let's evaluate this "algorithm" (it has infinite runtime, but apparently such an algorithm is acceptable in your paradigm!):

1. Take an infinite sequence of ones and zeroes.
2. Change the first element. By definition, the resulting sequence will still be in the same equivalence set as the original one (there is only one mistake!).
3. Now, do the following: IF we are in the original equivalence set, change the next (second, third, etc.) element. ELSE, halt.
4. Repeat (3) for all elements.

Now, obviously, after repeating for all elements, the list will not be in the same equivalence set any more. Therefore, we conclude that after some number of steps (let's call it n), (3) must halt. But then, despite only having one difference, the list at step n-1 and at step n are not in the same equivalence set!

Paradox?

[flOvermind]

Further observation on Problem #1:

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.

Not quite correct.

You are right that on any (non-empty, open) interval, at least one of the functions must be *unbounded*. That is, for any (arbitrarily large) value y and any interval I, there is an x in I such that |f(x)| > y or |g(x)| > y.
The proof is relatively simple:
Assume the opposite, that is, there is a (non-empty, open) interval I, such that f(I) is bounded by M and g(I) is bounded by N.
Let's say d := period of f, e := period of g.
Now we take an arbitrary x in I, and choose two naturals n and m such that x + n*d > M+N and x + n*d - m*e is in I.
(Proof that this is possible is omitted, basically, it follows from the rationals being dense in the reals).
Now we have:
M+N < x + n*d = f(x + n*d) + g(x + n*d) = f(x) + g(x + n*d - m*e) < M+N (because in I, f is bounded by M and g is bounded by N)
And that's a contradiction.

And of course, from that it trivially follows that *both* functions have to be unbounded on every interval. Because g(x) = x - f(x), if one of them is unbounded on some interval, the other has to be unbounded on the same interval, too.

But being *unbounded on any interval* is very different from being *infinite*. Both functions have a concrete, numerical, finite value at every point.

[gaius]

Further observation on Problem #1:

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.

Not quite correct.

You are right that on any (non-empty, open) interval, at least one of the functions must be *unbounded*. That is, for any (arbitrarily large) value y and any interval I, there is an x in I such that |f(x)| > y or |g(x)| > y.
The proof is relatively simple:
Assume the opposite, that is, there is a (non-empty, open) interval I, such that f(I) is bounded by M and g(I) is bounded by N.
Let's say d := period of f, e := period of g.
Now we take an arbitrary x in I, and choose two naturals n and m such that x + n*d > M+N and x + n*d - m*e is in I.
(Proof that this is possible is omitted, basically, it follows from the rationals being dense in the reals).
Now we have:
M+N < x + n*d = f(x + n*d) + g(x + n*d) = f(x) + g(x + n*d - m*e) < M+N (because in I, f is bounded by M and g is bounded by N)
And that's a contradiction.

And of course, from that it trivially follows that *both* functions have to be unbounded on every interval. Because g(x) = x - f(x), if one of them is unbounded on some interval, the other has to be unbounded on the same interval, too.

But being *unbounded on any interval* is very different from being *infinite*. Both functions have a concrete, numerical, finite value at every point.

Good point! Always interesting, these mathematicians with their non-well-behaved functions . Anyway, I did get quite far with a solution of problem #1, though you'll probably say my solution is not complete:

I just devised two periodic functions F and G (Reals->Reals) with periods d and d+epsilon, respectively. They are:
f(x) = -(x mod d) / epsilon
g(x) = ((1+epsilon)*x mod d) / epsilon
If we now take the limit of epsilon going to zero, then every individual point converges to f[x]+g[x]=x. Problem is, there will still be infinitesimally small areas n*d < x <= n*(d+epsilon) where the two are not equal. For an illustration, see this quick Mathematica plot I just made for d=1, epsilon=0.01:

convergence-plot.gif (5.57 KiB) Viewed 8411 times

Of course, in the limit epsilon -> 0, both individual functions F and G go to infinity.

[fwiffo]

The axiom of choice is obviously baloney. It's a rule mathematicians came up with to get out of doing work.

Bertrand: "Hey boss, I'm taking off early to go fishing."
Boss: "Have you finished that TPS report yet?"
Bertrand: "It is possible for me to do the TPS report, so we can just take it for granted that I did."

[Redundant]

Redundant, I've seen variations of the problem before, but get the impression that, following your specification, it must be unsolveable. If anyone sees a mistake in the reasoning below, I'd be interested!

First, you give no distribution of the colour of hats (maybe it's fifty-fifty, maybe it's only black hats? who knows). Therefore, there is absolutely no correlation between the colour of the hats that one can see and the colour of one's own hat. Then you say that there is no information exchange possible. Therefore, all that an individual can see is the colour of a bunch of hats, which is completely unrelated to the colour of his own hat and, therefore, useless information. Whatever any individual guesses, there will always be a chance that he's wrong. Since that holds for all individuals, there is no minimum on the number of people that guess wrongly. They just don't have any information!

One question: in what order are people are taken to the secluded room to guess their colour? I presume this is either completely random or fixed beforehand? Otherwise, the timing of walking away and stating your guess would be a form of information exchange.

The order is irrelevant to the solution I have. There is in fact a solution. If anyone wants to check me on this, here it is.
Solution:

First, give the people any numbering you want. Then look at the set of all mappings from the naturals to the set of all infinite sequences of black and white. Define two sequences to be equivalent if they differ in finitely many places. Then, using the axiom of choice, choose one element from each equivalence class, and have all the people memorize it. When they see the hats of the other people, that distribution will fall into one of the equivalence classes (since they don't know only one hat, their own), and thus will differ from one of the sequences they memorized in only finitely many places. They then guess the color given by the sequence they memorized. One can check that each person will guess based on the same representative of an equivalence class, so there will only be finitely many places where the guesses will differ from reality.

Note: I'll come back and edit this to be more readable later. I have to get to class right now.
Also: Shaddy just ninja'd me.

[tundra]

A possible solution to Problem 1, though using complex-valued functions in the complex plane:

We want f(z) + g(z) = z, where z = x + i*y, i such that i^2 = -1
i.e., x = Re(z) = the real part of z, y = Im(z) = = the imaginary part of z.

Define f(z) = f(x+i*y) = x - sin(x) + sin(y)
Note that f(z) has period d = 2*pi*i: When z changes by d, its real part, x, is unchanged, so x - sin(x) does not change either. Its imaginary part, y, changes by 2*pi, but this is just the period of sin(y). So f(z) is unchanged.

Similarly, define g(z) = g(x+i*y) = i*y + sin(x) - sin(y)
When z changes by d' = 2*pi, y is unaffected, and we just have the periodicity of sin(x).

So f and g are both periodic, with periods d = 2*pi*i and d'= 2*pi, respectively.

And when we take their sum, the sine functions all cancel, leaving us with:

f(z) + g(z) = x + i*y = z, as desired.

[flOvermind]

Good point! Always interesting, these mathematicians with their non-well-behaved functions . Anyway, I did get quite far with a solution of problem #1, though you'll probably say my solution is not complete:

I just devised two periodic functions F and G (Reals->Reals) with periods d and d+epsilon, respectively. They are:
f(x) = -(x mod d) / epsilon
g(x) = ((1+epsilon)*x mod d) / epsilon
If we now take the limit of epsilon going to zero, then every individual point converges to f[x]+g[x]=x. Problem is, there will still be infinitesimally small areas n*d < x <= n*(d+epsilon) where the two are not equal. For an illustration, see this quick Mathematica plot I just made for d=1, epsilon=0.01:

convergence-plot.gif

Of course, in the limit epsilon -> 0, both individual functions F and G go to infinity.

Hehe... Nice try, but the problem is that even though f+g converges and is (almost*) equal id, the individual functions f and g do not converge, hence are not really functions. I'm too lazy at the moment to try and verify your solution under the assumption that f and g are allowed to be distributions

There is a solution with proper functions, you don't need distributions. And in the correct solution, (f+g)(x) = x everywhere, not just almost* everywhere

(*Almost, of course, meaning that the exceptions have a Lebesgue measure of zero).

[gaius]

A possible solution to Problem 1, though using complex-valued functions in the complex plane:

We want f(z) + g(z) = z, where z = x + i*y, i such that i^2 = -1
i.e., x = Re(z) = the real part of z, y = Im(z) = = the imaginary part of z.

Define f(z) = f(x+i*y) = x - sin(x) + sin(y)
Note that f(z) has period d = 2*pi*i: When z changes by d, its real part, x, is unchanged, so x - sin(x) does not change either. Its imaginary part, y, changes by 2*pi, but this is just the period of sin(y). So f(z) is unchanged.

Similarly, define g(z) = g(x+i*y) = i*y + sin(x) - sin(y)
When z changes by d' = 2*pi, y is unaffected, and we just have the periodicity of sin(x).

So f and g are both periodic, with periods d = 2*pi*i and d'= 2*pi, respectively.

And when we take their sum, the sine functions all cancel, leaving us with:

f(z) + g(z) = x + i*y = z, as desired.

Hehe, that's a nifty way around the real problem . Though, I suppose this depends on your definition, but I don't believe the inequality 2*pi*i > 0 holds. Perhaps the problem should be rephrased for absolute clarity: rather than "d > 0" it could say "real d > 0".