ASF Puzzles & Conundrums Thread

[cynic]

It can be done in two complete trips. The first trip requires two switches flipped on and the lights noted. The light that isn't on belongs to the unflipped switch.

The second trip requires that one of the two flipped switches be unflipped.

The remaining light belongs to the flipped switch and the other light (that was previously on) belongs to the recently unflipped switch.

 

[pixel]

It can be done in two complete trips. The first trip requires two switches flipped on and the lights noted. The light that isn't on belongs to the unflipped switch.

The second trip requires that one of the two flipped switches be unflipped.

The remaining light belongs to the flipped switch and the other light (that was previously on) belongs to the recently unflipped switch.

If you want to allow two trips, you can simply flick switch One, climb the stairs at your leisure, mark the light that is burning with a "1". Then go back down, repeat the same with switch Two and lamp "2". No need to test switch Three.

I still prefer Boggo's solution

 

[cynic]

If you want to allow two trips, you can simply flick switch One, climb the stairs at your leisure, mark the light that is burning with a "1". Then go back down, repeat the same with switch Two and lamp "2". No need to test switch Three.
...

Yes - that'd work also.

It'll be interesting to find out if the one trip approach works for those high efficiency globes that barely heat.

 

[bellenuit]

You could turn on two of the switches and allow the lights to warm up, then switch one off and run up the stairs like buggery before the one you had on cooled down.
You should now have one on, one hot and the one that hasn't been switched on would still be cold ???????

Yes, Boggo. That is the answer

This is assuming that you are very fit you could do it in one trip.

It'll be interesting to find out if the one trip approach works for those high efficiency globes that barely heat.

Cynic/Boggo When I first heard the problem, which was phrased differently, I came up with the same answer as Boggo, but thought it had the same potential weakness in that it mightn't work for new style globes. I thought about specifying that they were incandescent globes, but realised that the word "incandescent" would be too big a clue and make the answer obvious. So the whole spiel about the room being locked for 50 years was simply to ensure no one could claim the answer was wrong because modern day globes leave off little heat. The globes are obviously from the 1960s at the latest and I am sure most bedrooms would only have incandescent globes available at that time. Globes from that era hold their heat for at least 10 minutes, but as only a few minutes are needed to climb the stairs, they would still be discernibly warm to the touch. Although fluorescent tubes were around then and are cooler, they still were not as efficient as today's variety and also would be discernibly warm after being off for 2 minutes say. In any case, I specified globes, not tubes, so I think Boggo's answer is without doubt correct.

 

[cynic]

Yes, Boggo. That is the answer

Darn it! Foiled again!!

P.S. Well done Boggo!

 

[bellenuit]

A really hard one this time.

This is a problem I came across years ago. I didn't work it out, but was staggered by the answer (I doubt if beforehand anyone would even guess close to the answer, but it it is purely mathematical and the answer is beyond question). It does require a lot of math, particularly probability theory. I have never been able to remember what the full answer is, but have been able to get a close approximation that is not far off the correct answer. The close approximation is still unbelievable by most people, but when they see the math they cannot dispute it. I will pose it here in the hope that some one can provide the exact solution. It is a simply described problem, but one must pay close attention to the actual wording. There is no trickery involved.

Random numbers between 0 and +infinity are generated by a computer and each is printed on a separate sheet of paper. This is done until several thousand numbers are generated. Each sheet of paper is placed face down on a table (I know, it must be a very big table) in no particular order. The computer also prints out on a separate sheet the highest number it generated. This is for the use of the administrator to check the result.

A brilliant logician is invited into the room and offered this challenge (he is told the number of sheets of paper on the table, which he can count anyway if he wanted to, and that each piece contains a random number between 0 and + infinity): "You are to turn up sheets of paper one at a time and after turning up a sheet and seeing its number you are to declare whether that number is the highest number among all the sheets of paper that are on the table. If you say it isn't you continue on turning. If you say it is, you stop". The question is: what is the probability that the logician will stop at the correct number that is the highest (e.g. corresponds to the number that the administrator was given by the computer).

You can assume that being a brilliant logician he will use a method that maximises his chances of being correct.

As most people often get this part wrong, I will reiterate. He can only declare the number he has just turned to be the highest and stop. He cannot say, for instance, that a piece of paper he turned earlier is the highest. If he thinks an earlier number is the highest, then it is too late and that attempt is seen as a failure.

 

