How Good Are You At Reasoning?

Here's some questions, some of which are quite cool, which you have to be quite mathematically minded to answer. I wanted to see how good people are at thinking rationally but creatively on DV. I threw in a couple of standard psychological experiments too. Just do the ones you can. Feel free to add more.


1. You have a row of 1,000 coins, all of which are heads up. You flip the second, fourth, sixth, and all other even coins over so that they're tails. Then you flip over the third, sixth, and all other coins which are multiples of three. Now you do this for every fourth coin, every fifth coin, etcetera, all the way up to every thousandth coin (which means just flipping the last one).

The question is this: which coins are heads up, and why? There is a concise and surprising answer.


2. What's the maximum number of pieces you can cut a pizza into using a cheese wire (i.e. straight cuts) if you can only cut six times? The pizza is to thin to cut horizontally, and too hot to pick up and move around.


3. There's a 1% chance that the average person has cancer. Somebody with cancer has an 80% chance of testing positive when they go for a scan. Somebody without cancer has a 9.6% chance of testing positive (i.e. getting a false positive). You go for a scan and receive a positive result. What is the probability that you have cancer?


4. 100 people out of a group of 10,000 are tree-huggers. You ask all 10,000 people if they hug trees or not. 80 out of the 100 people who hug trees are honest about it and say yes. 950 out of 9,900 people who don't hug trees also pretend that they do. What fraction of people who claim to hug trees are genuine tree-huggers?


5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you. They are

1, 2, red, blue.

Which cards do you need to turn over to check my claim?


6. In the UK you can drink at 18. There are four people drinking at the bar. One is 21, one is 16, one is drinking coke, one is drinking beer. What do I have to check to make sure nobody is breaking the law?


7. In any group of (two or more) people, there are always at least two people with the same number of friends in that group. True or false?

N.B. you can only be friends with somebody who is friends with you!

"How good are you at reasoning"?

I think I'm OK, how about you? :)

Okay I hope. But only 15% of professional doctors get the one about cancer correct, so we're in the minority, aren't we? Assuming of course that you can answer it, which you showed no evidence of. :)

These are tricky. I'm guessing 1 instinctively for the first question and 14 slices for the second. For the 3rd, I'm a little puzzled. 72.32?

1, 5, and 6 are the ones that caught my eye.

1) If we let D(n) denote the number of divisors of n that are not 1, then the coins at positions n such that D(n) is even will be in their initial state.

[edit]
Better:

The coins in positions with odd numbers of divisors will be heads up.

[/edit]

5) To test the claim, one would turn over the card showing two and the blue card.
When turning over the blue card, confirm that there's an odd number on it. (or there would be a blue and even card)
When turning over the card showing two, confirm that it's red.

6) That nobody under 18 is drinking. :cheeky:

1, 2 and 7 are probably the most interesting to think about as puzzles. The first two have especially pretty answers. The middle four are more about human intuition and psychology.

You are right about the odd number of divisors thing, but there is a more concise way of saying it. :)

Ok ok, squares will be in their original state. For 7, is friendship reflexive?

No, but it is symmetric.

And of course, the point of the coins question is to provide a reason. Anybody can assert an answer after checking a few cases.

1. oxxoxxxxoxxxxxxoxxxxxxxx etc etc
2. 64 assuming I can reorientate the pizza between slices.
3. I'm a little confused on this one. I'm thinkin 1%. I'll ponder it a little longer though.
4. 80/1030
5. You didn't limit my card flips. I will flip them all.
6. The IDs of those drinking alcohol.....
7. False. You never claimed friendship had to be mutual.

EDIT: looks like you changed the rules on the last question so my answer no longer applies. Don't have time to rethink it at the moment.

Okay, I'll bite: I'll probably fall into all the traps..

1) I'm not atall mathematical, but I notice that the first and second coins remain untouched.. and seeing as you said that the answer was concise and surprising, I'm gonna guess 2; [BTW.. a "stack" of 1000 coins? How does one flip without dismantling the stack?]

2) Using 2D for a few minutes, I managed 19; but some sort of nagging voice is saying something about dual parallel perspective in 3D;

3) 4 in 5;

4) 80/1030ths = 40/515ths;

5) a) All of them: any card could have been tampered with;

b) None of them: make sure that the cards are placed on a glass table and look from underneath;

6) First you need to check if the bar needs a license: it could be a bar built in one's living room, i.e. private- the UK 18-year-old thing only applies in certain premises;

7) False: could be any group of people who don't like each other.

Quote:

---

Originally Posted by Oneiro

7) False: could be any group of people who don't like each other.

---

If they don't like each other. They all have 0 friends in the group so it would be true.

Oooh! Clever.. I said I'd fall into all the traps..

(Is zero a number?)

Quote:

---

Originally Posted by LikesToTrip

1. oxxoxxxxoxxxxxxoxxxxxxxx etc etc
2. 64 assuming I can reorientate the pizza between slices.
3. I'm a little confused on this one. I'm thinkin 1%. I'll ponder it a little longer though.
4. 80/1030
5. You didn't limit my card flips. I will flip them all.
6. The IDs of those drinking alcohol.....
7. False. You never claimed friendship had to be mutual.

EDIT: looks like you changed the rules on the last question so my answer no longer applies. Don't have time to rethink it at the moment.

---

1. What do you mean by etcetera?
2. How come?
4. Yep.
5. But I did ask which ones you need to flip, and you don't need to flip them all.
6. Why would you need their IDs? The question tells you their ages.
7. Are you sure it'd be false? But okay, I clarified it. :P

Quote:

---

Originally Posted by Oneiro

Okay, I'll bite: I'll probably fall into all the traps..

1) I'm not atall mathematical, but I notice that the first and second coins remain untouched.. and seeing as you said that the answer was concise and surprising, I'm gonna guess 2; [BTW.. a "stack" of 1000 coins? How does one flip without dismantling the stack?]

2) Using 2D for a few minutes, I managed 19; but some sort of nagging voice is saying something about dual parallel perspective in 3D;

3) 4 in 5;

4) 80/1030ths = 40/515ths;

5) a) All of them: any card could have been tampered with;

b) None of them: make sure that the cards are placed on a glass table and look from underneath;

6) First you need to check if the bar needs a license: it could be a bar built in one's living room, i.e. private- the UK 18-year-old thing only applies in certain premises;

7) False: could be any group of people who don't like each other.

---

1. I changed the question to a row of coins if that makes it clearer for you.
2. That is close to my answer. Don't worry about 3D, the pizza is 2D.
3. Way off.
4. Yep.
5. No tampering, no glass tables. None of these are trick questions. :P
6. See above.
7. What LikesToTrip said.

3) Oh yeah! I just read the question properly..:roll: 1%;

It's definitely not 1% either. :P

I was referring to my brain power.. :lol:

2) I've managed 20 in 2D;

A photon checks into a hotel and the concierge says: "Any luggage, Sir?" The photon replies: "No.. I'm travelling light.."

1. All primes will be tails. Since all non primes (save 1 which is not flipped) must have an even number of factors they will be flipped an even number of times and thus be heads.
2. I managed 21 playing around trying to get the maximum number of intersections with each cut.
3. 7.76% chance of actually having cancer with a positive result (or 800/10304 more precisely). For bonus points you have a 0.22% (or 200/89696 more accurately) chance of having cancer when you get a negative result.
4. 80/1030 obviously.

Will look at the rest later.

Quote:

---

Originally Posted by Xei

1. What do you mean by etcetera?
2. How come?
4. Yep.
5. But I did ask which ones you need to flip, and you don't need to flip them all.
6. Why would you need their IDs? The question tells you their ages.
7. Are you sure it'd be false? But okay, I clarified it. :P

---

1. There will always be 2 more tails in between each heads all the way up to 1000. Why it does this, I have no clue. I'm sure there is some mathematical or logical equation you could write that sums it up, but that is beyond me.
2. Cut in in half and stack, cut in and half stack, cut in half and stack. You end up with 64 pieces. 2^6=64
5. Herp a derp. I'm retarded. Flip the 2.
6. You said four people. 21, 16, beer, coke. Aren't those the 4 people? We don't know the drinks of the 21/16 and we don't know the ages of the beer/coke. So we need to check the drink of the 16 and the age of the coke. Did I misinterpret the question?
7. I think the answer is now true. I'm not completely sure though. I'll ponder it more.

Quote:

---

Originally Posted by Photolysis

1. All primes will be tails. Since all non primes (save 1 which is not flipped) must have an even number of factors they will be flipped an even number of times and thus be heads.
2. I managed 21 playing around trying to get the maximum number of intersections with each cut.
3. 7.76% chance of actually having cancer with a positive result (or 800/10304 more precisely)
4. 80/1030 obviously.

Will look at the rest later.

---

1. Along the right lines, but doesn't check out with the actual numbers (2 is non-prime but tails for example).
2. Pretty close. If you formalise your technique you should get it right. What about n cuts?
3. Yep; via what general method did you do this? Why was 4 a more obvious question?

Quote:

---

Originally Posted by LikesToTrip

1. There will always be 2 more tails in between each heads all the way up to 1000. Why it does this, I have no clue. I'm sure there is some mathematical or logical equation you could write that sums it up, but that is beyond me.
2. Cut in in half stack, cut in half stack, cut in half stack. You end up with 64 pieces.
5. Herp a derp. I'm retarded. Flip the 2.
6. You said four people. 21, 16, beer, coke. Aren't those the 4 people? We don't know the drinks of the 21/16 and we don't know the ages of the beer/coke. So we need to check the drink of the 16 and the age of the coke. Did I misinterpret the question?
7. I think the answer is now true. I'm not completely sure though. I'll ponder it more.

---

1. Try numbering the coins for a more concise description of which ones are flipped. :P

The point of this question is in giving a good reason. I recommend you mull it over. None of these questions require mathematical knowledge or skill. They just require you to think like a mathematician, which is the important bit. :)
2. God damn you lateral thinkers. Okay no, no moving the pizza around. :P
5. Nope. You fell into the psychological trap that the vast majority of people do.
6. Yes that's completely right, and yes it is an easy question. The funny thing is this is logically identical to question 5.

You need to turn over 2 and blue. The claim is that all evens are red, however it's not specified that all reds are even. It doesn't matter if there is an uneven number on the other side of red. 2 is even and must be checked. Blue must be checked to ensure there is not an even number on it. 1 doesn't need to be checked since it isn't stated that odd numbered cards cannot be red.

I need to work on my math :(

Original answer

Quote:

---

Quote:

---

Originally Posted by Xei

Okay I hope. But only 15% of professional doctors get the one about cancer correct, so we're in the minority, aren't we? Assuming of course that you can answer it, which you showed no evidence of. :)

---

OK. 3) If I have cancer, then I have an 80% chance of being tested positive. If I'm tested positive, then the chance of me being positive is now 100%. The results, however, have only a 9.6% chance of being false, meaning I have only a 9.6% chance of not having cancer. Therefore, if I'm tested positive, then I have a 90.4% chance of having cancer.

---

Quote:

---

1. Along the right lines, but doesn't check out with the actual numbers (2 is non-prime but tails for example).

---

I was including 2 as a prime. Since when was it NOT a prime number, or am I misunderstanding you?

Quote:

---

3. Yep; via what general method did you do this? Why was 4 a more obvious question?

---

Easier numbers to work with. #3 also requires working out how many in total will get a positive result, but you already give the equivalent in #4.

Quote:

---

2. Pretty close. If you formalise your technique you should get it right. What about n cuts?

---

I'll have to think about a formal technique and on my answer.

5) Don't flip any.. I trust you, Xei;

Quote:

---

Originally Posted by Photolysis

2 is non-prime

---

Hahaha what a fantastic retard I am.

Okay, consider 6. Flipped at 2, 3, 6. Even number of factors means getting flipped to tails because 1 isn't included, that was my point. :P

Hey, Xei, could look at my answer and tell me where I went wrong?

Quote:

---

Originally Posted by Xei

Hahaha what a fantastic retard I am.

Okay, consider 6. Flipped at 2, 3, 6. Even number of factors means getting flipped to tails because 1 isn't included, that was my point. :P

---

Ah yes. Revision: all prime numbers and numbers that are the product of primes will be tails. Primes are flipped once. Products of n prime numbers have have 2n factors, but as they are not flipped at 1 they are flipped an odd number of times (2n-1) and thus tails.

Quote:

---

Originally Posted by Somii

Hey, Xei, could look at my answer and tell me where I went wrong?

---

A 9.6% chance of the results being false means 9.6% of the people with positive results have no cancer. But this is different from 9.6% of people with no cancer having positive results.

I recommend you draw a rectangle representing a population of 10,000 typical people, then subdivide it into people with cancer with positive tests, people without cancer with positive tests, etcetera.

Quote:

---

Originally Posted by Photolysis

Ah yes. Revision: all prime numbers and numbers that are the product of primes will be tails. Primes are flipped once. Products of n prime numbers have have 2n factors, but as they are not flipped at 1 they are flipped an odd number of times (2n-1) and thus tails.

---

Your approach is the closest yet, though your answer is not. All numbers are the product of primes, so as far as I can tell your current argument has all coins tails up.

I would have said that that for cut n, the maximum number of pieces that can be intersected with a straight cut is also n, thus making the maximum number of pieces the nth triangle number. Or the sum of the geometric series 1+2+...n, k=1.

Question: does the pizza have to retain its shape whilst being cut? If not, then it's 2^n pieces.

Quote:

---

Your approach is the closest yet, though your answer is not. All numbers are the product of primes, so as far as I can tell your current argument has all coins tails up.

---

Yeup, true. To revise it some more.

All square numbers are heads, every other number is tails. All square numbers have an odd number of factors and are thus flipped an even number of times. If that's not right then I shouldn't do this stuff so late :P

Quote:

---

Originally Posted by Xei

No, but it is symmetric.

---

Right. Stupid me. Thanks for seeing through my problem with word selection.

Quote:

---

And of course, the point of the coins question is to provide a reason. Anybody can assert an answer after checking a few cases.

---

The reason is inherent in the answer...?

A coin n will be flipped one time for each divisor of n that's greater than 1?

That's fairly obvious once you look at a few cases if not before?

I'll think about the friends problem but might get bored.

