Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

100 mathematicians, 100 rooms, and a sequence of real numbers


  • Please log in to reply
18 replies to this topic

#11 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 28 July 2013 - 01:54 AM

No shenanigans.

I'll be the judge of that :P
That is, if I decide I've had enough of this problem and just ask for the solution you two seem to have in mind. Which is not yet.
  • 0

#12 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 28 July 2013 - 02:52 AM

Rainman's post #4 has all the additional conditions necessary to solve.

(Including the Edit in my previous post.)


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#13 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 29 July 2013 - 03:43 PM

I finally had enough and went ahead and googled the OP. I've got to say, after looking at the solution they proposed, I would definitely place it in the category of "shenanigans". But maybe I'm missing something.

Spoiler for My understanding of their solution

  • 0

#14 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 29 July 2013 - 05:08 PM

You're missing that they are not just using one template sequence. They define equivalence classes by how a sequence ends, so that two sequences belong to the same class if and only if they are different in only finitely many places. Then they choose one template sequence from each equivalence class.
  • 0

#15 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 29 July 2013 - 11:38 PM

Spoiler for solution explained


  • 0

#16 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 30 July 2013 - 07:24 AM

I call shenanigans because I see no reason to presume that an infinite sequence of real numbers can be guaranteed to have a value of N at which it starts matching a template sequence for all elements >= N. And it's easy to give a counterexample.

 

This touches on a crucial idea required by the mathematicians' strategy. It must be understood before being used. It's the idea of equivalence classes. We'll first explore what they are by finding a way to construct them. Then we'll see how the math guys used them. So, let's take a minute to gather all the infinite sequences of real numbers of infinite length that exist, and lay them out here on my dining room table. 

 

Pick a sequence at random; call it sequence A. Quickly glance at all the other sequences, ignoring the initial finite number of terms. When a sequence, (call it sequence X) is found for which the remaining infinite terms agree with the corresponding terms in A, then we group X with A. Put that process into an infinite set of infinite DO loops [my FORTRAN is showing] and finally we get an infinite number of classes of infinite sequences. These are the equivalence classes needed to implement the math guys' strategy. Mull over that process so that you can define these classes in your own words.

 

The classes by themselves are too clumsy to use. We have to simplify matters. Enter the Axiom of Choice. Without it, the math guys remain locked in their rooms. AC is just this: There is a particular sequence, chosen from each class, that can be used to represent that class. So, for every infinite sequence of real numbers, it belongs to a unique equivalence class, and there exists a single, unique infinite sequence that can be used to represent it. Those are the vital ingredients: classes and their uniquely chosen representatives.

 

AC has importance only for infinite sets. Unique representatives of finite sets are not troublesome. But for infinite sets unique representatives are problematical. It cannot be proven. It must be inserted into the process as an axiom. And by the way, asserting a unique representative is not the same as finding it. So our math guys are only theoretical winners by this strategy. We don't get picky about that, even though the numbers in the boxes are real, the math guys aren't. This is only a puzzle.

 

Without AC, the math guys can't translate an infinite sequence into a unique representative sequence. So they can't predict any term of any real sequence they encounter in their rooms. But with AC, they can.  They just run a quick check of the final infinite number of terms. When they find congruence, they know its equivalence class. Using AC they find [but see the above disclaimer as to how they do this] the representative of that class. That identifies all the remaining real numbers that follow a finite number of differing ones. They just have to get sufficiently far out into the sequence to know that have skipped the differing numbers.

 

The rest of the strategy is easy to understand. One of them might have the wrong cutoff point, where the differing numbers end, and give the wrong number contained in a selected box. But there is at most one such guy. And 99 out of 100 is a win.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#17 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1461 posts
  • Gender:Male

Posted 30 July 2013 - 02:36 PM

Ah, thanks Rainman and Bonanova. That actually makes sense (which is sort of frightening).

Suppose we want to make things easier for the poor mathematicians who don't have infinite memories. For each equivalence class, we choose the representative sequence in that class such that x1 = 1, x2 = 2, x3 = 3 .... until we reach a point N out in infinity-land where it starts matching every subsequent term in the class. We know that such a point must lie infinitely far out since for any N if your representative sequence stops following x(N) = N and starts following the equivalence class' sequence, you can define a sequence which has x(N) = N and then starts matching the equivalence class for all subsequent terms. Since there is thus no finite limit to how large N can be, each representative sequence will be x1 = 1, x2 = 2, x3 = 3 ... for an infinite number of terms.

If the proposed solution using the axiom of choice works, then it should work using these representative sequences.

So if a mathematician guesses the value in any box numbered M in his subsequence, he must guess that it contains the value M.

Now I'm going to set up the boxes so they all contain negative numbers.

Edited by plasmid, 30 July 2013 - 03:30 PM.

  • 0

#18 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 143 posts

Posted 30 July 2013 - 04:40 PM

Ah, thanks Rainman and Bonanova. That actually makes sense (which is sort of frightening).

Suppose we want to make things easier for the poor mathematicians who don't have infinite memories. For each equivalence class, we choose the representative sequence in that class such that x1 = 1, x2 = 2, x3 = 3 .... until we reach a point N out in infinity-land where it starts matching every subsequent term in the class. We know that such a point must lie infinitely far out since for any N if your representative sequence stops following x(N) = N and starts following the equivalence class' sequence, you can define a sequence which has x(N) = N and then starts matching the equivalence class for all subsequent terms. Since there is thus no finite limit to how large N can be, each representative sequence will be x1 = 1, x2 = 2, x3 = 3 ... for an infinite number of terms.

If the proposed solution using the axiom of choice works, then it should work using these representative sequences.

So if a mathematician guesses the value in any box numbered M in his subsequence, he must guess that it contains the value M.

Now I'm going to set up the boxes so they all contain negative numbers.

 

Unfortunately foor the mathematicians, that doesn't work. But it is a good example illustrating the difference between arbitrarily large and infinite. You are right that the mathematicians can choose a number N, and let each representative sequence begin with (1, 2, 3, ..., N). And you are right that there is no finite limit to how large N can be. They can make N arbitrarily large. But perhaps surprisingly, that doesn't mean they can go on like that infinitely. They still must choose a number N, and there are no infinite numbers. In terms of sequences, infinity means forever. And forever means the sequence can't change at some point to match another sequence. There is only one sequence which goes x1=1, x2=2, x3=3, and so on for infinitely many terms.

 

As for the mathematicians, the unfortunate part is that no matter how large they make N, the probability is still 0 that their sequence matches its representative sequence at the N-th place. No matter how large they make N, it will still be infinitely small compared to the concept of infinity.


  • 0

#19 DeGe

DeGe

    Advanced Member

  • Members
  • PipPipPip
  • 128 posts
  • Gender:Male
  • Location:Paris

Posted 01 August 2013 - 09:33 AM

Aha, now I know why couldn't figure it out!

I was reducing the problem to 2 mathematicians, 2 rooms and say 5 or 10 boxes; where as if I understand correctly the explanation from Bonanova, I should have considered all the mathematicians in the world, matching number of rooms, and a much larger number of boxes :o


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users