[trainspotter]

Wan't this one done in November 2009? I have a very faint memory of wolframalpha being involved??

 

[keithj]

You can assume that being a brilliant logician he will use a method that maximises his chances of being correct.

The method a logician would use to find the highest number is

• work out the probability of the location of the 2nd highest number
• turn over that many papers & remember the highest number found so far
• finally turn over more papers until he finds one higher & declares it the highest.

I didn't use any maths or probability theory to arrive at this figures. I generated 4000 bits of paper with a random number on it, and asked my PC to try the method 1,000,000 times.

My PC seemed to think that on average the 2nd highest number would be found somewhere in the first 18.7% of the bits of paper.

It doesn't matter what the highest number is (infinity isn't an issue) - the only thing that matters is that after around 18.7% of the bits of paper have been sighted he can expect to have seen the 2nd highest.

And therefore if any subsequent number seen that is higher is likely to be the highest.



And the 2nd part of the question is what is the probability he is right.....

My PC checked 1,000,000 times to see how many times the highest number of all the bits of paper was not in the 1st 18.7%.

If he uses this method, my PC reckons he has a probability of around 72.5% chance of getting it right.

 

[bellenuit]

Wan't this one done in November 2009? I have a very faint memory of wolframalpha being involved??

Yes, I remember posting it before, but I don't recall where or if it was on ASF. I have yet to find the full solution other than approximations, so I was hoping some new minds working on it might prove fruitful.

 

[bellenuit]

The method a logician would use to find the highest number is

• work out the probability of the location of the 2nd highest number
• turn over that many papers & remember the highest number found so far
• finally turn over more papers until he finds one higher & declares it the highest.

I didn't use any maths or probability theory to arrive at this figures. I generated 4000 bits of paper with a random number on it, and asked my PC to try the method 1,000,000 times.

My PC seemed to think that on average the 2nd highest number would be found somewhere in the first 18.7% of the bits of paper.

It doesn't matter what the highest number is (infinity isn't an issue) - the only thing that matters is that after around 18.7% of the bits of paper have been sighted he can expect to have seen the 2nd highest.

And therefore if any subsequent number seen that is higher is likely to be the highest.



And the 2nd part of the question is what is the probability he is right.....

My PC checked 1,000,000 times to see how many times the highest number of all the bits of paper was not in the 1st 18.7%.

If he uses this method, my PC reckons he has a probability of around 72.5% chance of getting it right.

You are on the right track, but I see some errors already.

My PC seemed to think that on average the 2nd highest number would be found somewhere in the first 18.7% of the bits of paper.

Try a Mac instead. Surely basic probability would indicate that the on average the 2nd highest number would be found somewhere in the first 50%?

 

[cynic]

You are on the right track, but I see some errors already.

My PC seemed to think that on average the 2nd highest number would be found somewhere in the first 18.7% of the bits of paper.

Try a Mac instead. Surely basic probability would indicate that the on average the 2nd highest number would be found somewhere in the first 50%?

Also the highest number would surely have an equal chance of falling in the first 50%.

 

[cynic]

I haven't tested my approach with the maths yet, but at a glance I suspect that the presence of positive infinity will obfuscate the practical reality.

So for the moment I'll give my quick and dirty answer to how I'd approach the situation.

I'd sequentially turn over the first floor(N/2) papers. (I would only stop if I found positive infinity!)

Upon having examined the first half and noting the highest number, I'd then sequentially turn over the [N-floor(N/2)] papers until I found a new highest number and then stop.

There's a 50% chance that the highest number wouldn't already have been turned over (in the first half) which means there's a 50% chance that there are one or more larger numbers in the residual half.

My chance of being wrong would be 0.5 + sum[(probabilities > 1 higher numbers in second half)X(probability highest appearing later than first higher)].

 

[cynic]

It just occurred to me that, following on from my earlier logic, the second half would then be viewable in the same context as the first. (i.e. that there is a highest number that could just as easily fall within either the first or second half of the residual half.)

The perpetuation of such logic might easily result in turning over every card in the expectation that the last will ultimately be the highest!

 

[keithj]

He should turn over a sample set of 37% of the papers & note the highest number.

There is then (coincidentally) a 37% chance that the next paper he turns over that has a higher number on it will be the highest in the whole set.