1. all of the squares (I did it with 10 coins)
2. 24 (?)
3. 85.2% (?)
4. 8/103
5. 2 & red
6. the age of the beer drinker and the drink of the 16 yearold.
7. true (?)

(?) = guess

edit: #5 fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuck. (I knew better... I've read this problem in books before, lol)

Quote:

---

Originally Posted by PhilosopherStoned

Right. Stupid me. Thanks for seeing through my problem with word selection.

---

I wasn't trying to be sarcastic if that's what you mean... friendship could plausibly be reflexive.

Quote:

---

The reason is inherent in the answer...?

A coin n will be flipped one time for each divisor of n that's greater than 1?

That's fairly obvious once you look at a few cases if not before?

---

Of course, if your answer is 'coins with an odd number of divisors', then it follows immediately. But that's not far off from trivially answering 'coins which are flipped to heads by the given process'. The meat of the question is in explaining why odd number of divisors is equivalent to the more concise condition you stated of being a square.

Quote:

---

I'll think about the friends problem but might get bored.

---

It's quite a quick and linear question (it took me thirty seconds or so, but I'm used to these kinds of things).

Quote:

---

Originally Posted by IndieAnthias

1. all of the squares (I did it with 10 coins)
2. 24 (?)
3. 85.2% (?)
4. 8/103
5. 2 & red
6. the age of the beer drinker and the drink of the 16 yearold.
7. true (?)

(?) = guess

---

