Let's discuss Mathematics

[ParadigmShifter]

It's just mappings again.

The hotel has countably infinite rooms, all full.

A new guest arrives, move all guests from their current room (N) to the next room (N+1). The first room is now empty, put the new guest there. EDIT: So (countable)infinity+1 = (countable)infinity

Infinitely many new guests then arrive. Move each guest from their current room (N) to room (2N). All the even numbered rooms are now occupied, put the infinite number of new guests into the odd numbered rooms just vacated... EDIT: So (countable) infinity + (countable)infinity = 2 * (countable)infinity = (countable)infinity.

 

[IdiotsOpposite]

It's just mappings again.

The hotel has countably infinite rooms, all full.

A new guest arrives, move all guests from their current room (N) to the next room (N+1). The first room is now empty, put the new guest there. EDIT: So (countable)infinity+1 = (countable)infinity

Infinitely many new guests then arrive. Move each guest from their current room (N) to room (2N). All the even numbered rooms are now occupied, put the infinite number of new guests into the odd numbered rooms just vacated... EDIT: So (countable) infinity + (countable)infinity = 2 * (countable)infinity = (countable)infinity.

Ah, I get it. Thanks.

 

[ParadigmShifter]

It breaks if a countably infinite number of infinitely long buses arrive, each containing a countably infinite number of guests though (I think). I think you can accommodate them if the hotel has a countably infinite number of floors (each containing countably infinite numbers of rooms).

 

[Atticus]

So, apparently Petek's problem is mistyped, or you guys have a different definition in mind.

Let's say that S=S'U{x} and x\not\in S'. If S' is finite it has n elements, where n is a natural number. Then S has n+1 elements, and is thus finite.

Did you perhaps mean that they should be proven to be of equal cardinality?

If S is uncountable, choose a countable set {x_n} where x_1=x as above. Choose a mapping for which f(x_l)=f(x_{k+1}), and everything else keeps still, and that's your bijection.