By using a sample size of 37% of the papers, this balances the probability of actual highest number NOT being in that sample & also that the sample contains a sufficiently high number (not necessarily the 2nd highest) to exclude all but the highest in the remainder

And additionally the probability of any numbers higher than the highest in the sample set, but not the actual highest that are (fortunately) NOT turned over from the remaining papers.



However, still using brute force & a PC....

 

[bellenuit]

He should turn over a sample set of 37% of the papers & note the highest number.

There is then (coincidentally) a 37% chance that the next paper he turns over that has a higher number on it will be the highest in the whole set.

By using a sample size of 37% of the papers, this balances the probability of actual highest number NOT being in that sample & also that the sample contains a sufficiently high number (not necessarily the 2nd highest) to exclude all but the highest in the remainder

And additionally the probability of any numbers higher than the highest in the sample set, but not the actual highest that are (fortunately) NOT turned over from the remaining papers.



However, still using brute force & a PC....

Yes. Close enough to the optimum. He turns over the first 1/e pieces of paper, where e is the natural number e=2.718 approx, and notes the highest number among them. He then starts turning the remaining pieces of paper and stops at the first that is higher. The actual probability of that being the highest of all pieces of paper is also 1/e.

1/e = 36.787%

I usually explain it using 1/3 rather than 1/e as it gets the principle across (most would assume that the chances are close to zero) and is close enough to the optimum result anyway.

Using 1/3 as the ratio representing the number that are turned up first (that is why the logician must know the total number of pieces of paper) you get something like this.

What is the probability that the 2nd highest number is in the first 1/3, but the highest is not (because if this happens his method will cause him to stop on the highest). This probability is:

1/3 * 2/3 = 2/9 or 22.2%

But that is just one way that method would yield a win. It would also yield a win if the 3rd highest number is in the first 1/3, the 1st and 2nd highest are not in the first third and he turns the highest before the 2nd highest. The probability of that happening is:

1/3 * 2/3 * 2/3 * 1/2 = 4/54 or 7.4%

Since these are mutually exclusive events, and since both would yield a win, you can add the answers together and we now are at 29.6% probability.

You could still go on with additional mutually exclusive events that increase the final answer. The next one would be the probability that the 4th highest is in the first 1/3, the 1st, 2nd and 3rd highest are not in the first 1/3, and he turns the highest before he turns the 2nd or 3rd highest. The probability of that is:

1/3 * 2/3 * 2/3 * 2/3 * 1/3 =8/243 or 3.3%

The total is now at 32.9%.

So without too much math, it is easy enough to explain how rather than being an impossible task, the logician has about a 1 in 3 chance of being right. The interesting thing is once the optimum method is worked out, the actual process of stoping at the highest number is purely mechanical and doesn't take any thinking.

As I mentioned, the optimum ratio is 1/e and the math to work that out is beyond me. But I have discovered that this problem is on Wikipedia (called the Secretary Problem) and all is explained there for those interested.

http://en.wikipedia.org/wiki/Secretary_problem

 

[cynic]

...As I mentioned, the optimum ratio is 1/e and the math to work that out is beyond me. But I have discovered that this problem is on Wikipedia (called the Secretary Problem) and all is explained there for those interested.

http://en.wikipedia.org/wiki/Secretary_problem

After looking at that article, I'm pretty sure that 1/e is an approximation. The optimal ratio will approach 1/e as n (the total number of papers) approaches infinity.

The probability sum is essentially a real multiple of the difference between two harmonic numbers. This explains the relationship to e and the reason why the approximation can be expected to become increasingly accurate as n approaches infinity.

 

[trainspotter]

Yes, I remember posting it before, but I don't recall where or if it was on ASF. I have yet to find the full solution other than approximations, so I was hoping some new minds working on it might prove fruitful.

16th November 2009 you wrote this in ASF (took me a while to find it )

The Random Number Generator - One of the best Maths problems ever IMO

People seem to be now on the right track, so I will give the solution as best as I can. brty was close to the mark when he/she posted "By waiting until the first 500 numbers have been drawn,and then putting your name to the first number that is higher than any in the first 500, should give a probability of 1 in 4 of being correct" That is the strategy, but the number to pass over is not the optimum. 2020 was closer when he/she said " my gut feel is that it is about the 33% mark, that you turn up 333 of them, then continue until (as others have said) you get a bigger number than all the numbers to date = the biggest in the upturned pack".