1. Yep, why though? (Nobody's nailed this one yet).
2. Close, try to think of how you'd answer it if it were 100 cuts.
3. Nope, but try calculating the probabilities for various things in question 4. :P
4. Ya.
7. Maybe. :P

7. True.

Here's my answer to why.

Let n be group size
Let x be the number of friends a person has
Let z be the number of people in the group with 0 friends
Let d be the number of discreet values x may take

For this to be false, group size n must have a d value of n.

A person can only have a maximum of n-1 friends, x cannot be negative, and a person with 0 friends cannot increase the value of x for someone else therefore:
0<= x <= (n-(1+z))

If z=0, d=n-1, therefore for the statement to be false, z must =1.

Since the number of people with zero friends must be positive
0<= z <= n

However, a person with no friends cannot increment the friend count of someone else so for z=1, d = n-z

for z=0 and z=1 d>n, therefore statement is true.

Quote:

---

5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you. They are

1, 2, red, blue.

Which cards do you need to turn over to check my claim?

---

The 2 card and the blue card.

Quote:

---

Originally Posted by Xei

A 9.6% chance of the results being false means 9.6% of the people with positive results have no cancer. But this is different from 9.6% of people with no cancer having positive results.

I recommend you draw a rectangle representing a population of 10,000 typical people, then subdivide it into people with cancer with positive tests, people without cancer with positive tests, etcetera.

---

Since a person without cancer can only have a 9.6% chance of testing positive, no person without cancer can have a >9.6%> chance of testing positive. If a person is tested positive, which assumes a person is 100% positive, then it follows that with exclusion to this assumption, I may have a < 90.4% chance of having cancer. (This was actually the answer before the "original" one I tried to force. Albeit a bit broad, it's still possible. Who needs such silly complex math when you can make fenced guesses!) I win :party:


I'm an engineer undergrad. How sad :(

Thanks Xei, this was fun.

I'm answering these in Notepad before reading any of the other answers. I'm using a pencil, paper and calculator, not looking anything up online or anywhere.


1. Any y such that y = x^2, where x is an integer and y is between 0 and 1000. So 1, 2, 4, 16, 25, 36, etc. These are the only ones that will be flipped an even number of times. But I don't know why. I arrived at the conclusion through induction and recognized the pattern.


2. 22. I made a table:

Spoiler for Table:

cut through = number of previous edges cut through on the current cut
new slices = number of new slices made resulting from the current cut

http://i1198.photobucket.com/albums/...Problem001.jpg

The total resulting slices gives 22. That's assuming it's always possible to cut through every previous edge. I drew it out to make sure of this. And all of this is hypothetical, In real life, some of the slices would be so ridiculously small.

Spoiler for Circle:

http://i1198.photobucket.com/albums/...zzaProblem.jpg

3. This is unfair because I've taken STAT courses and know how to do this. I doubt

I'd be able to figure it out if I hadn't.

Spoiler for Cancer diagram:

http://i1198.photobucket.com/albums/...Problem001.jpg

4. T = tree-huggers
S = pretend to be tree-huggers

genuine tree huggers = T/(T+S) = 80/(80+950) = 80/1030 = 8/103


5. 2 and red. That was too easy. Is there some trick I'm missing?


6. If I take your question literally, you didn't specifically say what the minimum drinking age is. If you can drink at 18, maybe the minimum age is still 14 or something so neither would be breaking the law. So I guess you'd have to check the minimum drinking age, and then make sure the one drinking beer is at least that age. (Assuming the one drinking coke isn't drinking rum and coke or something). Also, I suppose you'd have to check everything about both of their lives, since they could be breaking the law in some way other than drinking alcohol. There are other possible word-play problems too, like maybe you just mean drinking anything, not just alcohol.


7. Do the friends have to be within that group? If they don't, then false. Otherwise, true. If none of them are friends, they they all have 0 friends. If there's at least 1 pair of friends, yes. I'm not sure why, I just don't see any possible arrangement which might make it false. It might be fun to try to prove it but I don't have much time to think about it lol.

Impressive stuff Dianeva. The pizza thing is right, the key insight of course that a straight line can only intersect another straight line once. If you fiddle about for a while you can find a nice way of doing it:

Spoiler for :

http://img41.imageshack.us/img41/849/pizzab.png

And 3 and 4 are right too of course.

The funny thing about 5 is that it is technically easy, yes, but your answer isn't correct. :P

The vast majority of people get this wrong.

Just take 6 at face value.

I won't comment on 1 or 7 because along with the pizza one they are the best. You've done the first half of what a mathematician does, which is 'experiment with the question and try to find a pattern'. The second part, and really the part that requires almost all the thinking, is in finding an iron cast reason for your suspected answer.

The main focus of my degree is to 'learn how to think well'. It's quite a subtle process by which they teach you so it's interesting to me to see how well others fare at pure, hard thought. I suggest mulling them over when you have time because they're quite satisfying... the friends one is probably the one to do first. The only thing I'll say is not to get lost in drawing complex diagrams, the answer can be distilled into a few lines of plain English and can be arrived at in a pretty linear, general fashion (I didn't need to draw anything).

I think I'm okay at reasoning, but you like to point out how horrible I am at it. Actually you like to point out how horrible everyone is at it.

Well, I tried reading the questions, but I shut down when I figured out they were math problems.

Okay my final answers for all except #6 which I still haven't looked at, along with the explanations.

1. All square numbers are heads, rest are tails.

For a natural number n, where n>1, all non-square numbers have an even number of factors. Square numbers have an odd number of factors because at least one factor is multiplied by itself.

A number has f factors, and because they are not flipped at 1, they are flipped (f-1) times.

Where f-1 is odd, the coin lands on tails. Where f-1 is even, the coin lands on heads. Therefore only square numbers are heads.

(Much easier if you look at the problem instead of trying to be clever as I did and jumping straight in. Though it was late. Yes that's my excuse!)

2. A straight line can only be intersected once, so cut n can only intersect n pieces.

The number of pieces you can obtain is the nth triangle number+1 (since you start with one piece already) , aka the result of the geometric series (1+2...+n, k=1) +1

for n=6, the number of pieces is 1+1+2+3+4+5+6 = 22

(Note I must have miscounted with my diagram... should have caught this one earlier.)
(Note 2: Also do not go to parties with mathematicians!)

3. You have to look at the number of people getting a positive result in total (including false positives)

0.01*0.8% get true positive results
0.01*0.2 get false negatives
0.99*0.096 get false positives
0.99*0.904 get true negatives

The chance of actually having cancer is therefore 0.01*0.8 / ( [0.01*0.8] + [0.99*0.096]. Works out at 800/10304 or ~7.76%

200/89696 or ~0.22% get a false negative.

Because the number of false positives is much higher than those who have cancer and get a genuine positive result, there is a very good chance that even a positive result means you don't have cancer, which is why doing multiple tests is so important in the real world.

4. It's similar maths here except the numbers are worked out.

80 people claim to hug trees who actually do
950 claim to who don't

80/(950+80) = 80/1030

5. You flip the 2 and blue cards.

You do not say that all red cards have an even number on the other side, only even numbers must have red. Therefore you don't need to flip 1 because the colour doesn't matter, and you don't flip the red card because the number doesn't matter (it could be odd).

If the two is not red, or if the blue has an even number on the other side this would disprove your claim.

7. For group size n, where n>=2, the maximum number of friends a person can have (x) is n-1 because a person cannot be friends with themselves. Let f be the number of friends a person has and z the number of people in the group with zero friends.

For the statement to be proven false, a group size n must have n different values for f. Since the maximum value for f is n-1 the only way this would be possible is if someone had zero friends.

However a person with zero friends cannot increment the friend count of someone else because friendships are two way, and so every person with zero friends further reduces x by 1.

Therefore the number of values f may take is always less than n, therefore the statement cannot be proven false therefore it is true.

Quote:

---

Originally Posted by DeeryTheDeer

I think I'm okay at reasoning, but you like to point out how horrible I am at it. Actually you like to point out how horrible everyone is at it.

---

No, I just disagree with you frequently because you are often wrong. What a whiny thing to say.

Quote:

---

Well, I tried reading the questions, but I shut down when I figured out they were math problems.

---

Only three of seven. Cool excuse though.

I'm often wrong on what? Opinions?

Anyway, I'll take an actual stab at some of the questions, don't know if I'll get any of them right though.

3. 70.4%

4. 80 out of 1050

5. 2 and red (my first guess was all of them)

6. The one drinking beer

7. True....

I just realized that (5) is 2 and blue. What the hell was I thinking. I didn't even make a mistake before with the wording. I translated it in my mind to [even number] --> [red other side] and realized it didn't have to be the other way around, but still made that mistake somehow. The 2 has to be flipped to make sure it's red on the other side, and the blue has to be flipped to make sure its other side is an odd number. No need to comment on that unless for some reason it's wrong.

EDIT: I was trying to work out the last one and have so far failed, but I'll keep trying. I was thinking of using mathematical induction. Showing that in any random configuration in which at least two are shared, any added line must also produce a graph in which at least two are shared. (I've been thinking of it on paper like a graph consisting of dots and edges in between them to represent friendship). I have no idea if I'm on the right track or not. I like these problems that sound so simple but answering them is so difficult, but then in the end the answer is simple again.

Quote:

---

Well, I tried reading the questions, but I shut down when I figured out they were math problems.

---

Math can solve a lot of puzzles. But yeah, It doesn't make sense to judge anyone's intelligence on their abilities to answer the math ones. They require specific knowledge learned in University-level courses (or in one's free time if they're into that) to answer. The pizza one I came up with on my own, but for the many of the others, there's no way I'd be able to answer them if I hadn't taken a couple STAT courses, math courses and a discrete logic & data structures course. And I still can't seem to get the reasons for 1 and 7.

Quote:

---

Originally Posted by Xei

Spoiler for :

http://img41.imageshack.us/img41/849/pizzab.png

---

Ah, I should have just tried to do this, this is how I imagined doing it.

I skipped the statistics since I haven't learned how to do this yet but I'm really anticipating the answer to number 1.

For number 5 you just flip the 2, since you didn't say that an odd number can't be red. To completely check the claim I guess you would have to flip both colored cards too.

For 6 I suspect an underlying trick, but my best guess is you would have to check what the 16 year old is drinking and if the person drinking beer is 18+.

Number 7 kinda boggled my mind lol At first I was almost sure the answer didn't have to be true, but after reasoning it out with a few examples I couldn't make it to be false.

Ok, I realize for 5 flipping the red card may additionally confirm the claim but isn't necessary.

Quote:

---

Originally Posted by Xei

Of course, if your answer is 'coins with an odd number of divisors', then it follows immediately. But that's not far off from trivially answering 'coins which are flipped to heads by the given process'. The meat of the question is in explaining why odd number of divisors is equivalent to the more concise condition you stated of being a square.

---

I thought the meat was in figuring out the odd factor thing. The squares thing is (imo)just a cute way to use a well known fact from number theory to cover it up and make it look cool. I hate it when people do that.

At any rate, an integer has an odd number of factors if and only if it's a square.

proof:
(if)
Suppose it's a square, N=n². We need to show that |S| is odd where S is the set of factors and |S| is the number of elements in S. Then for every divisor, d, N/d is also a factor. Hence we get a map f from S to itself given by f(d) = N/d. Note that f(f(d)) = f(N/d) = N/(N/d) = d. Hence we can partition S into distinct sets, S_d = {d, f(d)}. if d =/= n then d =/= f(d) and so each set formed from such d has two distinct factors. But n lays in S and so S_n = {n}. Hence S is partitioned into some numer k of sets with 2 elements and 1 set of 1 elements, and we can count it as |S| = 2k + 1. This is trivially an odd number as it is one greater than the even number 2k.

(only if)
Now suppose it has an odd number of factors. We need to show that it must be square. (This is the part that everybody seems to have forgotten so far.) Using the same labels as above, partition S into sets S_d = {d, f(d)} using the same f. Again, f(f(d))=d and so there is a maximum of two elements in a given partition. Let k be the count of partitions with 2 elements and p be the count of partions with 1 element. Then we have |S| = 2k + p. For |S| to be odd, p must be odd and hence not zero. Hence there is at least one d with |S_d| = 1, and f(d) = N/d = d and so N = d².


Now that's quite excessively nailed :)

Quote:

---

It's quite a quick and linear question (it took me thirty seconds or so, but I'm used to these kinds of things).

---

Yeah, you're right. Took me longer than thirty seconds and Photo made it to the comp first but I'll post my argument anyways as it's cleaner and actually correct rather than just being very close. ("it cannot be proven false, therefore it's correct"? :P Flirting with Goedel there...)

For a group of N people, there will be two with the same number of friends.

Proof:
For a person P, let f(P) be the number of friends.

First suppose that there are n people with zero friends. If there are two people with F(P_i) = F(P_j) among the N-n people with friends, then F(P_i) = F(P_j) among all N people as somebody with zero friends won't change the value of F. Hence we can assume that n=0, that is everyobdy as at least one friend.

Hence we have 1 <= F(P) < N for all P.(we're not counting friendship with oneself).

But then there are N values of F(P) to be chosen from among N-1 values. Hence by the pigeon hole principle, at least one value will occur at least twice.

Quote:

---

Originally Posted by Xei

Here's some questions, some of which are quite cool, which you have to be quite mathematically minded to answer. I wanted to see how good people are at thinking rationally but creatively on DV. I threw in a couple of standard psychological experiments too. Just do the ones you can. Feel free to add more.


1. You have a row of 1,000 coins, all of which are heads up. You flip the second, fourth, sixth, and all other even coins over so that they're tails. Then you flip over the third, sixth, and all other coins which are multiples of three. Now you do this for every fourth coin, every fifth coin, etcetera, all the way up to every thousandth coin (which means just flipping the last one).

The question is this: which coins are heads up, and why? There is a concise and surprising answer.

---

I'm gonna say only the first one is still heads up, coz it never gets flipped and the rest flip on to tails.

Quote:

---

Originally Posted by Xei

2. What's the maximum number of pieces you can cut a pizza into using a cheese wire (i.e. straight cuts) if you can only cut six times? The pizza is to thin to cut horizontally, and too hot to pick up and move around.

---

I didn't do this mathematically per se, I just drew it out, cutting through the maximum number of lines with each new line, I got 22.

Quote:

---

Originally Posted by Xei

3. There's a 1% chance that the average person has cancer. Somebody with cancer has an 80% chance of testing positive when they go for a scan. Somebody without cancer has a 9.6% chance of testing positive (i.e. getting a false positive). You go for a scan and receive a positive result. What is the probability that you have cancer?

---

1%

Quote:

---

Originally Posted by Xei

4. 100 people out of a group of 10,000 are tree-huggers. You ask all 10,000 people if they hug trees or not. 80 out of the 100 people who hug trees are honest about it and say yes. 950 out of 9,900 people who don't hug trees also pretend that they do. What fraction of people who claim to hug trees are genuine tree-huggers?

---

80/950

Quote:

---

Originally Posted by Xei

5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you. They are

1, 2, red, blue.

Which cards do you need to turn over to check my claim?

---

The 2 card. EDIT: Just revising this, I thought I was smart by doing the smallest amount possible. You would also need to flip the red card to make sure it was even. And also the Blue card lol And also the 1 haha
Of course IRL it would depend on whether the 2 ended up having blue on the back or not, and so on. But yes, you need to check them all to make sure all reds are even and all evens are red.

Quote:

---

Originally Posted by Xei

6. In the UK you can drink at 18. There are four people drinking at the bar. One is 21, one is 16, one is drinking coke, one is drinking beer. What do I have to check to make sure nobody is breaking the law?

---

Check if the bar keeper checked for ID for the 16 year old and the one drinking beer. And check if there's alcohol in the coke :lol:

Quote:

---

Originally Posted by Xei

7. In any group of (two or more) people, there are always at least two people with the same number of friends in that group. True or false?

N.B. you can only be friends with somebody who is friends with you!

---

Not sure what N.B means, but....I'd say true. Since we only have to check with a group of 2 people, they could both either have 1 friend in that group, or none.

Thanks Xei, that was fun. Now I'm off to check the other responses to see how far off I was :lol:

Now I feel like I'm in school again, waiting for my marks on a test :lol:

Quote:

---

Originally Posted by Xei

No, I just disagree with you frequently because you are often wrong. What a whiny thing to say.

---

Don't be mean to Deery. His avatar his cool.

Quote:

---

5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you. They are

1, 2, red, blue.

Which cards do you need to turn over to check my claim?

---

Version #1) You just flip the number 2 card, for that is the only even number card in front of me that is respective to your claim. The "other" side, presumably, is strictly the side opposite of what's facing me.

Version #2) If each card has strictly numbers on one side, colors on the opposite side, and some numbers are colored in themselves, then it follows in respect to your claim that we need only to check red and blue.

Version #3) 2 and red. 1 and blue are irrelevant, since we know at least one side for each card excludes a condition to the claim.

Quote:

---

6. In the UK you can drink at 18. There are four people drinking at the bar. One is 21, one is 16, one is drinking coke, one is drinking beer. What do I have to check to make sure nobody is breaking the law?

---

No inconsistencies of the law :)


These are the only non-math ones, I think, that no-one else has answered correctly?

Apparently I suck... the only one I got without looking was the cards one...

It's late and I'm tired so I only attempted 2, think it's 22. The sequence formed is just adding one more each time as each time the wire can go through one more previous cut. So you get the sequence 1 2 4 7 11 16 22. Think that works out as, (n(n+1))/2 +1.

1.To be flipped at the end it must have an odd number of divisors not including 1, and since in non squares the divisors can all be paired off and must be even, all numbers that are not square or prime must end up being flipped an odd number of times and so tails up (squares cant be paired off as one number would be paired with itself and in this coin game you are only going through each number once.). All primes must be tails up as they are only flipped once. So all that is left is squares. That argument doesn't quite feel right, think I've done something stupid but I'm going to go with all squares heads up.

2. answered last night.

3. Well that's just the chance of having cancer and testing positive over the chance of having cancer and testing positive added to the chance of not having cancer and testing positive. Numerically that's
(0.01*0.8)/(0.01*0.8+0.99*0.096)

4. 8/103 not really sure that one needs any explanation.

5. 2 and blue, 2 so you can see if it's red and blue so you can see if it's even.

6. Same thing again, 16 to see if its alcoholic, beer to see if their 18.

7. May have to mull this one over a bit. Can't immediately think of any counter examples but not got any reason that it would be true yet.

EDIT: with 7, if you think of it as a network you are essential saying that with friends as nodes you must always have 2 or more nodes with the same order. Now for a network with n nodes, since each person can only be connected to each other person once. The maximum order of a node is n-1. Now they can only take integer values and with n nodes and only n-1 different possibilities at least 2 must have the same value. Now you could say that n-1 possibilities doesn't include 0 but then if a person has no friends in the group then you can just treat the group as having one less member and so the argument still holds.

Again probably made something wrong there, normally seem to overlook something but seems sound to me.

Quote:

---

Originally Posted by Somii

These are the only non-math ones, I think, that no-one else has answered correctly?

---

Actually, I got both of those correct. :P

Does anybody have any more cool puzzles; especially like questions 1, 2 and 7?

I'm busy tonight but I'll try to post optimal answers to those three tomorrow for people to check against.

What about the birthday problem? I think it's common so people will have already heard of it but I'm not sure. I've heard it from a few different places. It's a math/stats problem.

There are a number of people in a room. How many people do there have to be in order for there to be at least a 50% chance that at least two of them share a birthday?

Assume that each person has an equal chance of being born on any particular day.
Assume that there are no leap-years, and that every year contains 365 days.

Are you gonna mark my paper Xei?

I have no idea about your one Dianeva.
I'm gonna just go out on a limb and say 366.
If there were 365 and each birthday has an equal chance, then none would share a birthday.
If you add one more person, their birthday would fall on the same day as someone elses.
But that's not a 50% chance of at least two people sharing the same birthday, that's a 100% chance.
So I dunno lol

182.5?

Oh I see you said "at least" a 50% chance. So I guess I may not be wrong. Probably am anyway lol

182.5 (well 183 whole people) would be the answer to how many people would be needed for a 50% chance that at least one of their birthdays lies on a particular day (ex: a 50% chance that at least one person's birthday is June 10th). But looking for any shared birthday is a different question and the answer is much smaller.

Stubert needs to change his avatar because I keep thinking at first glance that he's tommo lol.

Quote:

---

Originally Posted by PhilosopherStoned

Actually, I got both of those correct. :P

---

Looking back at mine, I see that I had misread his question as he implies that all cards with even numbers are red on the other side. So the result is of my version #3 as wrong. :( As for your answer to #6 - it's not necessarily correct :)


As for those of you lacking an adequate explanation as to how one is to arrive at the answer belonging to question #3. A friend of mine explained it as such: "Suppose ten thousand people take the test. 1% (100 people) have cancer and of those 80 will test positive. Of the 10,000 people, 9900 do not have cancer. 9.6% of those will test positive, which is 950 people. A total of 1030 people test positive, of which 80 have cancer. So if you receive a positive result, the probability you have cancer is 80/1030 = 0.078, abut one chance in 13."

Quote:

---

Originally Posted by Dianeva

182.5 (well 183 whole people) would be the answer to how many people would be needed for a 50% chance that at least one of their birthdays lies on a particular day (ex: a 50% chance that at least one person's birthday is June 10th). But looking for any shared birthday is a different question and the answer is much smaller.

---

Actually the correct answer for that problem 253.

For n people the chances of having at least one birthday lying on a given day is

1 - (364/365)^n

Or (364/365)^n for it not being on a given day.

Chances of it being on a given day for:
n=1, 0.27%
n=10, 2.71%
n=20, 5.34%
n=50, 12.82%
n=100, 23.99%
n=200, 42.23%
n=250, 49.93%
n=300, 56.09%
n=400, 66.63%
n=500, 74.63%
n=750, 87.22%
n=1000, 93.57%
n=1500, 98.37%
n=2000, 99.59%
n=4400, ~100%





For the original birthday problem, 1 - 365!/((365-n)!*365^n) is the chance of having a shared birthday in a group of n people.

Thanks. I saw your edits lol. Before seeing your final answer I did it myself too and got 253 as well.

Final answer obtained from what you had but solving for n, then replacing p with 0.5 and calculating.

p = 1 - (364/365)^n
n = log[base 364/365] (1 - p)

To be fair, I hadn't actually worked it out before. I was copying that answer from some website. I thought those things never lied!
Do the newer graphing calculators let you solve logarithms the 'normal' way with a custom base? I'm sick of having to solve for log[base a]b with log b / log a.

Quote:

---

Originally Posted by Dianeva

182.5 (well 183 whole people) would be the answer to how many people would be needed for a 50% chance that at least one of their birthdays lies on a particular day (ex: a 50% chance that at least one person's birthday is June 10th). But looking for any shared birthday is a different question and the answer is much smaller.

Stubert needs to change his avatar because I keep thinking at first glance that he's tommo lol.

---

How can it be smaller?

Hmmmm....

Gonna think type here....
If there's only 2 days and I need to find the amount of people needed to have a 50% chance of them having a birthday on the same day, the answer would be 2 people.

6 days, there is a 1/6 chance that 1 person will have a birthday on any given day. So.... fuck I just had this.... So to have a 3/6 chance of two people having the same birthday, so.... fuck.... This isn't gonna work, I don't know maths at all lol

Ok, ignore that I think.... Unless I was on the right track, then tell me lol

I think 1/365 chance of any given birthday. But you need it at a 182.5/365 chance.

So you need 91.25 people.

10 possible days. 1/10 chance for any given day. Need a 50% chance of two people on any given same day. If you have two people only, given the 1/10 chance, it raises it to a 1/20 chance. To get it down to a 1/10 chance again you would need ?2 people?
If I fucked that up I'll fuck up the rest of this... but here goes.

365 days. 1/365 chance for any given day. Need 50% chance of two people on any given same day. If there are two people, the chance is 1/730. If there are two people the chance is 1/365. If there are 3 people, the chance is 1/182.5. If there are 4 people, the chance is 1/91.25. If there are 4 people, the chance is 1/45.625. If there are 5 people, the chance is 1/22.8125. If there are 6 people, the chance is 1/11.40625. If there are 7 people, the chance is 1/5.703125. If there are 8 people, the chance is 1/2.8515625.

I'm just gonna say 9 people.

If I were bad at reasoning it would be likely that I'd come up with a bad reason as to why I was good at reasoning (due to my lack of reasoning skills leading me to falsely conclude I was good at it.) Since I haven't done that I must be good at reasoning.

Okay, here's the answers. They've pretty much all been done now, though there are simpler options:

Spoiler for Answers:

1. Coin n gets flipped for every number that divides n except 1, so coins with an odd number of divisors will be heads, and an even number will give tails.

For each number p that divides n, you get a second number q such that p*q = n, for instance, for n = 12

1*12
2*6
3*4,

so the only way a number can have an odd number of divisors is if for one of the divisors the second number is the same, e.g. for 36

1*36
2*18
3*12
4*9
6*6.

In other words, p = q, i.e. n = p*q = p^2, i.e. n is a square number.


2. A line can intersect another straight line at most once. Each time your cut hits another cut, or hits the edge of the pizza, you add another piece. So you get 1 piece for 0 cuts, 1 + 1 = 2 pieces for 1 cut, 2 + 2 = 4 pieces for 2 cuts, 4 + 3 = 7 pieces for 3 cuts, ... , 22 pieces for 6 cuts.

Technically all we have proved is that 22 is the maximum; it could be that it's impossible to intersect each line with a previous cut. But we can draw a diagram to show that it is possible:

http://img41.imageshack.us/img41/849/pizzab.png

And thus the maximum number of pieces for 6 cuts is 22.

It seems 'obvious' that you can always cut the previous lines no matter how many there are, but can you prove it..?


4. Simple math; total people claiming to be tree-huggers is 80 + 950 = 1030, total people claiming to be tree-huggers who are tree-huggers is 80, thus the fraction is 80/1030.

This was not a hard question, so why did I include it? Because it's actually exactly the same as question 3. The probability that somebody is a tree hugger is 100/10,000 = 1%, the probability that you find out they are when they are is 80/100 = 80%, and the probability that you think falsely that they are when they aren't is 950/9900 = 9.6%.


3. Like all of these questions, you don't actually need to know any maths. You just need to know that the probability of something being A when there are n things which are A and m things in total is n/m, which is obvious.

Draw a rectangle representing 10,000 average people. Split it into two groups, those with cancer and those without, and work out the number of people in each group. Then further split each group according to positive and negative test results, so you have four groups, (those with cancer who test positive, those with cancer who test negative, those without cancer who test positive, those without cancer who test negative). Work out the numbers in each and you can then easily work out the ratio of the number people who have cancer and positive tests to the total number of people who have positive tests.

The thing about this question is that if you are clear headed and define exactly what the question means, you easily see that it is the same question as 3, which is just simple arithmetic. Amazingly only 15% of doctors were able to do the question, but far more are able to do it when you change it into a problem about numbers of people rather than probabilities.


5. We obviously need to check that the card with an even number is red on the other side. We do not need to check the red card; if it was odd on the other side then that wouldn't contradict even cards being red (and for the same reason you don't need to turn over the card with a 1). We do however need to check the blue card, because if it were even on the other side then it would contradict even cards being red.

Again hardly anybody gets this, yet they do get the next question, which is exactly the same but with different words.


6. Obviously you need to check that the 16 year old isn't drinking alcohol and that the person drinking beer isn't under 18.


7. If my claim were false, we could have a group of n people where no two of them had the same number of friends, i.e. n people all with a different number of friends.

There are only n options (0 friends, 1 friend, ... , n - 1 friends), thus we must have one person with 0 friends, another person with 1 friend, ... , one person with n - 1 friends, i.e. friends with everybody.

However, if we have somebody who is friends with everybody, we can't have somebody who is friends with nobody, as they would have to be friends with at least this person.

Quote:

---

Originally Posted by tommo

I'm just gonna say 9 people.

---

Given n people, you need to work out the probability that none of them shares a birthday, i.e. n people have n different birthdays, i.e. person 2 doesn't have person 1's birthday, person 3 doesn't have person 2 or person 1's birthday, etc.

As for the other questions you asked for, 1 is wrong because the assertion that all coins get flipped to tails isn't right (just consider coin 4), 2 is correct and for the right reason, 3 is definitely wrong because it would mean testing positive for cancer doesn't make it more likely that you have cancer, 4 I'm guessing was an arithmetic slip, 5 is wrong because a red card having an odd number on the back doesn't contradict my claim that all cards with even numbers on the back are red, for 6 you need to check the drink of the 16 year old, the reason for 7 is wrong (why don't you have to check it for groups of size 3 or more; my claim is about groups of any size?). For more detail check the spoiler.

So apparently the answer to "How good are you at reasoning" is "pretty damn good, but can make silly errors". Which is nothing new to me.

Your answer to #7 is definitely more concise. Why I didn't think to phrase it like that, I don't know :p

I guess it's something you pick up in a maths degree; how to hone in on the crux of your argument and make it as simple and lucid as possible. It always makes the problem look easy, but most of the time it's infuriatingly hard to actually do. You have to learn quite quickly that your 'obvious' argument that you can't quite put into words is in fact probably wrong.

Question 7 is in fact a question from one of the official example sheets for the graph theory course here at Cambridge (well, the exact question was 'show that all graphs of size 2 or greater have two or more vertices of the same order'), so well done to those who got it. :P

If you want to have a go at honing your logic, here's quite a similar question from a different course:


8. On Hawaii, everybody has mobile phones, but naturally there are some people who don't know the phone numbers of other people (and if Alohi has Laka's number, Laka doesn't necessarily have Alohi's number).

We say that Alohi can communicate with Laka if Alohi knows the number of somebody who can then phone somebody else and so on until finally somebody phones Laka.

It can be shown that this splits the island into a distinct number of communicating groups, in which everybody can communicate with everybody else in the group.

Show that there is at least one communicating group which can't contact anybody outside the group.

[Part 2: show this isn't true for an infinite island].

Quote:

---

Originally Posted by Xei

I guess it's something you pick up in a maths degree; how to hone in on the crux of your argument and make it as simple and lucid as possible

---

http://i1112.photobucket.com/albums/...ks/abd-151.gif

Quote:

---

Originally Posted by Xei

5. We obviously need to check that the card with an even number is red on the other side. We do not need to check the red card; if it was odd on the other side then that wouldn't contradict even cards being red (and for the same reason you don't need to turn over the card with a 1). We do however need to check the blue card, because if it were even on the other side then it would contradict even cards being red.

---

I disagree with this. That's what I first thought of. But, you said 5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you.

1, 2, red, blue.

If red were odd, it would contradict the claim. If 1 was red it would also contradict the claim. If 2 was blue, it would also contradict the claim. If blue was 2 it would also contradict the claim.

It is not the same as the drinking question like you said. The drinking question only goes one way. The 21 year old or whatever will not be illegal no matter what. A red card can have an odd number though. Which would contradict your claim.

Quote:

---

Originally Posted by Xei

Given n people, you need to work out the probability that none of them shares a birthday, i.e. n people have n different birthdays, i.e. person 2 doesn't have person 1's birthday, person 3 doesn't have person 2 or person 1's birthday, etc.

---

Again.

1 Knew the first one was wrong lol
2 is correct and for the right reason - Pwned
3 is definitely wrong - Knew that too lol
4 I'm guessing was an arithmetic slip - Nope, although I guess you could call it that. I just haven't done maths in a long time and I'm not good at it.
5 is wrong because a red card having an odd number on the back doesn't contradict my claim that all cards with even numbers on the back are red - As stated, I disagree with this.
6 you need to check the drink of the 16 year old - I said that hapharzadly, but fair enough, was just mucking around.

the reason for 7 is wrong (why don't you have to check it for groups of size 3 or more; my claim is about groups of any size?). For more detail check the spoiler.
You said "7. In any group of (two or more) people, there are always at least two people with the same number of friends in that group. True or false?"
So I just went with 2 people. Not thinking you meant it would have to apply to groups with over 2 people as well.

Quote:

---

Originally Posted by Xei

7. If my claim were false, we could have a group of n people where no two of them had the same number of friends, i.e. n people all with a different number of friends.

There are only n options (0 friends, 1 friend, ... , n - 1 friends), thus we must have one person with 0 friends, another person with 1 friend, ... , one person with n - 1 friends, i.e. friends with everybody.

However, if we have somebody who is friends with everybody, we can't have somebody who is friends with nobody, as they would have to be friends with at least this person.

---

I have no idea what you mean here.

Quote:

---

Originally Posted by tommo

I disagree with this. That's what I first thought of. But, you said 5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you.

1, 2, red, blue.

If red were odd, it would contradict the claim. If 1 was red it would also contradict the claim. If 2 was blue, it would also contradict the claim. If blue was 2 it would also contradict the claim.

It is not the same as the drinking question like you said. The drinking question only goes one way. The 21 year old or whatever will not be illegal no matter what. A red card can have an odd number though. Which would contradict your claim.

---

It's subtle but 'the cards with even numbers are red' is not the same thing as 'the cards with even numbers are the red cards'. The latter means the evens and only the evens are red and thus a red card must be even, the former does not. There could be three red cards in that deck, but it would still be true that 'the even cards are red' (but not true that the even cards are the red cards).

Quote:

---

I have no idea what you mean here.

---

Not sure how I can simplify it. The claim is that in any group of people, some people have the same number of friends. If we think the claim is not true, we must be claiming that we can find a group where everybody has a different number of friends. We show that that is impossible. It's a proof by contradiction. It's the same method you would use to prove the claim that everybody on Earth but you is in your room.

... just means fill in the blanks in the obvious way for the rest of the cases.

Quote:

---

Originally Posted by Xei

It's subtle but 'the cards with even numbers are red' is not the same thing as 'the cards with even numbers are the red cards'. The latter means the evens and only the evens are red and thus a red card must be even, the former does not. There could be three red cards in that deck, but it would still be true that 'the even cards are red' (but not true that the even cards are the red cards).

---

Ok I'm honestly not trolling here or anything. But I simply don't agree.
Even if you are correct, it is incredibly vague and therefore not a good question.

I claim that cards with even numbers are red on the other side. I put the cards in front of you.

1, 2, red, blue.
red, blue 3 4

You said the cards with even numbers are red on the other side.

In this case, I am showing a possible result from flipping them all over, with the bottom line being the opposite side.

1 is red on the other side, proving your claim false - Because the red card has an odd number
2 is blue, proving your claim false - Because the even number is blue
red is 3, proving your claim false - Because the red card has an odd number
blue is 4, proving your claim false - Because the even number is blue

"We do not need to check the red card; if it was odd on the other side then that wouldn't contradict even cards being red"
See, the way you worded the question makes it seem like red cards also have to be even numbers. In fact, it's the only correct way to interpret your question.

I never said that there were two reds and two blues. I also never said that there were cards with a 3 and a 4 on the back.

If this had been the question you would be correct, but it wasn't, and it isn't ambiguous. I made no statements at all about how many of each there were, and it isn't implicit.

I never said there were two of each either....
Never mind.... It's obvious you don't understand what I'm saying. I'll leave it at that.

Well no I don't really understand, because what you're saying is logically wrong and thus impossible to understand. 'Even cards are red' doesn't mean 'red cards are even'. 'English people are British' doesn't mean 'British people are English'. This just follows from the basic meaning of the words and I still don't think you've explained it.

red=even even=red.

If the question said "all even cards are red, but not all red cards are even" then I'd say your answer was correct, and it was what I was thinking in the first place. I just changed my mind because it seemed too obvious.

Well, 'all even cards are red, but not all red cards are even' is equivalent to 'even cards are red'. It's just straight from the definition of how qualification works. It's clear when you consider more intuitive adjectives in exactly the same grammatical structure. For example, 'bats are mammals' means 'all bats are mammals, but not all mammals are necessarily bats'.

Quote:

---

Originally Posted by tommo

But I simply don't agree.

---

Do you often find yourself disagreeing with logic?

Nope. Just Chuck Testa.

Quote:

---

Originally Posted by Xei

1. Coin n gets flipped for every number that divides n except 1, so coins with an odd number of divisors will be heads, and an even number will give tails.

For each number p that divides n, you get a second number q such that p*q = n, for instance, for n = 12

1*12
2*6
3*4,

so the only way a number can have an odd number of divisors is if for one of the divisors the second number is the same, e.g. for 36

1*36
2*18
3*12
4*9
6*6.

In other words, p = q, i.e. n = p*q = p^2, i.e. n is a square number.

---

This is sufficient to claim that the coins that are heads up will be squares. As I pointed out earlier, it's not sufficient to claim that the set of heads-up coins is equivalent to the sets of squares, i.e. that "the sqaures" is the answer. For that, you need to show that every square will have an odd number of divisors...

I don't see how it isn't clear from the construction that a square will have an odd number of divisors? It will have an even number of non-square factors and one square factor. i.e. means equivalence and you can follow the implication backward from the last line if you really want.

I guess it depends on how rigourous you want to be. Normally when a proposition is of the "if and only if" style, one expects to see both sides at least acknowledged.

As for 8:

The problem isn't clearly stated. It could occur that everybody is in the same group (everyone has everyone else;s phone number), in which case we'd have to admit the empty group, hence making the problem trivial. It's also not specified that these are maximal groups in which case the assertion isn't correct either. Simply take the group that can't contact anyone and split it in two.

So lets assume:

1) each group has some maximality condition associated with it. I picked: If person p is not in group G then either p cannot contact anyone in G or no one in G can contact p.
2) there are at least two such groups.



Take a finite group. Pick another group that someone in this group can contact. Continue this way with the second group so that someone in the second group can contact the third group and so on. There are three possibilities.

1) we will eventually pick a group in which there are no external contacts
2) we will loop back around to a group we have already picked


Suppose the second occurs. Trim the chain from the beginning to first occurance of the group that was picked twice. Then any person in any of the groups can contact any person in any of the other groups that occur by following the chain to the group that contains the other person. But that person can then contact the first person in the same way. This contradicts the assumption of maximality and leaves only the first option which was to be proved.

For the second part, we construct an example. Let person n be able to contact person n+1 and n+2 if n is even and person n-1 if n is odd.

Note that it doesn't matter how many people we have, just how many groups we have.

Quote:

---

Originally Posted by PhilosopherStoned

The problem isn't clearly stated. It could occur that everybody is in the same group (everyone has everyone else;s phone number), in which case we'd have to admit the empty group, hence making the problem trivial.

---

The case being trivial doesn't somehow make the assertion incorrect... I was careful to be conscious of the case that Hawaii is a single group when I wrote it.

Quote:

---

It's also not specified that these are maximal groups in which case the assertion isn't correct either. Simply take the group that can't contact anyone and split it in two.

---

Although the ambiguity isn't fatal to the question, I see what you mean. I'm having to paraphrase technical mathematical terms in terms of intuitive things so it's a bit rough around the edges (as I'm sure you know I'm basically talking about a kind of equivalence relation partitioning a set, but that would be to much jargon for most people). I'll try to fix it.

Anyway.

Quote:

---

So lets assume:

1) each group has some maximality condition associated with it. I picked: If person p is not in group G then either p cannot contact anyone in G or no one in G can contact p.
2) there are at least two such groups.



Take a finite group. Pick another group that someone in this group can contact. Continue this way with the second group so that someone in the second group can contact the third group and so on. There are three possibilities.

1) we will eventually pick a group in which there are no external contacts
2) we will loop back around to a group we have already picked


