Brain teaser thread - Page 12

Rogan Josh · October 28, 2002, 11:07

Edit: Sorry - the answer I just gave was bullshit. Still thinking....

Rogan Josh · October 28, 2002, 11:22

Ok - think I have it now. All the rooms numbered 1,4,16,64.... will have their lights on. ie. numbers 4^n with n=0,1,2,3.....

Not sure I have a rigorous argument why though.

Dauphin · October 28, 2002, 11:27

Those will be on, but so will others.

Just in case I wasn't clear, every 3rd, then 4th, then 5th, then 6th then 7th ... then 998th, then 999th, then 1000th is switched.

Rogan Josh · October 28, 2002, 11:51

Hmmm... well it really depends on how many numbers a given number is divisible by. For example 50 is divisible by 1,2,5,10,25 and 50, so it light number 50 will be switched 6 times so it will be off. Similarly 51 is divisible only by 1 and 51, so it will be flicked twice and also be off. Conservely, 64 is divisible by 1,2,4,8,16,32 and 64 - an odd number of numbers, so light 64 will be on.

So I can see how to see if any particular light is on or off, but I still can't see the general pattern...

You thought this one was easier than the last one? You must have a strange mind...

Dauphin · October 28, 2002, 11:56

What property does a number have to have to have an odd number of factors?

Dry · October 28, 2002, 11:59

Quote:

Originally posted by Combat Ingrid
Here's another one:

It cannot be seen, cannot be felt.
Cannot be heard, cannot be smelt.
It lies behind stars and under hills,
And empty holes it fills.
It comes first and follows after,
Ends life, kills laughter.

Silence?

Dry · October 28, 2002, 12:06

Quote:

Originally posted by Sagacious Dolphin
What property does a number have to have to have an odd number of factors?

Not be a square number.

monolith94 · October 28, 2002, 13:37

I was very tired when I wrote my reasoning… still am… but my train of thought was basically the same as rogan josh's…
Just for the record…

Richard Bruns · October 28, 2002, 14:54

This is a really great thread. I've had fun solving some of these.

The only lights that are on are the rooms with square numbers. But I didn't really solve that.

I have a question about the robbery liars, however. From Rogan Josh's correct answer:

Quote:

Chris lying -> one of Brad or Dave must be telling the truth

I don't see how that can be inferred from the problem. All of them could be lying about the robbery, which means that all of them could be truthful when they say that others are lying about the robbery. You can't infer anything from that information.

I suppose that their statements are meant to refer to who is lying about who is lying, and not about who is lying about the robbery. But that creates a paradox. How can Alex know who is lying until he has heard all the statements of the others? How can any of them make such a statement until they have heard the others? It seems to be an impossible situation, a self-referencing paradox.

Can someone enlighten me?

Also, a couple of comments about the three-way duel. It is very clear that MLeonard gains by not firing. But consider the eventual outcome of the duel:

Once the initiative passes to Ming, he faces the same choice. There are three outcomes. If he plugs MLeonard, he dies when MtG shoots. If he frags MtG, he has a 1/3 chance of getting blasted by MLeonard next turn. If he misses or doesn't shoot, the choice of firing passes to MtG.

If MtG wastes MLeonard, then he has a 2/3 chance of getting inhumed by Ming. If he eliminates Ming, he has a 1/3 chance of kicking the bucket when MLeonard fires.

But MtG knows, at this point, that MLeonard will not fire if all three are left alive. So his best choice of action is to blow down a tree or something, so that everyone is left alive. That way nobody tries to gun him down next turn. If Ming knows that MtG knows this, his best chance of survival is also to not shoot at anybody, because that is the only way that nobody will fire at him next turn.

Basically, if all three are logical and they know that the other two are logical, then nobody will fire in the duel. They will all waste shots until they run out of ammo. Of course, if they were all logical they wouldn't have gotten into a duel in the first place. Three-power situations typically result in standoffs, since nobody gains by taking the forst shot.

Dauphin · October 28, 2002, 15:05

Quote:

Originally posted by Richard Bruns
I suppose that their statements are meant to refer to who is lying about who is lying, and not about who is lying about the robbery.

Correct.

Quote:

But that creates a paradox. How can Alex know who is lying until he has heard all the statements of the others? How can any of them make such a statement until they have heard the others? It seems to be an impossible situation, a self-referencing paradox.

Can someone enlighten me?

Its only a paradox if you take it they know that they are a liar or not. They could all be guessing - then the paradox is removed

Dauphin · October 28, 2002, 15:11

Quote:

Originally posted by Richard Bruns
If MtG wastes MLeonard, then he has a 2/3 chance of getting inhumed by Ming. If he eliminates Ming, he has a 1/3 chance of kicking the bucket when MLeonard fires.

But MtG knows, at this point, that MLeonard will not fire if all three are left alive. So his best choice of action is to blow down a tree or something, so that everyone is left alive. That way nobody tries to gun him down next turn. If Ming knows that MtG knows this, his best chance of survival is also to not shoot at anybody, because that is the only way that nobody will fire at him next turn.

Basically, if all three are logical and they know that the other two are logical, then nobody will fire in the duel. They will all waste shots until they run out of ammo. Of course, if they were all logical they wouldn't have gotten into a duel in the first place. Three-power situations typically result in standoffs, since nobody gains by taking the forst shot.

Depends on if MtG is playing to win, or to not lose.

Ming and ML will never target each other - that would be tantamount to suicide. Therefore MtG's odds will never improve. So if he wants to win he has to shoot someone first.

Zero-Tau · October 28, 2002, 16:46

Quote:

Originally posted by Sagacious Dolphin
A hotel has 1,000 rooms numbered 1 to 1,000. Jack is looking after the hotel for the winter and is going slightly crazy. He decides to flick every roomlight switch in the hotel. He then decides to flick the switch in every other room (starting with room 2). He then flicks the switch in every third room (starting with room three). He then flicks the switch in every fourth room (starting in room 4).

If all lights were originally off, which lights remain on once Jack has finished switching every 1,000^th roomlight switch?

All rooms with square numbers have their lights flicked on. Their prime factorization would be a1^e1*a2^e2*a3^e3... with all exponents being even. Using the formula for the number of divisors (e1+1)(e2+1)(e3+1)... we see that the square numbers have an odd number of divisors, meaning that they'll end up with the lights on. Conversely, if the number of divisors is odd, then each of e1+1, e2+1, e3+1,... would be odd, meaning that all the exponents would be even, making the number a square.

Dauphin · October 28, 2002, 20:15

I've got another one, if no-one posts one in the next hour.

Ramo · October 28, 2002, 20:20

I'm off to a class in 5 minutes. Post it now!

Dauphin · October 28, 2002, 21:07

You have a box with four balls of different colours. If you randomly draw two at a time, then paint the first ball to match the second. What is the expected number of drawings before all balls are the same colour?

Pekka · October 28, 2002, 21:16

I don't have the energy to think but quickly going through options it must be 3 or 4.. I'd go for 4.

Urban Ranger · October 28, 2002, 23:51

More than that.

Urban Ranger · October 28, 2002, 23:56

Balls are not replaced: twice

Balls are replaced:

There are 5 configurations (I use letters instead of colours, it's the same) -
ABCD (original, config 0)
AACD (config 1)
AAAC (config 2)
AACC (config 3)
AAAA (config 4, goal)

config 0 -> config 1 : 1 turn
config 1: 1/2 chance remaining config 1, 1/3 chance becoming config 2, 1/6 chance becoming config 3
config 2: 1/2 chance no change, 1/3 chance becoming config 4 (done), 1/6 chance becoming config 3
config 3: 1/3 chance no change, 2/3 chance becoming config 2

Then I forgot how to convert this into expectations

Dry · October 29, 2002, 04:48

Quote:

Originally posted by Urban Ranger
[...]config 1: 1/2 chance remaining config 1 [...]

So you may never reach config 4.

Urban Ranger · October 29, 2002, 05:01

That's true.

Dauphin · October 29, 2002, 10:35

When you toss a coin there is a possibility that it will never come up heads, but the expected number of throws to get a head is still finite at 2.

JohnM2433 · October 29, 2002, 18:20

Quote:

Originally posted by Zero-Tau
All rooms with square numbers have their lights flicked on. Their prime factorization would be a1^e1*a2^e2*a3^e3... with all exponents being even. Using the formula for the number of divisors (e1+1)(e2+1)(e3+1)... we see that the square numbers have an odd number of divisors, meaning that they'll end up with the lights on. Conversely, if the number of divisors is odd, then each of e1+1, e2+1, e3+1,... would be odd, meaning that all the exponents would be even, making the number a square.

Woah, I didn't even follow all that! As soon as Sagacious Dolphin asked what property a number needs to have an odd number of factors, I just figured: "For every number, each factor will be matched with exactly one corresponding factor so that the two together multiply to the number. A factor will be matched with itself if and only if it is a root of the number, so square numbers and only square numbers will have an odd number of factors, since the factors will come in pairs, except if the number is square, in which case the root will be by itself."

My way seems a lot simpler to me. (My explanation is a bit more wordy than my actual reasoning is complicated, trust me.)

JohnM2433 · October 29, 2002, 19:11

Quote:

Originally posted by Urban Ranger
Balls are not replaced: twice

Balls are replaced:

There are 5 configurations (I use letters instead of colours, it's the same) -
ABCD (original, config 0)
AACD (config 1)
AAAC (config 2)
AACC (config 3)
AAAA (config 4, goal)

config 0 -> config 1 : 1 turn
config 1: 1/2 chance remaining config 1, 1/3 chance becoming config 2, 1/6 chance becoming config 3
config 2: 1/2 chance no change, 1/3 chance becoming config 4 (done), 1/6 chance becoming config 3
config 3: 1/3 chance no change, 2/3 chance becoming config 2

Then I forgot how to convert this into expectations

I think config 2 should be: 1/2 chance no change, 1/4 chance becoming config 4 (done), 1/4 chance becoming config 3. The rest appear to be right.

Assuming that's correct...

The expected number of turns to get to config 4 from config 0, 1, 2, or 3 is 1 plus, for each possible next state, its probability of coming next times the expected number of turns to get to config 4 from that new state. Representing the expected number of turns to get to config 4 from config x by cx, we get

c0 = 1 + c1
c1 = 1 + (1/2)c1 + (1/3)c2 + (1/6)c3
c2 = 1 + (1/2)c2 + (1/4)c3 + (1/4)c4
c3 = 1 + (2/3)c2 + (1/3)c3
c4 = 0

After a lot of algebra, we can conclude that c0 = 9, c1 = 8, c2 = 5.5, c3 = 7, and of course c4 = 0.

So the expected number of turns after the first draw is 8.

JohnM2433 · October 29, 2002, 20:06

OK, most of you should find this one fairly easy:

Three missionaries and three canibals are traveling together and come to a river. None of them can swim, but luckily, there is a boat tied to their side. It can only hold two people. For obvious reasons, the missionaries would prefer that no group of canibals ever outnumber a group of missionaries (where a group can be one, but not zero) at any one place. Figure out a way that they can maintain that condition and get everybody across the river.

If that's too easy for you, you might want to try the more general case of x missionaries and x canibals (I don't actually know whether that can be solved or not).

Jaguar · October 29, 2002, 20:51

1 C and 1 M go over
1 C goes back
2 C go over (1 stays in boat)
1 M and 1 C go back
2 M go over
1 M goes back
1 M and 1 C go over

Dauphin · October 29, 2002, 21:04

Quote:

Originally posted by JohnM2433

So the expected number of turns after the first draw is 8.

9 draws in total.

I'm glad you got the same answer as I did, because I had to work it out myself too. It would have been embarrasing if my calculated answer was wrong.

Jaguar · October 29, 2002, 21:13

What do these words have in common:

Calmness
Canopy
Deft
First
Hijack
Laughing
Stupid

Jaguar · October 29, 2002, 21:14

rowr, new avatar!

Dauphin · October 29, 2002, 22:30

They have 3 consecutive letters that are also alphabetically consecutive.

Calmness
Canopy
Deft
First
Hijack
Laughing
Stupid

Dauphin · October 29, 2002, 22:36

I've got one, that I'm now kicking myself over. It is deceptively simple.

There are nine jars, each containing a different type of liquid, but the labels have all fallen off. Knowing nothing about the contents, a passerby reapplies the labels at random. What is the expected number of correctly labeled jars?