- 16 Nov '04 22:08

There are some constructive proofs of the first bit in the thead ''Counting Problem. There's an old discussion about Georg Cantor from around October 2002 in which someone posted a proof of the second bit. A thread from August 2003 called ''Another for royalchicken'' contains another proof of this.*Originally posted by PBE6***Prove that the number of natural numbers (1, 2, 3, etc...) and the number of rational numbers (1, -2, 4/5, 569/1978, etc...) is the same. Then prove that there are more real numbers than rational numbers.**

Unlike that weasel STANG, I'm more than happy to provide my answer if asked.

However, it's kind of silly to dismissively say ''this has been asked before'', so yeah, everyone give new proofs of both of those ! - 16 Nov '04 22:34Well crap. Thanks for the heads-up, royalchicken. For everyone else, these posts never happened.

(Just so nobody can call me a weasel with a clean conscience, my proof for the natural/rational number sets is very similar to the previous postings, that is finding a "clever" way to list both sets and demonstrating a 1-1 correspondence. My proof for the real/rational numbers is in the same vein.)

- 17 Nov '04 01:23

No, no. People, new proofs!*Originally posted by PBE6***Well crap. Thanks for the heads-up, royalchicken. For everyone else, these posts never happened.**

(Just so nobody can call me a weasel with a clean conscience, my proof for the natural/rational number sets is very similar to the previous postings, that is finding a "clever" way to list both sets and demonstrating a 1-1 correspondence. My proof for the real/rational numbers is in the same vein.)

Welcome to Posers and Puzzles ! - 17 Nov '04 17:00OK, I think I gots one:

Four hikers traipsing through the woods on a midnight hike happen upon a gorge spanned by a thin, tattered suspesnion bridge. Only two people can safely cross at a time, and due to several large holes in the bridge, each crossing person or pair must carry the only flashlight with them.

Now, each hiker was crippled to some extent in a previous horrible accident (for the sake of this poser), which affects their crossing speed. Speedy Joe can cross the bridge in 1 minute, Average Joe can cross the bridge in 2 minutes, Idiot Clyde can cross the bridge in 5 minutes and drool like nobody's business, and Stumpy McMeatface takes a whole 10 minutes to cross. He always got picked last for teams as a kid too, and stayed a virgin until that trip to the biggest little whore-house in Nevada when he was 32.

Each hiker is such a good friend, and owes at least one other person some money, that any pair crosses at the rate of the slower person.

The question is, what is the minimum amount of time it wil take for all 4 hikers to cross the bridge? Remember, each time anyone crosses (forwards or backwards), they must carry the flashlight. And no tricks. If you suddenly decide that you're a lawyer and try to change this into a semantics problem, I'll steal your first born child and raise it as a monkey.

Please submit your answers in triplicate with a note from your mom. - 17 Nov '04 18:39

Is this not already given in textbooks ? Have you got any altogether different proof ? If so , give it.*Originally posted by PBE6***Prove that the number of natural numbers (1, 2, 3, etc...) and the number of rational numbers (1, -2, 4/5, 569/1978, etc...) is the same. Then prove that there are more real numbers than rational numbers.**

Unlike that weasel STANG, I'm more than happy to provide my answer if asked. - 17 Nov '04 20:24Did you not read royalchicken's post? This question has been asked and answered, and I outline my solution in my reply. It probably has been published in a textbook, but who cares? What hasn't? Feel like solving the Navier-Stokes equations, Mr. Original?

But I did say I would provide my solution if asked, and as I am not a weasel, here it is (in 2 parts):

(A) natural numbers/rational numbers

List the non-negative rational numbers in a matrix as follows:

0/1 0/2 0/3 ...

1/1 2/1 3/1 ...

2/1 2/2 2/3 ...

3/1 3/2 3/3 ...

...

This matrix contains all quotients (p/q) of the natural numbers, and hence contains all the positive rational numbers (some more than once). Now we will order this matrix using the following algorithm:

1. Assign an index to each matrix entry in the form (a,b), where "a" is the row number and "b" is the column number.

2. Start with entry (1,1), which in the above matrix is 0/1 = 0.

3. For the next ordered rational number, make the previous number negative. Our first number, 0, is a special case where -0 = 0, so skip it (lest we double count).

4. To move to the next matrix entry, subtract 1 from both "a" and "b" so you move in a diagonal direction. If (b-1) = 0, move to (1,b), where "b" is the lowest column number not covered yet. In this case, 1-1=0, so we move to (1,2).

5. If the new entry is equal in magnitude to an entry already covered, remove that entry. 0/2 = 0 which was covered in step 2, so remove that entry (again, lest we double count).

6. Repeat steps 3 through 6, creating an ordred list of all the rational numbers where each number is listed only once. By ordering them this way, we create a list that extends inifitely in one direction from a matrix that extends infinitely in two directions.

7. Number the first entry ("0" in this list with a the natural number "1". Now number each successive ordered rational number with the next natural number, going in order of increasing magnitude. This pairing (mapping) of natural numbers and rational numbers is 1-1 and onto, meaning that each entry in both lists corresponds with 1 and only 1 entry in opposite list. Therefore, the "number" of elements, or more properly the cardinality of each list, is the same.

Therefore, the number of natural number and rational numbers is the same.

(B) real numbers/rational numbers:

We begin by creating two columns (1 and 2). In column 1, we list all the natural numbers in order of increasing magnitude. In column 2, we list the decimal expansions of the real numbers between 0 and 1 with no repeats (order does not matter). All decimals will be of infinite length, for example 0.5 will be written as 0.5000000... with an infinite number of 0's after the 5, and repeating decimals like 1/3 = 0.33333... will repeat infinitely.

It would appear that both lists have the same number of elements, and hence are of the same size, but this is not the case. It is possible to write a number in column 2 that has no corresponding number in column 1, and we do this as follows:

1. The new number (which lies between 0 and 1) has as the number in it's first decimal place the number in the first decimal place of the first number in column 2.

2. The number in it's second decimal place is equal to that in the second decimal place of the second number, the number in it's third decimal place is equal to that in the third decimal place of the third number, etc...

To make this slightly more concrete, let's use an example list:

1 2

1 0.7148302865...

2 0.3333333333...

3 0.5090909090...

4 0.8291287641...

... ...

Moving diagonally down and right from the first decimal place of the first number ("7", our new number would start 0.7391...

3. Now we change the new number in each decimal place as follows: add 1 to the number, unless the number is 9 in which case 9 becomes 0.

Our above number 0.7391... would become 0.8402...

This new number is a real number between 0 and 1 different from every other number in column 2 in at least one decimal place, therefore there is not a 1-1 and onto mapping from the natural numbers to the real numbers between 0 and 1. It is also clear that the list of real numbers between 0 and 1 has at least one more element. Therefore, there are more real numbers between 0 and 1 than rational numbers (which follows from the equal cardinality between natural and rational numbers established in (A) above), and therefore there are more real numbers in total than rational numbers.

- 19 Nov '04 15:06 / 2 editsAnd that is, of course, the correct solution. For those of you who don't like shorthand, here's the solution in columnumetagorical form:

Crosses Crosses Back

1+2

.............1

5+10

.............2

1+2

_______ ____________

2+10+2 2+1

14..........3

And 14+3 = 17.

Congratulations to iamatiger. He truly has the eye of the tiger. BTW, is that zebra-print dress one of your mom's sick jokes? She does look foxy in it, though. Rrrrowr.