Suppose the second occurs. Trim the chain from the beginning to first occurance of the group that was picked twice. Then any person in any of the groups can contact any person in any of the other groups that occur by following the chain to the group that contains the other person. But that person can then contact the first person in the same way. This contradicts the assumption of maximality and leaves only the first option which was to be proved.

---

All looks good.

Quote:

---

For the second part, we construct an example. Let person n be able to contact person n+1 and n+2 if n is even and person n-1 if n is odd.

---

There's a slight blip because person 1 is a closed communicating class here, but yeah I know what you mean. I suppose you could have labelled the islanders with the integers.

My answer was even simpler though kind of trivial.

Quote:

---

Originally Posted by Xei

The case being trivial doesn't somehow make the assertion incorrect... I was careful to be conscious of the case that Hawaii is a single group when I wrote it.

---

I must be missing something then. If we consider the trivial group a valid communicating group then why isn't it a member of every set? In that case the proof goes:

The empty set is a member of every set. There is no one in the empty set. Hence the empty set constitutes a group in which no one can contact anybody outside of that group.

That's a correct statement, there's just no meat to figuring it out.

Quote:

---

I'm having to paraphrase technical mathematical terms in terms of intuitive things so it's a bit rough around the edges (as I'm sure you know I'm basically talking about a kind of equivalence relation partitioning a set, but that would be to much jargon for most people). I'll try to fix it.

---

Yeah, this is tough stuff. Jargon exists for a reason. Consider the fact that my proof of question one really goes:

Suppose N is square. Decompose the set of divisors, S, into orbits under the involution f(d) = N/d. Then each orbit has at most two elements. If N = n^2 then the orbit of n has only one element. But all other elements lie in an orbit with two elements, hence the order of S is k*2 + 1 for some k and must be odd. Conversely suppose that S is of odd order. Splitting it into orbits under f, we can count it as K*2 + j*1 with j odd and j > 0. So there is at least one orbit with one element, n. Then f(n) = N/n = n and N = n^2.

Jargon allows precision and brevity.

Quote:

---

There's a slight blip because person 1 is a closed communicating class here, but yeah I know what you mean. I suppose you could have labelled the islanders with the integers.

---

Yeah, I'm trying to keep stuff short but I should have at least included the n >= 0 part. Or labeled with the integers. So person 1 would be in a class with person 0 who could contact person 2. Person 3 would be in a class with person 2 who could contact person 4, etc.

Quote:

---

My answer was even simpler though kind of trivial.

---

I'd like to see it. Your proof of #7 was very nice. You're good at writing short proofs. It makes me feel like I overindulge in formality...

It wasn't much simpler; it was just 1 can contact 2, 2 can contact 3, etcetera. Yours is just as good at illustrating the point at hand.

Quote:

---

Originally Posted by PhilosopherStoned

I must be missing something then. If we consider the trivial group a valid communicating group then why isn't it a member of every set? In that case the proof goes:

The empty set is a member of every set. There is no one in the empty set. Hence the empty set constitutes a group in which no one can contact anybody outside of that group.

That's a correct statement, there's just no meat to figuring it out.

---

Well, the statement is about any size group. The fact that this encompasses a trivial case where the group is the set just isn't a problem. And it happens all the time... the fundamental theorem of algebra includes the trivial case of polynomials of degree 1, rank nullity includes the case of vector spaces of dimension 0, etc. etc.

Quote:

---

Originally Posted by Xei

It wasn't much simpler; it was just 1 can contact 2, 2 can contact 3, etcetera. Yours is just as good at illustrating the point at hand.


Well, the statement is about any size group. The fact that this encompasses a trivial case where the group is the set just isn't a problem. And it happens all the time... the fundamental theorem of algebra includes the trivial case of polynomials of degree 1, rank nullity includes the case of vector spaces of dimension 0, etc. etc.

---

Yeah, yeah. We're talking past each other cause I was confused about something. Trivial case as in zero size is no problem. The trivial case with only one group is trivially true though because they can't contact anyone outside the group by virtue of there being no one outside the group. I was somehow missing that. Simplicity wise, I was thinking you had a simpler proof of the main part. I feel like there is one.

1. This is an interesting question. I'm going to say the answer is that every coin with an odd number of multiples is heads.

2. 22

3. This one is kind of a doozy. I'm not sure of my answer. If you test positive for having cancer, you have a 7.69% chance of having cancer.

4. 7,920 out of 104,900. Or 792 out of 10,490

5. The second and fourth card.

6. Given the information, you have to check if the 16 year old is drinking beer and you have to check if the person drinking beer is underage.

7. True. If there are two friends together, there must be a third friend for one of the two friends to have one more friend than the other. But with the addition of a third friend, there are now two people with only one friend in the group. There must be two more friends added to the group to give one of the single-friended friends more friends than the friend with two friends. But this means yet more friends must be added to the the group to give these new additions a different number of friends than that guy with only a single friend. This goes on for infinity. Thus, a group of two people or more containing a finite number of people must have at least two people that have the same number of friends.


Edit: I see where I went wrong with number 4. I added the twenty people who were tree huggers but would not admit it.

80/1030

Found a few nice questions whilst browsing one of my tutor's websites for revision stuff and remembered this thread. Again, none of them require maths knowledge.


1. I draw N circles on a piece of paper. Prove that they divide the paper into no more than N(N - 1) + 2 regions.


2. x is any number on the number line such that x + 1/x is a whole number. Prove x^n + 1/x^n is also a whole number, for any positive whole number n.


3. We have the set of consecutive numbers from 1 to some even number, for instance, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Now we take one more than half of the numbers from this set, for instance, {2, 3, 4, 7, 9, 10}.

a) Prove that in this new set, there will be two numbers with no common factors (for instance, 4 and 9).

b) Prove that in this new set, one number will divide another (for instance, 3 and 9).


4. You wish to drive around a mountain. There are fuel stops at various places on the road, and the total amount of fuel in them is exactly enough to make the journey once. Prove that it's possible to make the journey in a car with an empty fuel tank from some fuel stop.


5. There are six towns. Between each pair of towns is either a bus service or a train service, but never both. Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport.

Does this have to be true for five towns?

my thouoghts, without looking at anyone else's answers:

1. every coin is flipped except the first one

2. 24

3. 90.4% chance

4.7.77%

5. I would only need to flip the card with 2 on it

6. what the 16 year old is drinking, and the age of the guy drinking beer

7. true

probably all wrong :p

Mathematician circlejerk....

Technically it's an n-gon jerk. But if you don't want to play could you please bawww elsewhere, it's a little embarrassing to watch and you're killing the mood.

Quote:

---

Originally Posted by Xei

But if you don't want to play could you please bawww elsewhere, it's a little embarrassing to watch and you're killing the mood.

---

http://www.youtube.com/watch?v=iCv_OEtTn2M

I'm terrible at reasoning. I failed basic logic, I overgeneralize all the time, I believe in the gambler's fallacy (stats just don't make sense to me at all), and I tend to believe eyewitness testimonies over objective evidence. When I start an argument, I never take the time to define premises clearly, or ambiguous terms. It just takes too much effort, y'know?

Oh wait. That's not me at all. I'm the opposite of that. How could I forget?

Quote:

---

Originally Posted by Xei

Technically it's an n-gon jerk. But if you don't want to play could you please bawww elsewhere, it's a little embarrassing to watch and you're killing the mood.

---

In reality, circles don't have points, therefore you cannot classify it as n-gon. I wasn't bawwwing either, I was simply pointing out being good at maths does not mean you are good at reasoning. And vice versa.

Quote:

---

Originally Posted by tommo

In reality, circles don't have points, therefore you cannot classify it as n-gon

---

I think that was Xei points exactly, as each person would represent a point and you'd therefore not be circle jerking.

And in reality you can't form a circle out of a chain of masturbators. ;)

Like I said, the questions are not intended to require mathematical knowledge. If I wanted to pleasure the mathematicians here I would have done some tricky integrals or some groups questions which would have looked like Greek to everybody else. Though to be honest I think reasoning and mathematics (the action rather than the body of knowledge) are pretty synonymous, and indeed the whole point of the questions was to allow everybody to have a go at the kind of questions that a mathematician would typically tackle, but specially picked so that you didn't have to know anything at all about maths per se.

That was the goal, anyway. I suppose that question 1 requires a modicum of algebra to complete, but that's not really important. If you want, exchange N circles with 6 circles and N(N - 1) + 2 regions with 32 regions. Then the only knowledge you need is what 6 and 32 are and what circles are.

Question 2 is the most algebra heavy, but it's the kind of very basic stuff you learn at school. And question 3 only requires a basic familiarity with numbers, if you know for instance how to split something into factors you're fine. But if you really hated maths at school then I'd leave those two out.

And then questions 4 and 5 really are pure reasoning questions.

Please add your own, that was the point of the thread in the first place.

Quote:

---

Originally Posted by khh

I think that was Xei points exactly, as each person would represent a point and you'd therefore not be circle jerking.

---

Oh, right.:lol:

But yeah I might try them out just coz I like to test my intelligence.

A penny saved is worth two in the bush.

Quote:

---

Originally Posted by tommo

I was simply pointing out being good at maths does not mean you are good at reasoning. And vice versa.

---

I think we would all be surprised to know how much our structure of logic and mathematics are actually related.

Quote:

---

Originally Posted by Wayfaerer

I think we would all be surprised to know how much our structure of logic and mathematics are actually related.

---

Oh, no doubt. But one doesn't imply the other.
But definitely. You need logic if you want to figure out any problem with already knowing the method , not just maths.

Fuck mathematics! I'm balancin' my checkbook!

I'd be very interested to see people take a crack at 5. It's purely a reasoning question. I basically did it straight off; it will be particularly interesting to see (though to go into details why would give it away at the moment) if that's down to being trained to think like a mathematician, or simply because it's quite an easy question.

And somebody else please post some other cool puzzles. :(

4 and 5 seem to prove themselves for me, you start empty at one out of multiple gas stations that have enough fuel to take you around the mountain, so you're able to go around the mountain and you never said there had to be any trains, so there could just happen to be 3 towns next to each other with car transportation in between. The proof is in the pudding. The other ones are a bit beyond me.

Sorry, number 4 is kind of hard to express clearly. I had the same misinterpretation when I first read it... of course, that's not what it means, the answer is totally trivial. No, the total amount of fuel in all of the fuel stops combined is enough to travel around the mountain once, not in each and every fuel stop. Hopefully it makes much more sense as a puzzle now. It is not immediately obvious that you can do it, because some stops might not contain enough fuel to make it to the next stop, even if combined there is enough fuel to make the trip once.

As to number 5, it's true that I didn't say there had to be any trains, and so it is possible that each town could just have a bus service. But that is not a proof that this is necessarily true for the kind of situation I described; although it is possible that there aren't any trains, it is also possible that it isn't the case that there aren't any trains.

You could definitely do number 1 if you took a crack at it, just replace it with,

1. I draw 6 circles on a piece of paper. Prove that they divide the paper into no more than 32 regions.

The answer is very pretty.

Quote:

---

Originally Posted by Xei

1. I draw N circles on a piece of paper. Prove that they divide the paper into no more than N(N - 1) + 2 regions.

---

I don't know how to prove this without just doing it, which is kind've pointless I guess.

Quote:

---

Originally Posted by Xei

2. x is any number on the number line such that x + 1/x is a whole number. Prove x^n + 1/x^n is also a whole number, for any positive whole number n.

---

Hmmmm, yep..... ok, yep
Yes, I know some of these words....

Quote:

---

Originally Posted by Xei

3. We have the set of consecutive numbers from 1 to some even number, for instance, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Now we take one more than half of the numbers from this set, for instance, {2, 3, 4, 7, 9, 10}.

a) Prove that in this new set, there will be two numbers with no common factors (for instance, 4 and 9).

b) Prove that in this new set, one number will divide another (for instance, 3 and 9).

---

Oh god....
See, again, I could just do this a few times, but it's not really proving anything, one needs to know maths to prove it.

Quote:

---

Originally Posted by Xei

4. You wish to drive around a mountain. There are fuel stops at various places on the road, and the total amount of fuel in them is exactly enough to make the journey once. Prove that it's possible to make the journey in a car with an empty fuel tank from some fuel stop.

---

Even if they all have unequal amounts of fuel?

I don't think it's always possible. Say 100km is the full distance. The first fuel stop is only full enough to go 1km and the next fuel stop is 2km away. Fail straight away.
Or was this worded incorrectly?

Quote:

---

Originally Posted by Xei

5. There are six towns. Between each pair of towns is either a bus service or a train service, but never both. Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport.

Does this have to be true for five towns?

---

I don't know what "pairs of towns" means, but I'm going to assume they're laid out like this. (Oh wait I get it now, but this suffices anyway)

Actually fuck I don't even need a diagram.
Why is this a question? Just take a bus between each town. Or do you not know whether it will have a train or a bus before you get there?
If so, it's impossible. It may work one time, if there is a bus to each town but not another time, if there's a train fucking up your whole plan.

I know how you're thinking about it, but it doesn't work IRL.

For example in number 4, thinking like a mathematician you would say "Okay well if we start at the stop (which could be in the middle or whatever) which has the most fuel, we can suddenly make it the rest of the way".
But thinking in IRL terms, you just start out at the start of the mountain.

4. The point is that it's a circular path; you don't have to start at any fuel stop, you can choose. The question is to prove that there is always some station or other that you can start from, and get all the way round (running out of fuel at the very end). And I promise that it is always possible. ;)

The practical basis of the question doesn't really matter of course, it's just there to explain what the puzzle is. Maybe you get to the mountain by helicopter or something. The original question was about travelling round the moon in a moon buggy, I just changed it to something slightly less confusing.


5. To clarify the 'pairs of towns' thing; you've got six towns, A, B, C, D, E, F. It just means that between any two towns, for instance B and F, there is either a bus service or a train line. I'm not sure what you mean by taking a bus between each town; every single connection between towns could be a train line.

You don't need to travel to a town to find out what services it has. You know everything about the towns and which services are between them. The question is to prove that for whatever the situation is, it'll be possible to find three towns all connected by the same type of service, in a triangle.

Again, it's definitely possible to prove.

Number one looked the most interesting to me, and I haven't looked at any answers yet so I don't know if this is right.

Every n^2 coin (where n is a positive integer) should be heads up (1, 4, 9, 16...). I came up with this by counting the number of times each coin would be flipped from 1 to 10. Even number of flips = heads. Odd number = odd. That gave me 1, 4, and 9. I tested 25 and 36 which both worked, and the pattern becomes obvious.

Ill probably try the other ones tomorrow, but aren't two of them just applied conditional probability?

Yes, in fact they were exactly the same question. It's just that one of them was phrased in terms of numbers of things, which people are normally fine at; the other was phrased in terms of probabilities, which people tend to baulk at, when really if you just put it in intuitive terms it's fine. So it was kind of a test at how good people are at boiling things down to their definition.

Your guess about the coins is correct, but guessing the answer is only 10% of the work, of course. The 90% is in finding out the secret behind the pattern, in other words proving it in general.

Quote:

---

Originally Posted by Wayfaerer

Best answer possible.

---

Lol... I don't get why 'just take buses' is such a popular 'answer'.

Quote:

---

Originally Posted by Xei

4. The point is that it's a circular path; you don't have to start at any fuel stop, you can choose. The question is to prove that there is always some station or other that you can start from, and get all the way round (running out of fuel at the very end). And I promise that it is always possible. ;)

---

So.... this.

Quote:

---

Originally Posted by tommo

For example in number 4, thinking like a mathematician you would say "Okay well if we start at the stop (which could be in the middle or whatever) which has the most fuel, we can suddenly make it the rest of the way".
But thinking in IRL terms, you just start out at the start of the mountain.

---