As I mentioned at the very beginning you can get an approximate answer with very basic probability theory, but to get the exact answer requires a better knowledge of maths than I have. In fact my maths has improved enormously over the last day or so when I started using the Wolfram Alpha computational engine, but more about that below.

If you don't want to get deeply into the maths, you can derive the optimum fraction to use by evaluating for easy fractions like 1/5, 1/4, 1/3, 1/2 etc. and seeing which if these gives the greatest chance of being right. If you do this, you will find that 1/3 gives the greatest chance. Later I will show how to work out the optimum fraction using more advanced mathematics.

So your strategy is to answer No to the first 333 numbers generated (noting the highest number among these) and then say Yes to the first number (if any) that is higher than this. This will give you the greatest chance of success. This is how you work out the probability of being right....

This strategy will give you the correct answer if the 2nd highest number is in the first third (1/3 chance) AND the highest number is not in the first third (2/3 chance). Thus you will be correct 2/9 or 22% of the time (at least).

But it will also give you the correct answer if the 3rd highest number is in the first third (1/3 chance) AND the highest and second highest numbers are not in the first third (2/3 X 2/3 chance) AND the highest number comes up before the second highest number (1/2 chance). This comes to 2/27 or 0.074 or 7.4%. Since this is a mutually exclusive result to the first, both are potential outcomes, so the chances of either happening are 29.4%.

You would also be successful if the 4th highest number is in the first third (1/3) AND the first, second and third highest are not in the first third (2/3 X 2/3 X2/3) AND the highest number is generated before the second or third highest (1/3). This is 8/243 or .033 or 3.3%. Again, as this is a mutually exclusive result, the chances of any one of these three outcomes occurring, which would give the correct result, are now up to 32.7%.

So this is almost a one in three chance, but it will increase slightly more each time you evaluate and include additional possible successful outcomes. The 667th term will be the highest you can go and this will be when the 667th highest number is in the first third AND all 666 higher numbers are not in the first 1/3 AND the highest number comes before the other 665. However, evaluating beyond a few terms is pointless, as each additional term adds proportionally less and less to the final result.

So as an approximation, the chances of success using this strategy is about 1 in 3.

Now for the heavy stuff. If any of you are not aware of the computational engine Wolfram Alpha, I urge you to go to the website http://www.wolframalpha.com/ and play around with it. It will blow your mind when you see its capabilities. There is an introductory video there that is worth watching. I will be using that website in this section.

In the advanced solution instead of using 1/3 as the fraction to turn, you need to first determine what actual fraction will yield the highest chances of success. 1/3 is close, but not the optimum fraction.

Lets say this fraction is n, where n is between 0 and 1.

So following the above basic probability logic, using the same strategy, but this time using n rather than 1/3, we get:

This strategy will give you the correct answer if the 2nd highest number is in the first n of the generated numbers (n chance) AND the highest number is not in the first n of the generated numbers (1-n chance). Thus your chance of success is n(1-n) at least.

But it will also give you the correct answer if the 3rd highest number is in the first n of the generated numbers (n chance) AND the highest and second highest numbers are not in the first n of the generated numbers ((1-n)(1-n)) AND the highest number comes up before the second highest number (1/2). The chance of this happening is 1/2*n*(1-n)^2. Since this is a mutually exclusive result to the first, both are potential outcomes, so the chances of either happening are n(1-n) + 1/2*n*(1-n)^2.

You would also be successful if the 4th highest number is in the first n of the generated numbers (n chance) AND the first, second and third highest are not in the first n of the generated numbers ((1-n)(1-n)(1-n)) AND the highest number is generated before the second or third highest (1/3). This is 1/3*n*(1-n)^3. Again, as this is a mutually exclusive result, the chances of any one of these three outcomes occurring, each of which would each give the correct result, are now n(1-n) + 1/2*n*(1-n)^2 + 1/3*n*(1-n)^3.

This can be continued on by evaluating for the 5th and subsequent highest numbers in a similar fashion, increasing the accuracy of your answer each time. It should be apparent that including the (x+1)th highest number in the evaluation will add 1/x*n*(1-n)^x to the result for your chances of success. As the highest term you can evaluate to is the 1000*(1-n)th highest number, the complete formula for the probability of success is:

sum of 1/x*n*(1-n)^x for x =1 to 1000*(1-n)

