שאלות תכנות - חלק ג

21.

Another well known problem in probability is the Monty hall problem.

You are presented with three doors (door 1, door 2, door 3). One door has a million dollars behind it. The other two have goats behind them. You do not know ahead of time what is behind any of the doors.

Monty asks you to choose a door. you pick one of the doors and announce it. monty then counters by showing you one of the doors with a goat behind it and asks you if you would like to keep the door you chose, or switch to the other unknown door.

Should you switch? If so, why? What is the probability if you don't switch? what is the probability if you do.

Lots of people have heard this problem.. so just knowing what to do isn't sufficient. its the explanation that counts!

The answer is that yes, you should *always* switch as switching increases your chances from 1/3 to 2/3. How so, you ask? Well, let's just enumerate the possibilities.

It's clear that if you just choose a door and stick with that door your chances are 1/3.

Using the switching strategy, let's say you pick door 1. if its case 1, then you lose. if it's case 2, Monty shows you door 3, and you switch to door 2, you win. if it's case 3, Monty shows you door 2, and you switch to door 3, you win. it doesn't matter what door you pick in the beginning, there are always still three possibilities. one will cause you to lose, and two will cause you to win. so your chances of winning are 2/3.

The solution all resides in the fact that Monty knows what is behind all the doors and therefore always eliminates a door for you, thereby increasing your odds.

Maybe it's easier to see in this problem. There are 1000 doors, only one of which has a prize behind it. You pick a door, then Monty opens 998 doors with goats behind them. Do you switch? It seems more obvious in this case, because Monty had to take care in which door not to open, and in the process basically showing you where the prize was (999 out of 1000 times).

22.

A man has a gold chain with 7 links. He needs the service of a laborer for 7 days at a fee of one gold link per day. However, each day of work needs to be paid for separately. in other words, the worker must be paid each day after working and if the laborer is ever overpaid he will quit with the extra money. Also he will never allow himself to be owed a link.

What is the fewest # of cuts to the chain to facilitate this arrangement and how does that guarantee payment?

Can we get change back from the laborer?

If so, we cut one link to make a chain of 4 links, a chain of 2 links and the cut link itself.

Day 1, we give him the cut link Day 2, we take back the cut link, give him the 2 link chain Day 3, we give him the cut link Day 4, we take back both the cut link and the 2 link chain, give him the 4 link chain Day 5, we give him the cut link Day 6, we take back the cut link, give him the 2 link chain Day 7, we give him the cut link

23.

Problem: a one armed surgeon with a hand wound needs to operate on three patients. The surgeon only has two gloves. How can he operate on the three patients in turn without risking exchange of fluids? (Remember he only has one arm so he only needs to wear one glove at a time.)

Solution: the surgeon places both gloves on his hand (1 and 2). he operates on patient A. he then takes the top glove off (#2), leaving on the bottom glove (#1) and operates on patient B. then he carefully reverses glove #2, so the clean side is on the outside, and he places it on top of glove #1 which is on his hand, and operates on patient C.

This problem is kind of dumb because how's the surgeon going to change the gloves on his hand when he only has one hand. plus no offense, but how often do you come across a one-armed surgeon (i'm sure there are plenty of one-armed doctors, but a surgeon!?!). Anyway, i had to make this problem child friendly and changing the story to the above was the only way to do it. Consider for a minute what the initial problem was. The surgeon was just a guy, the patients were women, and the glove was... well, i won't insult your intelligence.

24.

Part I: what is the angle between the minute hand and the hour hand at 3:15 on an analog clock? No, its not 0.

Part II: how often does the minute hand pass the hour hand on an analog clock?

answer:

part I: 12 hours on the clock make 360 deg. so one hour is 30 deg. the hour hand will be directly on the 3 when the minute hand is at 12 (3:00). After 15 minutes or 1/4 of an hour, the hour hand will be 1/4 * 30 deg = 7.5 deg. away from the minute hand.

Part II: if you just think about it, intuitively you'll see the minute hand passes the hour hand 11 times every 12 hours, so it must pass it every 1 1/11 hours. But this doesn't make sense to me. i need to prove it.

If x is our answer then every x hours, the minute hand and the hour hand will be right on top of each other. Every hour the hour hand travels 5 units. so between every time that the minute and the hour hand meet, the hour hand will go 5*x units. every hour the minute hand travels 60 units, so it will have gone 60*x units.