So yes I know it is always possible. But it requires you knowing the amount of fuel in each stop, and choosing the one with the most fuel to start at.

Ok....say there are 10 stops over 100km. Stop 1 (wherever you start) must have the most fuel, otherwise you won't make it.
If it does have the most fuel, you will make it.

Basically write this in to a maths equation to prove it :lol:

Stops and km's of fuel in each stop
0--10-20-30-40-50-60-70-80-90-100km
60-10-5---5--5---5--5--5---0--0--0

Start (0) will get you to 60km by itself, but you're picking up stop 2, 3, 4, 5, 6, 7 and 8 along the way.
Giving you 100km of fuel by stop 8.

I'd actually enjoy knowing how to put this in to an equation. I should get around to learning one day.
But I don't know if this question really tests reasoning.... Maybe it does but it seemed pretty obvious straight away that it's possible.
As long as you're not thinking about it as a real life situation. Which is what most people do.

Quote:

---

Originally Posted by Xei

5. To clarify the 'pairs of towns' thing; you've got six towns, A, B, C, D, E, F. It just means that between any two towns, for instance B and F, there is either a bus service or a train line. I'm not sure what you mean by taking a bus between each town; every single connection between towns could be a train line.

You don't need to travel to a town to find out what services it has. You know everything about the towns and which services are between them. The question is to prove that for whatever the situation is, it'll be possible to find three towns all connected by the same type of service, in a triangle.

Again, it's definitely possible to prove.

---

Fine, take either all buses or all trains :lol:

Ok, math thinking again....

You have six towns and only two different modes of transport.
There may be 1 train 5 buses, you can go between 3 towns on buses,
2 trains, 4 buses, you can go between 3 towns on buses
3 trains, 3 buses, you can between 3 town on either,
etc. vice versa

Again, can't really figure out how to get this in to an equation.

Quote:

---

Originally Posted by Xei

Lol... I don't get why 'just take buses' is such a popular 'answer'.

---

I think it is possibly because the question is fairly simple.
I mean.... if you know there are buses or trains, take the bus to a town with a bus, take that bus to another town with a bus that will take you back to the first town.

When I said 4 and 5 didn't require maths knowledge, I wasn't trying to mislead anybody. Honest, they really don't, they're plain old reasoning problems.

There are no equations involved; there's no method I've learned for doing these questions, they're novel problems. The point is to devise your own method.


4.

Quote:

---

Originally Posted by tommo

But I don't know if this question really tests reasoning.... Maybe it does but it seemed pretty obvious straight away that it's possible.

---

One of the first things you learn to do in a maths degree is to distrust yourself whenever you think a question is obvious. If something looks obvious, yet you can't actually explain in plain words why exactly it's true, it can't really be said to be obvious at all; and indeed, it will often turn out that you are wrong, or at least that the answer is not as obvious as it seems.

A great example of this is actually your proposed solution, namely, "wherever you start must have the most fuel, otherwise you won't make it". This does seem obvious, but can you actually explain in clear terms why it is the case?

If you can't, start to doubt that it actually is the case. See if you can come up with an example where you don't start from the stop with most fuel.


5.

Quote:

---

Ok, math thinking again....

You have six towns and only two different modes of transport.
There may be 1 train 5 buses, you can go between 3 towns on buses,
2 trains, 4 buses, you can go between 3 towns on buses
3 trains, 3 buses, you can between 3 town on either,
etc. vice versa

---

I think the only way to solve this one is to actually draw it and mess around.

What you're talking about currently is not actually what I described; there are not 6 different services in total. There are lines between each PAIR of towns. Like this.

http://upload.wikimedia.org/wikipedi...aph_K6.svg.png

The key to solving these problems is to first break it down into its absolute simplest terms. A boiled down version of this question would be, "if you colour each line either red or blue, do you always have to draw a triangle of one colour?".

Alright, let's see if we can pull the 'ol modus ponens and find some answers.

Quote:

---

Originally Posted by Xei

1. I draw N circles on a piece of paper. Prove that they divide the paper into no more than N(N - 1) + 2 regions.

---

http://img268.imageshack.us/img268/1848/0531121754.jpg

Quote:

---

Originally Posted by Xei

2. x is any number on the number line such that x + 1/x is a whole number. Prove x^n + 1/x^n is also a whole number, for any positive whole number n.

---

I interpret this as,

x ∈ ℤ, where ƒ(x) = [x + (1/x)], and ƒ(x) ∈ ℤ.

ƒ₂(x) = [x^n + (1/x^n)], where ƒ₂(x) ∈ ℕ only when n ⊂ x.

I'm not sure the first function should look like [(x+1)/x] or [x+(1/x)].

If I were to take the sum of the geometric series which results from expanding ƒ₂(x) while keeping x static at some value, namely 2, then the series doesn't have a common ratio and does diverge to an arbitrary whole number.

Quote:

---

Originally Posted by Xei

3. We have the set of consecutive numbers from 1 to some even number, for instance, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Now we take one more than half of the numbers from this set, for instance, {2, 3, 4, 7, 9, 10}.

a) Prove that in this new set, there will be two numbers with no common factors (for instance, 4 and 9).

b) Prove that in this new set, one number will divide another (for instance, 3 and 9).

---

B ⊂ A and A ∪ B and B ∩ A. If both sets are communicative with respect to the other, and each set contains elements of the other, then every valid operation for the set A will be valid for the set B. The number of valid operations depends on the total number of elements taken from the consecutive sequence set to the subset B and is proportional to limiting value of ½+1 number of elements in the subset.

Quote:

---

Originally Posted by Xei

4. You wish to drive around a mountain. There are fuel stops at various places on the road, and the total amount of fuel in them is exactly enough to make the journey once. Prove that it's possible to make the journey in a car with an empty fuel tank from some fuel stop.

---

Do you mean the car or the fuel stations when you say "them"? The gas stations would need to be at equivalent distances around the mountain and the surface of the terrain would need to be consistent for this to be possible.

Quote:

---

Originally Posted by Xei

5. There are six towns. Between each pair of towns is either a bus service or a train service, but never both. Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport.

Does this have to be true for five towns?

---

There will always be at least one more bus than train station or vice versa between all the towns, and no that doesn't have to be true for five towns.

http://img802.imageshack.us/img802/4599/0531121833.jpg

1. It's quite easy for 3, but can you work out how to prove it for 6 circles and 32 regions?

Also the solution requires a brief explanation of why you can't create more regions.

2. x is not generally an integer.

3. I guess you're using some more general theorem I haven't encountered yet. I don't really understand your answer. How does your solution fail when the set has less than n + 1 elements?

4. Fuel stations. If you add up all of the fuel in each station, there's just enough to make the journey once. It's possible for any position of the fuel stops around the route; the question is to prove this.

5. I make it 15 different services between towns, so I accept that there will always be at least one more of one type of transport. I don't see how the conclusion follows (i.e. that you will always be able to travel in a loop through three towns via only one means of transport).

Quote:

---

Originally Posted by Xei

When I said 4 and 5 didn't require maths knowledge, I wasn't trying to mislead anybody. Honest, they really don't, they're plain old reasoning problems.

---

Oh, I couldn't even remember you saying that.

Quote:

---

Originally Posted by Xei

4.
One of the first things you learn to do in a maths degree is to distrust yourself whenever you think a question is obvious. If something looks obvious, yet you can't actually explain in plain words why exactly it's true, it can't really be said to be obvious at all; and indeed, it will often turn out that you are wrong, or at least that the answer is not as obvious as it seems.

A great example of this is actually your proposed solution, namely, "wherever you start must have the most fuel, otherwise you won't make it". This does seem obvious, but can you actually explain in clear terms why it is the case?

If you can't, start to doubt that it actually is the case. See if you can come up with an example where you don't start from the stop with most fuel.

---

Yes, of course it is possible. But it won't be possible every time, I already stated that (if you start at one with 1km of fuel and need to go 2km).
Whereas to keep it simple, all you have to know is which pump has the most fuel.

Maybe I should have said "wherever you start must have the most fuel, otherwise you are less certain to make it".
I can't explain in clear terms why this is so. I can picture it in my head but can't grasp it fully.
If you have 100km's of fuel, distributed around a 100km circle you still have 100km's of fuel.
You could also start at a pump which has less than the most full pump if the distance to pump 2 is shorter than the amount of km's you get from pump 1.

See this is where I thought some algorithm would come in handy, coz you could figure out the least fuel you would need from each pump, given their distances apart etc.
It's tangential to the question, but still.

You seem to be changing the question though. You just said "prove that it's possible", at first. And I did.

Quote:

---

Originally Posted by Xei

5.
I think the only way to solve this one is to actually draw it and mess around.

What you're talking about currently is not actually what I described; there are not 6 different services in total. There are lines between each PAIR of towns. Like this.

http://upload.wikimedia.org/wikipedi...aph_K6.svg.png

The key to solving these problems is to first break it down into its absolute simplest terms. A boiled down version of this question would be, "if you colour each line either red or blue, do you always have to draw a triangle of one colour?".

---

Ok, what you should have said is "There is a line (or, service, whatever) connecting each town to each other town". That's much more clear. Or just put the picture up first.

You did it here again, btw
First you said "Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport."
Now you're saying "do you always have to draw a triangle of one colour?" i.e Is there always a way between 3 towns using one mode of transport.

Quote:

---

Originally Posted by tommo

Oh, I couldn't even remember you saying that.


Yes, of course it is possible. But it won't be possible every time, I already stated that (if you start at one with 1km of fuel and need to go 2km).
Whereas to keep it simple, all you have to know is which pump has the most fuel.

Maybe I should have said "wherever you start must have the most fuel, otherwise you are less certain to make it".
I can't explain in clear terms why this is so. I can picture it in my head but can't grasp it fully.
If you have 100km's of fuel, distributed around a 100km circle you still have 100km's of fuel.
You could also start at a pump which has less than the most full pump if the distance to pump 2 is shorter than the amount of km's you get from pump 1.

See this is where I thought some algorithm would come in handy, coz you could figure out the least fuel you would need from each pump, given their distances apart etc.
It's tangential to the question, but still.

You seem to be changing the question though. You just said "prove that it's possible", at first. And I did.

---

The question is to prove that it's always possible.

Obviously it's possible in some circumstances. For instance, there could simply be one stop with all of the fuel. The question is to prove it can be done in all circumstances, for any given arrangement of fuel pumps.

Are you saying that if you start from the stop with most fuel, you are certain to make it..? Is that the basis of your argument?

Quote:

---

Ok, what you should have said is "There is a line (or, service, whatever) connecting each town to each other town". That's much more clear. Or just put the picture up first.

---

I simply copied the question from its source. It isn't ambiguous. There's a service between each pair of towns... what else can that mean?

I didn't put the picture up because working out what the picture looks like is part of the question. I only put it up now because lots of people did not have the right picture in mind.

Quote:

---

You did it here again, btw
First you said "Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport."
Now you're saying "do you always have to draw a triangle of one colour?" i.e Is there always a way between 3 towns using one mode of transport.

---

It don't understand what you think the difference is.

The two formulations are equivalent, it's just that the latter is boiled down to the absolute basics of what you need to prove, minus all of the superfluous information about travelling and things.

Quote:

---

Originally Posted by Xei

The question is to prove that it's always possible.

Obviously it's possible in some circumstances. For instance, there could simply be one stop with all of the fuel. The question is to prove it can be done in all circumstances, for any given arrangement of fuel pumps.

---

Well, that's not what it said.
So, wherever they are, choosing a certain starting point will enable you to complete the course.
But as I said, I don't know how to prove this, I just know that it's possible.
It seems like some maths is required for this.
The best way I can explain is to give examples like I did before, but obviously that doesn't suffice.

Quote:

---

Originally Posted by Xei

Are you saying that if you start from the stop with most fuel, you are certain to make it..? Is that the basis of your argument?

---

No.
If the one with the most fuel has a huge distance, you may not make it.
But if you start at the one after it and collect all the smaller amounts of fuel (which will be closer together) you will make it.

I can't see how it's a difficult question, it's just difficult to explain why.
There's always 100km's of fuel. You just have to choose the correct one to start at.
Which would differ every time depending on amount of fuel and distance between each one.

Quote:

---

Originally Posted by Xei

I simply copied the question from its source. It isn't ambiguous. There's a service between each pair of towns... what else can that mean?

---

What I thought at first.

Quote:

---

Originally Posted by Xei

I didn't put the picture up because working out what the picture looks like is part of the question. I only put it up now because lots of people did not have the right picture in mind.

---

Hmmmm, what does that say about the question? Maybe that it is ambiguous.
It's pretty obvious that "There is a line (or, service, whatever) connecting each town to each other town" is infinitely more clear.

Quote:

---

Originally Posted by Xei

It don't understand what you think the difference is.

---

"Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport."
Means, show that you can travel through three towns in a loop using one mode of transport. So everyone says, "Ok, I'll go through town with only buses."

The other one is saying that you need to prove that you can ALWAYS travel through 3 towns in a loop using one mode of transport, no matter which modes of transport are between each town.

You'll probably need to switch your mind out of mathematician mode to be able to see the difference, but I've tried to explain it clearly.

I guess they were phrased by a mathematician for a mathematician and we have certain ways of speaking. In both questions, you're given the conditions first, so the implication is that the object already objectively exists. You can't choose it. To prove that you can do it, it is therefore required that you prove you can do it for all circumstances which satisfy the conditions, and hence the specific circumstance that you'll have been provided with.

I suppose we are also used to talking about pairwise conditions, but really it isn't ambiguous. In your original interpretation, which involved six lines, if you actually drew it and asked, 'is it true here that every pair of towns is connected, as required?', the answer would have been no. It's an understandable misunderstanding though.

As to question 4 not being difficult but it being hard to explain why... well, the entire question is to explain why, which nobody has come close to yet. The question isn't 'can you do it', you're already told that you can definitely do it. The challenge is to prove the assertion. And like I say, I can speak from plenty of experience: whenever something seems obvious and yet you can't actually explain why it's obvious, you probably don't actually have any justification, and could well be wrong. The human brain is only capable of making very basic inferences; if your contention can't be pinned down to any inferences, it begs the question where your contention is coming from in the first place.

Consider this question (this is just a metaphor, not a puzzle for the thread): you have three dice, A, B, C, (they are cubes), with numbers on each face (not necessarily 1 to 6). Prove that if die A is more likely to beat die B, and die B is more likely to beat die C, then die C can't be more likely to beat die A.