So what we want to now do is find what value of n gives the highest value to that formula.

The days when I could work that out are long behind me, but we can use Wolfram Alpha to help us.

Remember each additional term adds proportionally less and less to the accuracy of the answer so lets try firstly just for three terms (e.g. that the 4th highest number is in the first n etc. as described above). So we want Wolfram Alpha to evaluate this formula

global maximum sum(1/x*n*(1-n)^x) for x = 1 to 3

So copy this line in its entirety (including the words global maximum) and paste it into the search field at www.wolframalpha.com and then hit enter or press the = sign. Wait a few seconds for the results to be calculated. There will be a section called Global Maximum. If it shows "approximate form" at the top right of that section, click on that term and it should show "exact form" You will get the formula expanded out into individual terms and then to the right of it, it shows:

0.341572 at n~~0.422862

What that is saying is that formula is at its maximum when n is approximately 0.422862 and it evaluates to 0.341572 when n has that value. In other words, if we calculate to just 3 terms, the optimum number of random numbers to let pass is 422 (instead of 333 using the 1/3 approach), and the chance of success will be 34%.

Now lets make Wolfram Alpha really work and change the 3 in the formula to 199 so it reads "for x = 1 to 199". So we are trying to get really accurate by evaluating to 199 terms. The result under global maximum is so big, you will need to scroll down to see the result which this time shows:

0.367879 at n~~0.367861

If you try to go higher than 199, Wolfram Alpha usually gives up, so this is as close to the optimum as we can get using that tool. In fact the optimum would be only ever so slightly different and would be:

0.367879 at n~~0.367879

Both the optimum fraction to use to maximise the chances of success and the probability of success at that optimum value are the same.

For those of you still awake, this fraction just happens to be 1/e, e being the natural number e. Now, ain't that interesting.

So what the final result is saying is that to maximise the chance of success, say No to the first 367 numbers (but note the highest of them). Then answer Yes to the first number that is higher than the number noted. If you follow that strategy, your chance of identifying the highest number overall (of the 1000 generated) is 36.7%.

*whew* for a second there I thought my memory was going !!

 

[bellenuit]

16th November 2009 you wrote this in ASF (took me a while to find it )

The Random Number Generator - One of the best Maths problems ever IMO



*whew* for a second there I thought my memory was going !!

What thread was that? I thought I might have posted it on ASF before, but the only puzzle thread I could find was this one and it wasn't here.

Seeing the answer is fully explained in Wiki, it will be hard to post any of the classic puzzles without someone being able to look up the answer. You would certainly have to call them by a different name to what the original was called and change the narrative a bit.

 

[cynic]

What thread was that? I thought I might have posted it on ASF before, but the only puzzle thread I could find was this one and it wasn't here.

Seeing the answer is fully explained in Wiki, it will be hard to post any of the classic puzzles without someone being able to look up the answer. You would certainly have to call them by a different name to what the original was called and change the narrative a bit.

Yes! What's happening seems analogous to people relying upon calculators instead of learning their times tables.

Your postings to this thread have attracted much interest from some of the logically and mathematically inclined members of this forum.

Perhaps some of us could invent puzzles of our own and post them here.

 

[barney]

Your postings to this thread have attracted much interest from some of the logically and mathematically inclined members of this forum.

Yeah its a good fun thread ..... although I'm still not convinced about the brown and blue eyed Slaves. My logic behind not being convinced is thus ....

If the Captain of the boat had lined the 3 Slaves up (facing away from him of course) and asked them all (both separately and/or collectively) ..... Do all the Slaves on this Island have brown eyes, they would have all said NO. Even if they heard each others answer, what does that teach them that they didn't already know? I don't see why a third party saying NO gives any added info, but I am quite prepared to admit my brain is simply not up to the "twist"

Here is a simple one to start the week. I just got it off the net so hopefully a few haven't seen it. PS. If it looks too easy, try it after 3 beers!

At a recent downhill mountain bike race, four entrants entered the challenging slalom event.


Alan came first.

The entrant wearing number 2 wore red, whereas John didn't wear yellow.

The loser wore blue and Steve wore number 1.

Kev beat Steve and the person who came second wore number 3.

The entrant in yellow beat the entrant in green.

Only one of the entrants wore the same number as their final position.


Can you determine who finished where, the number and colour they wore?