What we're trying to find is the distance traveled by the minute hand to reach the hour hand, once the minute hand has looped around once. Consider its 12:00. Both hands in the same position. After an hour, minute hand is on 12, hour hand on 1 (it's traveled 5 units). Now in the time it takes the minute hand to catch up to the hour hand it will travel a little bit further.

We only need to find x where 5*x = 60*(x-1), since the real distance traveled by the minute hand, from where it started to where it ends, is 60*(x-1). the first hour just puts it back where it started, so we're only concerned with the extra part it traveled to reach the hour hand.

5x = 60(x-1)

5x = 60x - 60

60 = 55x

60/55 = x

There it is. The answer is 60/55 hours, or every 1 and 1/11 hours.

I apologize that this is horribly confusing, but if you stare at it long enough it will make sense.

25.

Problem: at 6 a.m. a man starts hiking a path up a mountain. He walks at a variable pace, resting occasionally, but never actually reversing his direction. At 6 p.m. he reaches the top. He camps out overnight. The next morning he wakes up at 6 a.m. and starts his descent down the mountain. Again he walks down the path at a variable pace, resting occassionally, but always going downhill. At 6 p.m. he reaches the bottom. What is the probability that at some time during the second day, he is in the exact same spot he was in on the first day?

Answer: the probability is 100%. The easiest way to see it is, consider that on the second day when the man is going down the mountain, a ghost follows his original pace up the mountain. So even if he varies his pace as he goes down the mountain, at some point in time, he will be in the same spot as the ghost, and therefore, the same spot he was in the day before.

26.

Problem: you find an old treasure map in your grandma's attic. The map shows a cannon, a coconut tree, and a palm tree. The map states that to find the treasure you must: a. start at the cannon, walk toward the palm tree while counting your paces. When you reach the palm tree, turn 90 degrees to your left and walk the same number of paces. Mark that spot on the ground with a stake. b. start at the cannon again, walk toward the coconut tree while counting your steps. When you reach the coconut tree, turn 90 degrees to your right and walk the same number of paces. Mark that spot on the ground with a stake. c. find the midpoint between the two stakes and dig for the treasure.

You set off in secrecy to the deserted island. upon reaching the shore you site the coconut tree and the palm tree, but someone has removed the cannon. Without digging randomly all over the island, is it still possible to find the treasure?

Solution: this just takes basic geometry skills. when we get to the island all we see are the coconut and palm trees. so lets lay out our coordinate system such that the palm tree is at (0,0) and the coconut tree is at (1,0). it honestly doesn't matter how you describe the coordinate system - you could say the coconut is at (c,0) if you like, or even (0,c) or (0,1). We are just placing our own coordinate system on top of the existing surface. if you use a different system, you will get a different numerical answer but the same positional answer in the real world.

Here is our island. The cannon is at (x,y) because we have no idea where it is, so x and y are the unknowns. (Note the cannon doesn't have to be in the upper right quadrant but it won't make a difference in the solution because x and y could be negative if we want them to be).

If we walk to the palm and turn right we can easily see the way it lays out in the diagram. You basically have just transposed the x and y positions.

It might be easier to think of it as a triangle, and flipping the triangle around to find the point for the next stake at (y, -x)

we do the same thing with the coconut tree, although here its only a tiny bit trickier because we have to factor in the position of the coconut tree at (1,0) or (c,0).

We use the idea of a triangle to help us better understand that the stake will end up at (1-y, x+1) or (c-y, x+c).

Then to find the midpoint of the two points which is just the first position + the second position divided by two.

(y, -x) and (1-y, x+1)

((y - y + 1)/2, (x - x + 1)/2)

(1/2, 1/2)

Hence our answer is (1/2,1/2) - although we'll see that if we had use the constant C for the coconut tree we would have ended up with (c/2, c/2). this is important because even though we laid out the island in our own coordinate system, its not always the case that c must be positive. i think (and i've seen this solution elsewhere, but can't really come up with a repro, so let me know if i'm wrong here) there really are two places the treasure could be because c could also be negative. so if we use our first answer of (1/2,1/2) we must also search at (-1/2, -1/2). if the cannon was in the lower half of the coordinate system you can see that the treasure would actually be in that quadrant also.

27.

There are three ants on a triangle, one at each corner. at a given moment in time, they all set off for a different corner at random. what is the probability that they don't collide?

Consider the triangle ABC. We assume that the ants move towards different corners along the edges of the triangle.