Would you say that this is roughly as obvious as the fuel question?

Pedagogy aside, now that you get the gist of the towns puzzle, I recommend you take a shot at it.

The third problem is eerily related to the classic NP problem, one of the seven greatest problems of the century.

Every proof question is essentially NP. That's one of the reasons why P = NP would be so dramatic; a computer could prove any theorem in polynomial time.

It's probably the hardest question there, certainly the second part.

Quote:

---

Originally Posted by Xei

I guess they were phrased by a mathematician for a mathematician and we have certain ways of speaking. In both questions, you're given the conditions first, so the implication is that the object already objectively exists. You can't choose it. To prove that you can do it, it is therefore required that you prove you can do it for all circumstances which satisfy the conditions, and hence the specific circumstance that you'll have been provided with.

I suppose we are also used to talking about pairwise conditions, but really it isn't ambiguous. In your original interpretation, which involved six lines, if you actually drew it and asked, 'is it true here that every pair of towns is connected, as required?', the answer would have been no. It's an understandable misunderstanding though.

---

The problem was that I automatically put them in 3 pairs.
OO
OO
OO

So I didn't think about "pairs" the way it's meant.

But anyway.... I think you pretty much get why people are confused at these types of questions sometimes.

Quote:

---

Originally Posted by Xei

Consider this question (this is just a metaphor, not a puzzle for the thread): you have three dice, A, B, C, (they are cubes), with numbers on each face (not necessarily 1 to 6). Prove that if die A is more likely to beat die B, and die B is more likely to beat die C, then die C can't be more likely to beat die A.

Would you say that this is roughly as obvious as the fuel question?

---

Not really. At first it seems obvious. But then I quickly realise that I don't know what the numbers are so C could easily beat A.

Quote:

---

Originally Posted by Xei

Pedagogy aside, now that you get the gist of the towns puzzle, I recommend you take a shot at it.

---

Quote:

---

5. There are six towns. Between each pair of towns is either a bus service or a train service, but never both. Prove that you can always () travel through three towns in a loop (without visiting any others) with only one type of transport.

Does this have to be true for five towns?

---

Think it's probably easiest to explain with a diagram.

Say all possible second town's paths (excluding ones leading back to the first town) are trains, but you've taken a bus to the second town. This is the worst situation.
But you can just start instead at one of the other towns, which all have all trains in loops.

Like this.

http://i.imgur.com/qs1fD.png

But then we can eliminate some of those paths to break the loops.
I'll break all of them.

http://i.imgur.com/xbz2G.png

But this just opens up several loops to take buses on again.

I keep confusing myself trying to figure out the possible paths and why there are always loops available.

Basically, as soon as you cut off enough loops (by replacing them with the other type of transport) you have just created loops for the other type of transport.

Quote:

---

Originally Posted by Xei

But that's not the only information you have, is it? A beats another die B, and that die B beats C. So surely it's obvious that A beats C?

---

Yeah but, who knows. What are the rules? Highest number?
Anyway....

Quote:

---

Originally Posted by Xei

This is basically just a restatement of what the question is rather than an answer. Of course, for the assertion of the question to be true, it must be true that breaking loops will create another loop. But it's not clear that this will always happen. Maybe for some specially created circumstance you haven't considered yet it will fail. Also, if this argument works, it shouldn't matter how many towns there are; but are you sure it is even true for any number of towns (consider 5)?

Playing with maps is the right general way to go about it, though. I recommend you try taking the birds eye view of the transportation planner, rather than the perspective of the person setting out on a journey.

---

I realise my answer doesn't suffice. And also that it is better not to think of it like a person taking a journey, but I'd started like that and so went with it. I haven't done anything like this for years and I think my brain is having trouble grasping precisely what I'm thinking. I rewrote that like 5 times coz I kept getting mixed up with my train of thought haha

I will re-attempt it tomorrow, even though I'm getting over it now.

Why the fuck did that post go before yours, and shows me posting it an hour before you?
That's a real puzzle right there. :D

Why the fuck did that post go before yours, and shows me posting it an hour before you?
That's a real puzzle right there. :D

Quote:

---

Originally Posted by tommo

Not really. At first it seems obvious. But then I quickly realise that I don't know what the numbers are so C could easily beat A.

---

But that's not the only information you have, is it? A beats another die B, and that die B beats C. So surely it's obvious that A beats C?

Quote:

---

Basically, as soon as you cut off enough loops (by replacing them with the other type of transport) you have just created loops for the other type of transport.

---

This is basically just a restatement of what the question is rather than an answer. Of course, for the assertion of the question to be true, it must be true that breaking loops will create another loop. But it's not clear that this will always happen. Maybe for some specially created circumstance you haven't considered yet it will fail. Also, if this argument works, it shouldn't matter how many towns there are; but are you sure it is even true for any number of towns (consider 5)?

Playing with maps is the right general way to go about it, though. I recommend you try taking the birds eye view of the transportation planner, rather than the perspective of the person setting out on a journey.

I'm gonna start knocking these out in a few days if you guys are done playing...

Quote:

---

Originally Posted by Xei

6. In the UK you can drink at 18. There are four people drinking at the bar. One is 21, one is 16, one is drinking coke, one is drinking beer. What do I have to check to make sure nobody is breaking the law?

---

The 16 year old is on one side of the bar drinking coke. On the other side of the bar is the 21 year old barmaid, the landlady and the landlord. The landord is drinking the beer. The barmaid, landlord and landlady have to be at least 18 to be on the serving side of the bar.

There wasn't anything clever about the way the situation was described. There are literally four people sat at the bar with drinks, that's all. You know for sure that one is 21, another is 16, another is drinking coke, and another is drinking beer. The question is to determine the minimum amount of information about drinks and ages I would need to obtain to be sure that nobody is breaking the law.

It isn't supposed to be very hard at all. The point is that it's coupled with the cards question one so try that too.

Quote:

---

Originally Posted by PhilosopherStoned

I'm gonna start knocking these out in a few days if you guys are done playing...

---

I look forwards to it. And no appealing to arcane theorems please! :P

I started reading around some of the basics of graph theory a couple of days after I set that towns puzzle (which I knew nothing at all of beforehand) and it turns out that one of the most famous theorems has this as a simple consequence (which, thinking about it, is no doubt what inspired the tutor to set this as an introductory puzzle for undergrads in the first place). Can't remember the name but it was to do with graphs with every vertex joined (which is what the towns are) having subgraphs with every vertex joined (which is what a triangle is) when you colour the edges.

When a few of them have been knocked down (which none have so far), I'll put up some really awesome riddles I've found recently which are definitely pure reasoning riddles with nothing to do with mathematics.

Well technically you'd also need to check the age of the person serving the drinks, and whether the bar has a valid license to sell alcohol. And that it wasn't violating various health and safety laws. And....

It's funny because the reasoning behind puzzles like these are by design capable of being demonstrated from many facets of mathematical understanding.

Quote:

---

Originally Posted by Xei

1. Along the right lines, but doesn't check out with the actual numbers (2 is non-prime but tails for example).

---

This brought me joy to an otherwise dull day.

Sorry tommo, didn't see the posts. To be fair you did put them in a silly place.

Quote:

---

Originally Posted by tommo

Yeah but, who knows. What are the rules? Highest number?

---

If it were the highest number on the die that determined the winner then A would indeed always beat C. But as I imagine you guessed, it's not true. It seems very obvious, but if you relied on this intuition, and a reason that you 'know but can't put into words', you'd be incorrect. It is of course normally true. But there are various dice for which it is not true. For instance,

die A has sides: 2, 2, 4, 4, 9, 9
die B has sides: 1, 1, 6, 6, 8, 8
die C has sides: 3, 3, 5, 5, 7, 7.

You can work out the probabilities of A beating B and so on (any pair of numbers from the two dice is equally likely to come up, so just count the ones which win). You find that the probability that A rolls a higher number than B is 5/9 (55.55%), the probability that B rolls a higher number than C is 5/9, and the probability that C rolls a higher number than A is 5/9.

Quote:

---

I realise my answer doesn't suffice. And also that it is better not to think of it like a person taking a journey, but I'd started like that and so went with it. I haven't done anything like this for years and I think my brain is having trouble grasping precisely what I'm thinking. I rewrote that like 5 times coz I kept getting mixed up with my train of thought haha

I will re-attempt it tomorrow, even though I'm getting over it now.

---

Like all of these things, the answer is hard to get, but very easy to understand. It can be explained in two or three short sentences, I think.

Quote:

---

Originally Posted by Dreams4free

This brought me joy to an otherwise dull day.

---

I saw what you did there.

Even numbers are never prime. Sure you could tout 2 as a so called 'counter-example' but that would just be cherry-picking, wouldn't it. :P

Clearly I'd been studying too hard and was actually thinking in Z[√-5]... thankfully what I said does actually make sense in context. Very well spotted though.

Since people are playing again, I'll hold off on solutions. I will give a counter-example to the claim that one can circum-navigate the mountain by starting at the stop with the most fuel...

We'll have four depots. One has one third of the gas and each of the other three has two ninths. Starting from the stop with one third, one can traverse the circle in either direction and can hence potentially reach any point on two thirds of the circle. So one only needs to cluster the remaining three depots within the remaining one third of the circle to assure that starting at the point with the most gas will end in failure.

Quote:

---

Originally Posted by Xei

Sorry tommo, didn't see the posts. To be fair you did put them in a silly place.

---

Hehe. Probably didn't understand my post in the meta forum thread then about time-travel.

Quote:

---

Originally Posted by Xei

If it were the highest number on the die that determined the winner then A would indeed always beat C. But as I imagine you guessed, it's not true. It seems very obvious, but if you relied on this intuition, and a reason that you 'know but can't put into words', you'd be incorrect. It is of course normally true. But there are various dice for which it is not true. For instance,

die A has sides: 2, 2, 4, 4, 9, 9
die B has sides: 1, 1, 6, 6, 8, 8
die C has sides: 3, 3, 5, 5, 7, 7.

You can work out the probabilities of A beating B and so on (any pair of numbers from the two dice is equally likely to come up, so just count the ones which win). You find that the probability that A rolls a higher number than B is 5/9 (55.55%), the probability that B rolls a higher number than C is 5/9, and the probability that C rolls a higher number than A is 5/9.

---

So.... yes my "intuition" or whatever, was correct. :D
(Not really intuition, I did think about it a bit, just not too much).

Quote:

---

Originally Posted by Xei

Like all of these things, the answer is hard to get, but very easy to understand. It can be explained in two or three short sentences, I think.

---

Ok what about this....
There will be, at worst (because any more of each will create multiple circuits of one transport type), 7 buses and 8 trains.

Ala,
http://i.imgur.com/soda5.jpg?4478

The one from top left to bottom right can be red, otherwise it creates 2 green circuits. But making it red creates a red circuit.

http://i.imgur.com/y1n7C.jpg?2237

And breaking that circuit in any way will create a green circuit (light green and yellow are green ones breaking red circuit).

http://i.imgur.com/oQd5Y.jpg

This I guess is still not proof, but you can't prove it wrong at least. So fuck it.

Quote:

---

Originally Posted by PhilosopherStoned

Since people are playing again, I'll hold off on solutions. I will give a counter-example to the claim that one can circum-navigate the mountain by starting at the stop with the most fuel...

We'll have four depots. One has one third of the gas and each of the other three has two ninths. Starting from the stop with one third, one can traverse the circle in either direction and can hence potentially reach any point on two thirds of the circle. So one only needs to cluster the remaining three depots within the remaining one third of the circle to assure that starting at the point with the most gas will end in failure.

---

And fuck you.

Quote:

---

Originally Posted by tommo

And fuck you.

---

You're welcome.

That's not bad at all tommo, you're definitely approaching the right direction to tackle it, in particular the bit about a single line not being able to be green or red.

Choosing a 'worst' case is also a good way to go about it, though you need to start simpler, and you need to think about some kind of 'bad' feature that will be present for every situation, so you get a nice general proof, rather than some specific bad cases where it's not clear how to extend them to every instance.

Edit: Oh, and looking at modified versions of the puzzle is also a common way to gain insight. In particular if you try the second part of the question first, about five towns, and then analyse the solution there.

Quote:

---

Originally Posted by PhilosopherStoned

You're welcome.

---

Feel free to ruin my theories any time.

And Xei, why won't you just let me give up!!?!?!????:lol:

I did realise all that, but I guess it will just take me some time to figure out how to go about doing it.

I believe there is only one solution for 5. The solution is obviously special if you look at it / draw it right, and should give you quick insight into how to do 6.

By all means feel free to give up. :P

OK. Time to start knocking them out.

Quote:

---

Originally Posted by Xei

4. You wish to drive around a mountain. There are fuel stops at various places on the road, and the total amount of fuel in them is exactly enough to make the journey once. Prove that it's possible to make the journey in a car with an empty fuel tank from some fuel stop.

---

For a contradiction, supose that some arrangement of depots exists for which it is not possible. Choose a direction of traversal. Each depot, T, defines a segment, S(T) of the road which is reachable by starting from T, traveling in the given direction, and stopping at all reachable depots along the way. There is at least one depot, T₁, which defines a longest segment. Start at T₁ and travel until you run out of gas. Push the car to the next depot. The car hence traverses some distance D₁ of roadway with no fuel. Fill the car with fuel and procede in this manner until you arrive at the starting point. You hence completed one circuit of the road and put enough enough fuel in the car for precisely one circuit. However the car was pushed for distance D = D₁ + ... + D_n and so there must be enough gas left in the tank to travel D units of distance. This means that there is some depot, T₂, such that T₁ is reachable from it. Specifically, it will be the last depot into which the car had to be pushed. But then S(T₂) is longer than S(T₁) because it properly contains the latter segment and this contradicts our assumption that S(T₁) is maximal. Hence there must always be an arrangement of depots such that there is at least depot, T, with S(T) being the entire road.

Hope that's reasonably clear.

That looks solid to me. Definitely an interesting and elegant attack, why did you go about it like that? I did it by induction on the number of stops, though I did read a nicer answer than either of these (it was closer to your idea).

