Dr. Straw, is there some hidden problem there? I thought he was just being a little inexplicit, by not writing "i.e. for all x, f(x) + g(x) = x".

_________________
Occupy Babel!

This is a much nicer version of the answer I tried to compose using clocks. But then, you're a mathematician.... so you would know how to do it right! I guess in these terms, I was thinking of f(x) = 2x, g(x) = -x. I think the idea was in my head, just didn't have the math to state it clearly!

There are very many nice properties of the zero ring. Any equation involving any of its elements are true.

Here's a problem related to Redundant's, and I'm not quite sure how I solved it since in my solution M/2 was still an infinite number.

Imagine 200 people in prison and the prison warden makes them a deal that if they can guess the color of the hat on their head they get to go free. The Warden, knowing the solution to Redundant's problem, decides to make it a bit harder on the prisoners and not only uses Black and White hats but uses Red, Green, and Blue hats as well.

So, the Warden with his five colors of hats decides to give the prisoners time to develop a strategy beforehand. When the judgment day arrives, so to speak, he is going to put all the prisoners in a room and ask them the color of their hat. If they get it correct, they can go free. If they are incorrect, they have to stay there and serve the remainder of their original sentence.

Obviously, they can see everybody else's hat and not their own.

What is the optimal solution for the prisoners?

_________________
My plan to become an SDK is here.

The infinite case still works the same as before

Finitely ... I'll have to think about this.


Another cool problem. Find two sets (A and B) that partition the naturals (including zero) subject to the following condition: for each n, the number of distinct unordered pairs in A that sum to n is the same as those for B.

Identity function: f(x)=x

Not that confusing.

The problem with that is probably that English is not my native language. That's why I've written the clarifying definition "f(x)+g(x)=x", because I was not sure if "identity function" is the correct word.


These functions are not periodic. There doesn't exist a d>0 such that f(x) = f(x+d).

Solution to Problem 1:


Correct.

More about problem #2:

Shaddy, my algorithm shows a paradox that arises by defining these equivalence classes. It's not even directly related to the original problem (though, of course, if the concept of equivalence classes is shown to be bogus, the original solution doesn't work). The fact that each individual lacks knowledge of one hat is not relevant for my algorithm.



I understand what you mean - my algorithm will never reach the point where all elements (or an infinite number, for that matter) are flipped. The point is, again, that there exists no way to find the equivalence classes either - any calculation will not finish in the same manner. So my technical problem is: how do you define this world? I am keeping in mind that this world is completely detached from reality! But you cannot say: "despite the fact that you can obviously never calculate for all elements, our solution algorithm is valid; but your algorithm is not valid because you can never calculate for all elements."

By the way, I couldn't agree more with your paraphrasing of Jaynes. Not beginning with finite models taken to the limit can lead to this kind of insanity .

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

I'll give a proof of the well definedness of the equivalence relation. We must check that it is reflexive, symmetric, and transitive.

Let a, b, and c be sequences of zero and one. a has zero differences with a, so the relation is reflexive. If a differs from b on some finite set, then b differs from a on the same finite set by the transitivity of equality. Now, if a differs from b on some set (of places in the sequence) S, and b differs from c on T, then a differs from C on at most cardinal of S union T places. Since both S and T are finite, their union is finite also.

Your notion seems to be one of computability, that we cannot ever actually tell whether or not two sequences are in the same equivalence class in finite time. This is true, but not relevant to the mathematics. It's just another example of how this algorithm is not possible in reality. However, mathematics is in no way meant to be a model for reality.

ah, yeah, i misunderstood your algorithm. red and bill have said everything i wanted to say now that i understand, though..

edit: i have thought of something to say. for any n finite, it will not halt. if we accept that it can compute infinitely like the people in the problem, then it will halt- but you've changed an infinite number of terms, so the equivalence still works.

EDIT: Shaddy came up with a very interesting point! My gut feeling is still protesting, but I'll have to sleep on it before I'll say anything more here .

@Redundant: OK, you just (I think) proved that the equivalence relation is well-defined when applied to a finite number of sets. Whether or not this automatically implies that the collection of equivalence classes forms a discrete basis set for all the infinite sequences of ones and zeroes is beyond me.

More importantly though, you did not really address my argument, which is pertinently NOT one of computability. I have stated many times that I am willing to accept infinite memory and runtimes. However, I will, yet again, repeat my problem, which you did NOT address:

I have provided an algorithm that, provided infinite runtimes are available, will give an inconsistency in your model. I would love to hear why this does not actually break your logic; unfortunately, it seems that no one here has a deep enough understanding of the math to explain this. That's fine, neither do I, but please either address this issue or admit that you don't know the answer!

_________________
My name is Gijs, from Utrecht, NL.

When in doubt, play the most aggressive move

Back to this, you say that because after infinite time, your algorithm gives a member of a new equivalence class means that there is some n where we actually change equivalence class. This is false.

Consider the sequence of (1/n) it converges to zero, yet no element of the sequence is nonzero. It's the same here, the "end result" of the process of changing finitely many elements at once an infinite number of times is in a different equivalence class, but at no point in the process do we change equivalence classes.

Shaddy, will you say a little bit more about your solution? It seems to me that a lot is riding on an ambiguity in "This" in the last sentence. You would agree, right, that when the Nth person recites his number, the maximum number of people who could have gotten their number wrong is "N", and that the number of people who have gotten their number right will be a binomial around N/2?

Yes they are: d=1. For example f(0.5) = f(1.5) = f(2.5) = 0.25

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).

As I said, that is only the identity function under the operation of composition, but the problem is one of function addition. The identity function under addition is f(x) = 0.

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).

Looking at the other people, each person will know which equivalence class they are in (as they only fail to know the state of their own hat). Thus everyone will guess based on the same representative of that equivalence class, which differs from the true distribution in only finitely many places.

It helps to know that the reals modulo one are isomorphic to the zero ring, that is that everything is zero. DrStraw's solution is correct as far as the problem statement is concerned, but a little underhanded, demonstrating that the problem is not sufficiently well defined.

I'm not sure if this will help anyone, but here is where I first heard of the infinite prisoners/hats puzzle--it has a fair bit of exposition. http://cornellmath.wordpress.com/2007/0 ... -is-wrong/

_________________
Occupy Babel!

But under the reals modulo 1, 1 = 0, therefore, d is not > 0
Or, if you define f as a function from the reals to the reals mod 1, f(x) != x. Either the functions are not periodic, or their sum is not the identical mapping (is that the correct English word?).