Total no. of movements: 8 A->B, B->C, C->A A->B, B->A, C->A A->B, B->A, C->B A->B, B->C, C->B A->C, B->C, C->A A->C, B->A, C->A A->C, B->A, C->B A->C, B->C, C->B

Non-colliding movements: 2 A->B, B->C, C->A A->C, B->A, C->B

(i.e. the all ants move either in the clockwise or anti-clockwise direction at the same time)

P(not colliding) = 2/8 = 0.25

28.

Problem: how many places are there on the earth that one could walk one mile south, then one mile east, then one mile north and end up in the same spot? to be precise, let's assume the earth is a solid smooth sphere, so oceans and mountains and other such things do not exist. You can start at any point on the sphere and walk in any direction you like. Think you've figured it out? I'll tell you now, there is more than one. in fact, there are more than two. Also be advised that walking north from the North Pole (or south from the South Pole) is illogical and therefore does not enter into the problem. All normal assumptions about directions will be used.

There are no tricks involved with this question. It just forces you to really think about the problem to come up with all the solutions.

Solution:

Well the North Pole is one such place.

Then somewhere near the South Pole such that when you walk one mile south you are at the point on the earth where the circumference is 1. That way when you walk 1 mile east, you end up back at the same point. And of course one mile north from there puts you back where you started. Here is a drawing courtesy of jy. There may or may not be such a

place in the northern hemisphere where walking a mile south puts you at the 1 mile circumference point on the earth.

i'm no geometry sphere expert, so someone will have to let me know if that is physically possible (i.e. i tend to think that if you walk n units south from any point on the northern part of a sphere, other than the north pole, it is impossible for the circumference to be n or less than n, but who knows?)

Finally there are actually an infinite number of points. If we consider the case before where we went to the point with a circumference of 1, why not go to the point with a circumference of 1/2. Then when you go a mile east, you loop around twice, and end up in the same spot. This holds true for 1/3, 1/4, 1/5, ... 1/n, etc.

29.

This is difficult to describe in words, so read this carefully, lest there be any confusion. you have a normal six sided cube. i give you six different colors that you can paint each side of the cube with (one color to each side). how many different cubes can you make?

Different means that the cubes can not be rotated so that they look the same. this is important! if you give me two cubes and i can rotate them so that they appear identical in color, they are the same cube.

Let X be the number of "different" cubes (using the same definition as in the problem). Let Y be the number of ways you can "align" a given cube in space such that one face is pointed north, one is east, one is south, one is west, one is up, and one is down. (We're on the equator.) Then the total number of possibilities is X * Y. Each of these possibilities "looks" different, because if you could take a cube painted one way, and align it a certain way to make it look the same as a differently painted cube aligned a certain way, then those would not really be different cubes. Also note that if you start with an aligned cube and paint it however you want, you will always arrive at one of those X * Y possibilities.

How many ways can you paint a cube that is already "aligned" (as defined above)? You have six options for the north side, five options for the east side, etc. So the total number is 6! (That's six factorial, or 6 * 5 * 4 * 3 * 2 * 1). Note that each way you do it makes the cube "look" different (in the same way the word is used above). So 6! = X * Y.

How many ways can you align a given cube? Choose one face, and point it north; you have six options here. Now choose one to point east. There are only four sides that can point east, because the side opposite the one you chose to point north is already pointing south. There are no further options for alignment, so the total number of ways you can align the cube is 6 * 4.

Remember, Y is defined as the number of ways you can align the cube, so Y = 6 * 4. This gives us 6! = X * 6 * 4, so X = 5 * 3 * 2 * 1 = 30.

30.

I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. i put a hat on each of their heads and told them that one of them must shout out the correct color of their own hat or they will all be drowned by the incoming tide. i give them 10 minutes to do this. Fisherman A and B can only see the sand dune i erected. Fisherman C can see that fisherman B has a white hat on. Fisherman D can see that C has a black hat, and B has a white hat. the fisherman have been told that there are four hats, two white and two black, so they know that they must have either a white or a black hat on. Who shouts out the color of their hat and how do they know?

Fisherman C shouts out.

Fishermen A and B are in the same situation - they have no information to help them determine their hat colour so they can't answer. C and D realise this.

Fisherman D can see both B and C's hats. If B and C had the same colour hat then this would let D know that he must have the other colour.

When the time is nearly up, or maybe before, C realises that D isn't going to answer because he can't. C realises that his hat must be different to B's otherwise D would have answered. C therefore concludes that he has a black hat because he can see B's white one.