Thank you kindly. I saw the opportunity for an induction proof but figured that one based on contradiction would be good for non-mathematicians to read. In my experience, it's the easier method to grasp and apply.

Actually, the depot that I call T₂ is a depot from which one can complete the entire route, it just seemed easier to claim a contradiction than to prove it. Starting at T₂ one arrives at T₁ with enough fuel to cover precisely the distance which one would have to push the car if one had started at T₁ instead. That would probably be a nicer way to do it.

I think that was a fairly round about way of doing it, tbh.

It was quite literally a round-about way of doing it in that one went all the way around the route. But it was my first stab at the problem. Here's my second draft. This is probably closer to the nicer way that Xei alluded to.

Choose any depot to start at and procede, stopping to collect all fuel, until the car runs empty. Transport the car to the next fuel depot and repeat the process until arriving at the starting depot. At this point the car was transported without fuel for some distance D. Yet enough fuel was collected (by the terms of the problem) to go all the way around the route precisely once. Hence there is enough fuel to travel for D distance in the tank. If D is zero, then the problem is solved. Otherwise, there is some last stop into which the car needed to be tranported. Were one to start at this stop, then one would reach the original stop with enough fuel to drive a distance of D which is precisely the amount of fuel that is needed to traverse the route from that point.

I thought that's what you were saying before.... Never mind my feeble mind then.

I wanted to comment on problems 5 and 6. These same puzzles were just mentioned in the book I'm reading, The Tipping Point.

You are right, Xei, that it is the same problem framed two different ways and that most people get 6 right, but not 5. The reason for this is that humans are inherently social creatures. We understand and can solve problems involving people much easier than abstract problems.

I'm not sure if it's about social situations per se, but rather domains of human intuition in general... for instance, if I phrased the question as,

'A friend claims that bananas with green skins are sweeter with ones with yellow skins. I want to prove him wrong. I'm given two unpeeled bananas, yellow and green, and two peeled bananas, one of which tastes sweet and the other of which not. What information do I ask for to try to disprove my friend'?

is that any harder?

Quote:

---

Originally Posted by tommo

I think that was a fairly round about way of doing it, tbh.

---

I don't understand what this means at all... it's a simple and precise answer, what did you want instead..?

Quote:

---

Originally Posted by PhilosopherStoned

Choose any depot to start at and procede, stopping to collect all fuel, until the car runs empty. Transport the car to the next fuel depot and repeat the process until arriving at the starting depot. At this point the car was transported without fuel for some distance D. Yet enough fuel was collected (by the terms of the problem) to go all the way around the route precisely once. Hence there is enough fuel to travel for D distance in the tank. If D is zero, then the problem is solved. Otherwise, there is some last stop into which the car needed to be transported. Were one to start at this stop, then one would reach the original stop with enough fuel to drive a distance of D which is precisely the amount of fuel that is needed to traverse the route from that point.

---

Yeah that's pretty much the same. Certainly much closer than my brute forcing by induction.

Spoiler for Simple solution to 4:

Drive around the route in a different vehicle from some random position, with a large tank and enough fuel to make it without using the fuel stops. Fill up at each stop anyway, and record how much more or less fuel there is in the tank than your starting amount. To get all the way around using only the fuels in the stops, simply start from the stop where you recorded having least fuel arriving there. The amount of fuel in your car can never drop below this level, so you can make it all the way.

Quote:

---

Originally Posted by tommo

I thought that's what you were saying before.... Never mind my feeble mind then.

---

It's basically the same. I just phrased it as a constructive proof rather than as a proof by contradiction. This is simpler because by the time one had done enough work to get the contradiction, one had already constructed a solution to the problem.

Quote:

---

Originally Posted by PhilosopherStoned

It's basically the same. I just phrased it as a constructive proof rather than as a proof by contradiction. This is simpler because by the time one had done enough work to get the contradiction, one had already constructed a solution to the problem.

---

Ah! ok. Yes that's what I gathered, cool.

Quote:

---

Originally Posted by Xei

I don't understand what this means at all... it's a simple and precise answer, what did you want instead..?

---

It was a joke. Because

Quote:

---

This is simpler because by the time one had done enough work to get the contradiction, one had already constructed a solution to the problem.

---

And he had to go.... around.... and stuff

Quote:

---

Originally Posted by Xei

Spoiler for Simple solution to 4:

Drive around the route in a different vehicle from some random position, with a large tank and enough fuel to make it without using the fuel stops. Fill up at each stop anyway, and record how much more or less fuel there is in the tank than your starting amount. To get all the way around using only the fuels in the stops, simply start from the stop where you recorded having least fuel arriving there. The amount of fuel in your car can never drop below this level, so you can make it all the way.

---

Is this even proof? Why can you get all the way around from the stop where you had the least fuel? Just because it cannot drop below that level, doesn't mean you can make it to the next stop.

The amount of fuel in your car will go up and down by the same amounts that it went up and down in the test car with the large tank with ample fuel. You start at the stop where the test car had least fuel. When you start there, you have 0 fuel. So the least fuel you will have on your journey will be this amount; 0. Hopefully this now makes it clear that you can make the journey. You collect the fuel at the stop, and the amount never falls lower than 0. If you always have fuel during the journey, there won't be any point at which you stop.

Late to the party, but I thought I'd take an honest stab at a few of these.

Quote:

---

Originally Posted by Xei

1. You have a row of 1,000 coins, all of which are heads up. You flip the second, fourth, sixth, and all other even coins over so that they're tails. Then you flip over the third, sixth, and all other coins which are multiples of three. Now you do this for every fourth coin, every fifth coin, etcetera, all the way up to every thousandth coin (which means just flipping the last one).

The question is this: which coins are heads up, and why? There is a concise and surprising answer.

---

Given that flipping over that many coins is tedious (and that I can't trust the help staff not to steal any of them), I've hired a team of software engineers to write a script to simulate the sequence. In full 3D and everything!

I'll get back to you when they're done.

Quote:

---

Originally Posted by Xei

2. What's the maximum number of pieces you can cut a pizza into using a cheese wire (i.e. straight cuts) if you can only cut six times? The pizza is to thin to cut horizontally, and too hot to pick up and move around.

---

Well, since the pizza would likely be a novelty appetizer, I would be content having it cut into 16 quaint squares. No need to maximize the piece yield per pizza, as the kitchen staff can always make more.

Quote:

---

Originally Posted by Xei

3. There's a 1% chance that the average person has cancer. Somebody with cancer has an 80% chance of testing positive when they go for a scan. Somebody without cancer has a 9.6% chance of testing positive (i.e. getting a false positive). You go for a scan and receive a positive result. What is the probability that you have cancer?

---

Well, balls.

Either way, the statistics are unimportant. I will assume a 100% chance and solicit myself for pity sex and Reddit karma immediately.

I'll get a second opinion tomorrow.

Quote:

---

Originally Posted by Xei

4. 100 people out of a group of 10,000 are tree-huggers. You ask all 10,000 people if they hug trees or not. 80 out of the 100 people who hug trees are honest about it and say yes. 950 out of 9,900 people who don't hug trees also pretend that they do. What fraction of people who claim to hug trees are genuine tree-huggers?

---

An important question, as we must quickly find and detain these genuine tree huggers indefinitely and without trial.

A cursory review shows 80 people out of the 1030 who claim to be tree huggers do, in fact, hug trees. However, this isn't good enough. We must find the 20 out of 8970 people who are covering up their true identity.

Furthermore, I propose action against these supposed tree hugging sympathizers who would lie to my face about their loyalties to industry, capitalism, and imperialism!

I will have my father send notice to his government contacts immediately.

Quote:

---

Originally Posted by Xei

5. I have four cards with numbers on one side and colours on the other. I claim that cards with even numbers are red on the other side. I put the cards in front of you. They are

1, 2, red, blue.

Which cards do you need to turn over to check my claim?

---

While I only need to turn over 2 and blue to check your claim, I will instead flip them all over to ensure you aren't trying to conceal any tree hugger secrets from me.

I'm on to you lot.

Quote:

---

Originally Posted by Xei

6. In the UK you can drink at 18. There are four people drinking at the bar. One is 21, one is 16, one is drinking coke, one is drinking beer. What do I have to check to make sure nobody is breaking the law?

---

Are you a police officer? If so, good. I need you to come with me immediately; the tree huggers are holding a peaceful protest--where the new mall is planned to go up--and they must all be arrested so they can face proper justice!

If not...why are you bothering these people? What gives you the right, huh? HUH?!

Quote:

---

Originally Posted by Xei

7. In any group of (two or more) people, there are always at least two people with the same number of friends in that group. True or false?

N.B. you can only be friends with somebody who is friends with you!

---

Don't be silly. My father taught me at a very young age that there's no such thing as "friendship." Only money and what you can buy with it.

Quote:

---

Originally Posted by Xei

8. On Hawaii, everybody has mobile phones, but naturally there are some people who don't know the phone numbers of other people (and if Alohi has Laka's number, Laka doesn't necessarily have Alohi's number).

We say that Alohi can communicate with Laka if Alohi knows the number of somebody who can then phone somebody else and so on until finally somebody phones Laka.

It can be shown that this splits the island into a distinct number of communicating groups, in which everybody can communicate with everybody else in the group.

Show that there is at least one communicating group which can't contact anybody outside the group.

[Part 2: show this isn't true for an infinite island].

---

Some lonely bastard either has no one's number, or no service plan with which to place a call, and thus can only communicate with himself, putting him outside of all other communication circles. Sad, really.

Also, an infinite island is impossible because with infinite land, you can have no surrounding water. Come on, man.

Quote:

---

Originally Posted by Xei

1. I draw N circles on a piece of paper. Prove that they divide the paper into no more than N(N - 1) + 2 regions.

---

Hard to say unless I know how good you are at drawing circles. At how high an N do your muscles start to spasm?

It might be better to have a robot built to figure this out. Or better yet! I'll add this simulation to my software engineers' to-do list!

Quote:

---

Originally Posted by Xei

2. x is any number on the number line such that x + 1/x is a whole number. Prove x^n + 1/x^n is also a whole number, for any positive whole number n.

---

Well, since x can only ever be 1 or -1, and 1 to the power of any whole number n is always one, you can simplify x^n + 1/x^n to the form x + 1/x and be done with the whole mess.

How do I know x can only ever be 1 or -1? I paid people to do that part for me; that's how.

Quote:

---

Originally Posted by Xei

3. We have the set of consecutive numbers from 1 to some even number, for instance, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

Now we take one more than half of the numbers from this set, for instance, {2, 3, 4, 7, 9, 10}.

a) Prove that in this new set, there will be two numbers with no common factors (for instance, 4 and 9).

b) Prove that in this new set, one number will divide another (for instance, 3 and 9).

---

The guy I paid to work through this one said something about there always being at least one even or odd number in each of the 210 odd sets, but I was too busy talking to people in my communication group and exploiting my positive cancer results to pay attention.

Quote:

---

Originally Posted by Xei

4. You wish to drive around a mountain. There are fuel stops at various places on the road, and the total amount of fuel in them is exactly enough to make the journey once. Prove that it's possible to make the journey in a car with an empty fuel tank from some fuel stop.

---

Why drive around the mountain when I can have a tunnel built through it and have fuel delivered to me via helicopter?

That seems much more fun.

Quote:

---

Originally Posted by Xei

5. There are six towns. Between each pair of towns is either a bus service or a train service, but never both. Prove that you can travel through three towns in a loop (without visiting any others) with only one type of transport.

Does this have to be true for five towns?

---

Given that I have access to private helicopters, I could care less about the public transport options and instead fly wherever I'd like. Be it in a loop between three towns, or no.

But alas, the second and third tests I got all came back positive and the MRI scan have revealed a malignant tumor growing in my neck. There's little chance of recovery at this point, so screw these towns, I'm going somewhere more interesting with the little time I have left...

Quote:

---

Originally Posted by Xei

The amount of fuel in your car will go up and down by the same amounts that it went up and down in the test car with the large tank with ample fuel. You start at the stop where the test car had least fuel. When you start there, you have 0 fuel. So the least fuel you will have on your journey will be this amount; 0. Hopefully this now makes it clear that you can make the journey. You collect the fuel at the stop, and the amount never falls lower than 0. If you always have fuel during the journey, there won't be any point at which you stop.

---

But how do you know that it only hits zero once :P

http://shechive.files.wordpress.com/...0&h=375&crop=1

tommo think he funny bunny

Tommo, you need to get a better web-cam. You look like ace ventura.

I assume that by whole, one means integral. Otherwise, there's more work to do.

Quote:

---

Originally Posted by Xei

2. x is any number on the number line such that x + 1/x is a whole number. Prove x^n + 1/x^n is also a whole number, for any positive whole number n.

---

Using strong induction, the one case is given to us. Specifically, x¹ + 1/x¹ is whole by the terms of the problem.

For the inductive case, note that (x^n-1 + 1/x^n-1)(x + 1/x) - (x^n-2 + 1/x^n-2) is whole as, by the inductive hypothesis, each term in brackets is whole. But trivial algebraic simplification reduces this to xⁿ + 1/xⁿ. Hence we've proven it for n as well.

:fame:

Very nice once again.

Have you stumbled across any puzzles yourself for a lay audience?

Here's one:

100 passengers are queuing to board a plane (which seats 100 passengers). The first passenger has lost his boarding pass and so sits in a random seat.

The remaining passengers board one at a time. If their seat is free, they take it. Otherwise, they sit in a randomly chosen seat.

What is the probability that the last passenger who boards will be able to sit in his allocated seat, and why?

Edit: Oh and also assume that the first passenger isn't thrown off for not having the pass, and that the remaining passengers don't refuse to fly for fear of the incompetence displayed by staff and airport security.

Quote:

---

Originally Posted by Xei

Have you stumbled across any puzzles yourself for a lay audience?

---

Haven't been looking. One interesting extension to (2) would be to determine for which integers, n, some real x exists with x + 1/x = n. One could then prove that as n -> infinity, x/n approaches 1. This is more amateur mathematician stuff than "lay audience" friendly though. If we let x(n) be such that x(n) + 1/x(n) = n, and let w_n(k) = x(n)^k + 1/x(n)^k, then it might be interesting to explore the sequences w_n(k) as k tends to infinity. Right now we just have the recurrence formula w_n(k) = w_n(k - 1)n - w_n(k - 2).