Now when I think about it, Dutchfire might have posed the exact same question before, and I got it right then too! This is great, I was feeling so stupid for not getting the [0,1] & ]0,1[ thing...

 

[ParadigmShifter]

That's much easier, yeah

 

[Petek]

Atticus' solution is what I had in mind. The problem wasn't meant to be difficult or deep.

 

[ParadigmShifter]

I posted this classic question when someone asked for a harder maths question in OT.

'Pooh', said the Wizard, 'is where we are now. The railway starts here and runs in a straight line via 39 intermediate and equally spaced stations to the terminus at Oz.

'Unfortunately, the railwaymen are on strike, so you'll have to go by bus. The bus goes along the Yellow Brick Road, which runs in a straight line from here to the outlying village of Bah, where it turns through a right-angle and goes in a straight line back to first railway station after Pooh. From there it goes in a straight line to the next outlying village, where it again turns through a right-angle and proceeds in a similar zig-zag fashion all the way to Oz, alternately calling at railway stations and outlying villages. Each of the 80 straight stretches of road is a different whole number of miles long. Rail distances are also whole numbers of miles.

'The fare is on ozzle per mile, but you needn't be alarmed, as all distances are as short as they can possibly be.'

I was alarmed, and it turned out I had good reason to be. My money was running short, for the Wizardry of Oz had been suffering from hyper-inflation recently.

Unfortunately the Wizard had vanished before I could ask him the vital question, HOW LONG IS THE Yellow Brick ROAD?

(Christmas problem from the 1976 Yorkshire Post, reprinted from one of my maths textbooks: extremely hard 10* difficulty, perhaps a bit easier with a computer program)


Dutchfire could probably solve it with Excel though...

EDIT: And I can't seem to find the maths book anymore, it is on the internet but with the pages that give the answer removed I think

 

[Petek]

I'll post a sketch of my solution in a spoiler. Not enough energy right now to post it in full. Maybe tomorrow if ParadigmShifter says I'm on the right track.

Spoiler :

Stripping out the chaff, we are given that we have 40 Pythagorean triples. All the hypotenuses (the segments of the railroad track between stations) have the same integer length. The other sides all have different lengths. The formula for a set of primitive solutions of such triples is given by

a = m² - n²
b = 2mn
c = m² + n²,

for nonzero integers m, n. Thus, we have to find an integer c that can be written as the sum of two positive squares in 40 different ways.

Hauling out some number theory books, the smallest such integer I could find was

148,208,125.

Wolfram Alpha indeed lists 40 representations of that number as the sum of two squares. Each pair of integers on the Wolfram Alpha page corresponds to m and n in the above. I have to compute a and b and sum them to get the total length of the Yellow Brick road. If this is correct, it seems that Oz is slightly larger than the Earth.

 

[Souron]

So in other words, find a set of 40 Pythagorean Triples with the same hypotenuse?

 

[ParadigmShifter]

You are on the right track, but the road is the zigzag path, not the straight line path (all the station distances on the straight line path are the same length).

It is about finding the smallest number which is the sum of 2 squares in 40 different ways.

EDIT: And then adding up those 80 numbers

EDIT2: This may help too...

If a is a sum of 2 squares, and b is a sum of 2 squares, then so is ab

EDIT3: And if p is prime, then p is NOT a sum of 2 squares if and only if p == 3 (mod 4)

so 2= 1^2 + 1^2 is
5 = 1^2 + 2^2 is
13 = 3^2 + 2^2 is, etc.

hence 3, 7 are not sums of 2 squares since those are congruent to 3 (mod 4)

 

[Mise]

It also has to be a square number itself though doesn't it? As in, it can't be 13 because sqrt(13) isn't a whole number of miles. Am I stating the obvious or have I missed something????

 

[Truronian]

As far as I can see we need to...

...take the first 40 primitive Pythagorean triples, then multiply them up so that we have a common hypotenuse (which is going to be massive), add up all the massive sides and finally go bankrupt getting to Oz.

EDIT: Not that simple. The answer won't be optimal.

EDIT2: Or even work.

I like the easy BODMAS OT question a lot more.

EDIT3: http://oeis.org/A006339 Unfortunately only goes up to n = 24.

 

[Mise]

Well I guess you could just take the Mathematica formula and turn that into a pseudo-code algorithm.

 

[Truronian]

Well I guess you could just take the Mathematica formula and turn that into a pseudo-code algorithm.

That's the plan. I know nothing about Mathematica though, so it's going to be trial and error.

EDIT: Done. I make the hypotenuse in question 32045, which would put the length of the railway at 1281800 miles. This assumes there isn't an n>40 that outputs lower than 32045, which there doesn't look to be (done up to a 100) and could be brute force proven.

Next step: road length. I think we're going to need a lot of ozzles.

I can sure that it's bounded below by 1281800 and above by Graham's number.

EDIT:

{716, 32037, 32045}, {1363, 32016, 32045}, {2277, 31964, 32045}, {2400, 31955, 32045}, {3045, 31900, 32045}, {3757, 31824, 32045}, {3955, 31800, 32045}, {4901, 31668, 32045}, {5304, 31603, 32045}, {6764, 31323, 32045}, {7259, 31212, 32045}, {7656, 31117, 32045}, {7888, 31059, 32045}, {8283, 30956, 32045}, {8580, 30875, 32045}, {8772, 30821, 32045}, {10075, 30420, 32045}, {10192, 30381, 32045}, {11475, 29920, 32045}, {11661, 29848, 32045}, {12325, 29580, 32045}, {12920, 29325, 32045}, {13572, 29029, 32045}, {15080, 28275, 32045}, {15708, 27931, 32045}, {15916, 27813, 32045}, {16269, 27608, 32045}, {16704, 27347, 32045}, {17051, 27132, 32045}, {17253, 27004, 32045}, {18291, 26312, 32045}, {19227, 25636, 32045}, {19552, 25389, 32045}, {19795, 25200, 32045}, {20300, 24795, 32045}, {21000, 24205, 32045}, {21093, 24124, 32045}, {21576, 23693, 32045}, {22100, 23205, 32045}, {23067,22244,32045}

Just need to sum the legs.

Answer, after much experimentation in Mathematica: 1635668 miles. Correct?

 

[ParadigmShifter]

Spot on!

The hypotenuse is 32045, which is 5x13x17x29 which are all sums of two squares themselves.

Aren't you going to factorise 32045 in 40 different ways too?

EDIT: You can do the factorisation in 40 different ways since a prime which is a sum of two squares is not prime as a Gaussian Integer.

 

[Spoonwood]

The word "bigger" is ambiguous. You can use it to say that at least in the sense of measure or number of elements (which is a measure too, btw), or if you have order. Thus even though set [0,1]U{2} isn't bigger in the sense of (Lebesgue) measure than [0,1], you can say it's bigger because inclusion of sets is a partial order. At least so I think.

1-to-1 correspondence between [0,1] and [0,2] is pretty easy,
f:[0,1] -> [0,2]: f(x)=2x
will do

In general, there is no one to one correspondence between uncountable sets, since they aren't necessarily of the same cardinality. There is no bijection from R to it's power set, although both of them are uncountable.

Don't you just have an injection from [0, 1] to [0, 2] with such a function? Don't you need a function from [0, 2] to [0, 1] also for a bijection here? The function here doesn't suggest an inverse function either.

 

[nc-1701]

Don't you just have an injection from [0, 1] to [0, 2] with such a function? Don't you need a function from [0, 2] to [0, 1] also for a bijection here? The function here doesn't suggest an inverse function either.

f^-1(x) = x/2 is the inverse and it is definitely onto as well as 1-1 making it a bijection.

 

[Spoonwood]

f^-1(x) = x/2 is the inverse and it is definitely onto as well as 1-1 making it a bijection.

Oh, you're right. Somehow I thought it would go 2/x. Don't know how I made that mistake. Still, you need that inverse for the bijection, which didn't get specified in the original comment.

 

[Spoonwood]

Let Cab the material conditional of "a" and "b", Aab logical disjunction the logical disjunction of "a" and "b", Kab denote the logical conjunction of "a" and "b", Eab the material equivalence of "a" and "b", Nb the logical negation of "b". The following wffs are neither true, nor false in propositional calculus.

1. CCpqq

2. CpKpq

3. KpAqr

4. Cpq

5. ECKpqqKqr

Let "!" denote the existential quantifier, and "@" the universal quantifier.

Problem 1: Pick any of the wffs 1.-5. and quantify it so as to make it true.

Problem 2: Pick any of the wffs 1.-5. and quantify it so as to make it false.

For instance, with Cpq, I might write !q @p Cpq, which makes it true, since if q is true, Cpq is true also.

Extra challenge: Find an analogous valid formula (or invalid formula) in propositional calculus to your quantified formula. For instance, !q @p Cpq can get said to correspond to CqCpq.

 

[ParadigmShifter]

I found my rings & factorisation book, so I can post the partial solution to the Yellow Brick road problem!

I'll do it in stages though:

I recall that the Yorkshire Post reported that only one correct solution was received from readers. (Was it from the person who set the problem?!). I have to admit I do not have a complete solution.

Denote the distance between successive stations on the railway by d, in miles, and consider a right-angled triangle of roads and rail as shown (d^2 = a^2 + b^2, omitted cos the diagram is obvious).

If d is even, then because d^2 = a^2 + b^2, it is easy to see that a, b must also be even. Thus all distances can be divided by 2, which contradicts the fact that they are as short as possible. Thus d is odd. Suppose that d has a prime factor p==3 (mod 4). Now p|(a^2+b^2) and p is irreducible in Z, so either p|(a+ib) or p|(a-ib) in Z. Thus p|a and p|b in Z, and again distances are not as short as possible. Thus every prime factor of of d is congruent to 1 (mod 4). The problem now amounts to finding the smallest positive integer d whose square can be expressed as the sum of two squares in 40 different ways.