Life In 19x19

GoCat wrote:

Redundant wrote:.... 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?

tundra wrote: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

hyperpape wrote: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.

fwiffo wrote: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

robinz wrote: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.

Redundant wrote:What exactly are the domain and codomain for these functions?

gaius wrote: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.

flOvermind wrote:

gaius wrote: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 wrote: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.

gaius wrote: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.

tundra wrote: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.