PDA

View Full Version : Recreational Mathematics



Pages : [1] 2 3 4

Rincewind
07-01-2004, 11:45 AM
I've tried to extricate this thread from the gambling on the Results of the Aussie Champs thread. It began (as most thread do) with a slinging match between Bill and Matt. But I'll start reproducing posts from the part where I got involved...


Question:
A bag contains an unknown number of marbles >1.
Each marble is either black or white.
You draw out one marble, it is white and you put it in your pocket.
What colour is most likely to be pulled out in the next draw, and why?


The correct answer to this is that you have insufficent information to answer the question. All you know is that your chance of drawing a white marble has decreased and your chance of drawing a black marble has increased (provided the number of marbles in the bag is finite). But without knowing the initial mix and number of marbles you can't say either colour is more likely than another.

Here are two possible answers based on an unprovided assumption which lead to opposite answers.

Assumption 1: The initial mix of black to white was 1:1

Answer 1: Black is now more likely as there are now 1 more black marble than white. However the change in probability is inversely proportional to the initial number of marbles in the bag.

Assumption 2: The initial mix of black to white was significantly different from 1:1 and there were a reasonably large number of marbles in the bag.

Answer 2: White was pulled out first so it is more likely that there were more white than black. Due to the large number of marble the non-replacement has not affected probablilities too greatly and therefore White is again the more likely result.

However, neither answer is correct unless the assumptions are accepted.


To illustrate the point for you here are some questions which have answers.

1. You have a bag with black and white marbles, 12 of one colour and 8 of the other. A marble is drawn at random (it happens to be white) and put into your pocket. Is it now more likely that the next marble drawn will be black or white? (4 points)

2. Provide the probability to 4 decimal places. (2 points)





Almost true. We can always answer. I practical terms. the answer is "a white marble". However, your arguments and examples are 100% correct! I concur fully with you. We must make some assumptions.

I put it to you that practically, the bag it not of infinite size. Further that the proportion of white to black is unknown, and thus in practical terms normally distributed unless otherwise known. Therfore, of all the possible actual black and actual white marbles in the bag there are proportional very few that have B=W. This means that the number of balck and white are nearly always unequil. Now we can say, as you have already explained, that what ever draw out first is the best prediction for the second marble's colour.


Not so. We can answer or we can guess. When assuming you are making a guess as to what is reasonable. You cannot say what the probability of your guess being correct is. You may as well flip a coin.

Here you are making some additional assumptions as to the likely distribution of marbles. Furthermore, your logic is flawed. The reliability of the "same again" strategy is improved the more biased the sample of marbles and the greater the number of marbles, however, the first rule of Probability is do not trust your intuition.

BTW did you have a crack at my question? (hint)

Marbles are distributed 12/8, does the "same again" strategy perform better or worse than the "opposite" strategy?

There was an attempted solution submitted by Matt at this point but he clearly understood I was giving the distribution as Black:12, White:8 whereas I didn't intend this to be inferred from the way the questoin was worded. Anyway a second solution was submitted...


#1. The most likely colour of the second marble is white.

#2. There are 4 possible outcomes for the two marble draw without replacement:
Majority marble, Majority marble
Majority marble, Minority marble
Minority marble, Majority marble
Minority marble, Minority marble

The probablity of these are :
12/20 x 11/19 = 0.3474
12/20 x 8/19 = 0.2526
8/20 x 12/19 = 0.2526
8/20 x 7/19 = 0.1474
SUM =1=P

The P of a Major coming out second is
(12/20 x 11/20) + (8/20 x 12/19) = 0.6000

The P of a Minor coming out is
1 - P(Maj) = 1 - 0.6000 = 0.4000

The first marble drawn was White,
and the P of drawing a Maj in the first draw is 12/20 = 0.6000,
hense the P of White being the Maj is also 0.6000.

It has been shown that that the porobabilty of drawing a Maj in the second draw is also 0.6. In deed, in the absence of information of what has already been draw, the P of drawing a Maj in any/every draw is always 0.6

Therefore the chance of the second marble being White is also 0.6000

Sorry Barry, your flipped coin and going against your instinct means the laser fitted sharks have just made yum cha of your girlfriend. :evil: :twisted:


Actually your score is

Q1 - 0 points - harsh but fair, the correct answer is Black

Q2 - 1 point - generous but some of your working is right, although your logic is confused.

1/6 is not a good start but don't lose heart, there will be future assignment with which you can earn credits prior to exam day.


The correct solution is as follows.

The colour of the marbles is largely irrelevant as we don't know if white or black is the majority. The easiest thing to do is to calculate the probablity of the second marble being the same colour as the first marble.

That is Maj then Maj, or Min then Min.

The probability (P1) is 12/20 * 11/19 + 8/20 * 7/19 = (132 + 56)/380 = 188/380

For completeness, possibilities for differing colours are Maj then Min or Min then Maj

The probability (P2) is 12/20 * 8/19 + 8/20 * 12/19 = (96 + 96)/380 = 192/380

NB: P1 + P2 = 1

NMB: P1 < P2

So the most likely result (although only ever so slightly) is that second marble will differ in colour from the first. The first was White, therefore the second will most likely be Black.

The correct answers are

Q1. It is more likely that the second marble will be Black

Q2. Black (P2) = 192/380 ~ 0.5053
White (P1) = 188/380 ~ 0.4947

Feel free to asks questions, but next time you're working on a probability problem, don't forget to check your intuition in at the cloak room as it usually leads one astray. ;)

If you don't believe me do a web search on the "Monty Hall Problem". That one is a beauty.


I did this independently and got exactly the same answer as Barry, though I wouldn't have explained it as well as he did. Very neat example indeed. :D


Thanks, as an footnote, the inequality that is satisfied for differing colours to be more likely that same colours is quite neat. Here it is...

(x1 - x2) ^ 2 < (x1 + x2)

where x1 and x2 are the numbers of marbles of each colour.

Or to express in words, the second marble is more likely to differ in colour from the first when the square of the difference in number of the marbles of each colour is less than the total number of marbles.

In this example x1 = 12, x2 = 8

RHS = 12 + 8 = 20 (total number of marbles)

LHS = (12 - 8 ) ^ 2 = 4 ^ 2 = 16 (square of the difference (in this case 4))

Anyway, LHS is less than RHS in this example so different marbles rule. ;)

Kevin, if you haven't already you might like to derive this inequality to see if I have this right.


That is a really tough marking system :shock: . I would have though maybe 3/6 . 2 for using a matrix, 2 for calculating their probabilities, -2 for logic error, 0 for answer, bonus 1 for showing that all draws have exactly the same chance of a Maj being picked.

Yes, I can see how I made it hard for myself, and picked the wrong matrix pair. I like how your more eligant approach did not lead to the logical complexities that I stuffed up. :D That Monty Hall Problem is a cracker. You bloody professional mathamaticians come up with fabulous ways to fool people.

However, you still have yet to say why you picked Black as the second colour in the absence of sufficient information. ;)

You could reasonably assume the ratio of Maj to Min is normaly distributed. Futhermore, you might assume that estimates of the number of marbles on the bag would have an asymetric distribution. Putting those equations and your personbal estimate of the number of marbles, together with the inequality you gave {(x1 - x2) ^ 2 < (x1 + x2)} you might have found the solution, while your girlfriend was dangling - but I doubt it. So why did you pick black.

Rincewind
07-01-2004, 12:15 PM
That is a really tough marking system :shock: . I would have though maybe 3/6 . 2 for using a matrix, 2 for calculating their probabilities, -2 for logic error, 0 for answer, bonus 1 for showing that all draws have exactly the same chance of a Maj being picked.

I think I said "Harsh but fair". 4 points for a true/false question which you have a 50% chance of guess. The calculation of the exact probability was 2 marks and you scored 50% in that department.

The result regarding a maj marble being drawn on the second time is intersting but was not asked.


Yes, I can see how I made it hard for myself, and picked the wrong matrix pair. I like how your more eligant approach did not lead to the logical complexities that I stuffed up. :D That Monty Hall Problem is a cracker. You bloody professional mathamaticians come up with fabulous ways to fool people.

It is an interesting problem because at the heart of the disagreements on the correct solution is really, "what can be reasonably assumed?"


However, you still have yet to say why you picked Black as the second colour in the absence of sufficient information. ;)

I didn't say I'd pick black. I said I would mentally toss a coin and go the opposite to my original guess. But really, if the number of marbles could be reasonably guessed at based on sensory cues and the the distribution could be assumed to be almost normal (within the contraint of the bag containing at least 1 marble of each colour), then a maximising strategy could theortically be worked out based on the colour of the first marble. My example shows however, that the strategy would need to be worked out and not guessed at as intuition leads you astray as often as not. Also, be aware that the Dr Evil is a sick dude and any distribution he concocts is unlikely to be "normal".


You could reasonably assume the ratio of Maj to Min is normaly distributed. Futhermore, you might assume that estimates of the number of marbles on the bag would have an asymetric distribution. Putting those equations and your personbal estimate of the number of marbles, together with the inequality you gave {(x1 - x2) ^ 2 < (x1 + x2)} you might have found the solution, while your girlfriend was dangling - but I doubt it. So why did you pick black.

You are self-contradictory here, if you exclude symetric distributions then you are not talking about anything like a normal distribution. Also you said the bag does contain at least 1 marble of each colour so again normal distribution does not strictly apply. But I have another problem for you. This one is worth 8 marks so if you get it 75% correct you can redeem yourself to a pass mark. ;)

Q3

Dr Evil has a marble making machine which randomly produces a black or white marble with equal probability. He uses this machine to fill a bag with 20 marbles. If at the end of the process the bag contains only one colour of marble then the marbles are emptied into the crack of Mt Doom and he begins the process again.

A bag which has been prepared in this way is presented to you and you draw a marble from the bag, it is White.

(a)
What colour marble is most likely to be drawn from the bag next? (2 marks)

(b) What is the probability that the next marble drawn from the bag will be White? (Show answer as a fraction and approximate to 8 decimal places) (6 marks)

Have fun.

Anyone can submit a solution to me my Private Message. If I don't hear from Matt with a solution within one week, a solution and results for other posters (if any) will be posted.

Kevin Bonham
07-01-2004, 01:49 PM
That is a really tough marking system :shock: . I would have though maybe 3/6 . 2 for using a matrix, 2 for calculating their probabilities, -2 for logic error, 0 for answer, bonus 1 for showing that all draws have exactly the same chance of a Maj being picked.

You really expect 1 point for something as obvious as that? :(

Looking forward to your solution to Q3 Matt, after your doubting-Thomas effort towards my (admittedly fading) maths ability on the other thread. I reckon I can get this one without too much trouble and I doubt that I'll be the only one.

PHAT
07-01-2004, 02:36 PM
I think I said "Harsh but fair". 4 points for a true/false question which you have a 50% chance of guess. The calculation of the exact probability was 2 marks and you scored 50% in that department.

The result regarding a maj marble being drawn on the second time is intersting but was not asked.

Hmmm. I will let it rest with this comment: How many exams have you done where T/F questions were worth 4 marks while the interpretation and calculation questions were worth 2 marks? [one raised eyebrow]


However, you still have yet to say why you picked Black as the second colour in the absence of sufficient information. ;)


I didn't say I'd pick black. I said I would mentally toss a coin and go the opposite to my original guess. But really, if the number of marbles could be reasonably guessed at based on sensory cues and the the distribution could be assumed to be almost normal (within the contraint of the bag containing at least 1 marble of each colour), then a maximising strategy could theortically be worked out based on the colour of the first marble. yes

My example shows however, that the strategy would need to be worked out and not guessed at as intuition leads you astray as often as not. Also, be aware that the Dr Evil is a sick dude and any distribution he concocts is unlikely to be "normal".
Dr Evil would want the highest execusion rate. So, he would assume that most people would pick what I did - same colour. Therefore Dr Evil's best stratergy would be to give a bag with an even number of colours.


You could reasonably assume the ratio of Maj to Min is normaly distributed. Futhermore, you might assume that estimates of the number of marbles on the bag would have an asymetric distribution. Putting those equations and your personbal estimate of the number of marbles, together with the inequality you gave {(x1 - x2) ^ 2 < (x1 + x2)} you might have found the solution, while your girlfriend was dangling - but I doubt it. So why did you pick black.


You are self-contradictory here, if you exclude symetric distributions then you are not talking about anything like a normal distribution. I should have explained further, that the asymetric distribution of the marble number guess is due to the fact that you cannot guess a -ve number of marbles. However. we could assume a distribution that approximates a normal.


Q3

Dr Evil has a marble making machine which randomly produces a black or white marble with equal probability. He uses this machine to fill a bag with 20 marbles. If at the end of the process the bag contains only one colour of marble then the marbles are emptied into the crack of Mt Doom and he begins the process again.

A bag which has been prepared in this way is presented to you and you draw a marble from the bag, it is White.

(a)
What colour marble is most likely to be drawn from the bag next? (2 marks)

(b) What is the probability that the next marble drawn from the bag will be White? (Show answer as a fraction and approximate to 8 decimal places) (6 marks)

Have fun.

Anyone can submit a solution to me my Private Message. If I don't hear from Matt with a solution within one week, a solution and results for other posters (if any) will be posted.

I'll have a think about it. and post later. But for now, I will guess
(a) second marble will be black (after the white first)
(b) 0.50000001

Rincewind
07-01-2004, 03:30 PM
Hmmm. I will let it rest with this comment: How many exams have you done where T/F questions were worth 4 marks while the interpretation and calculation questions were worth 2 marks? [one raised eyebrow]

You can't claim my marking to be draconian when you had my love interest dangling over a pool of enraged sea-bass.


Dr Evil would want the highest execusion rate. So, he would assume that most people would pick what I did - same colour. Therefore Dr Evil's best stratergy would be to give a bag with an even number of colours.

Often in Bridge you have to make decisions of ways of playing a hand based on the likely distribution of a suit between two hands. It is somewhat akin to the marbles of two colours problem. Usually it is the wild distributions (say 4-1 or 5-0) that cause problems as they can cause the declarer to lose trump control or allow the opponents to quickly set up a number of tricks at no-trumps. However, sometimes the ONLY way to make a contract is to assume the distribution is wild, when it actually turns out that way, it makes all the points you've given away in undertricks in the past just melt away. :)

Anyway, Dr Evil's best strategy is probably to not know the distribution himself. That way it prevents him from telegraphing the distribution via mannerisms, etc. Good bridge players (a class of which I am not a member, BTW) are masters of studying mannerisms for just such information.


I should have explained further, that the asymetric distribution of the marble number guess is due to the fact that you cannot guess a -ve number of marbles. However. we could assume a distribution that approximates a normal.

Does my marble making machine in Q3 sufficiently approximate a normal distribution for you?


I'll have a think about it. and post later. But for now, I will guess
(a) second marble will be black (after the white first)
(b) 0.50000001

If you're still guessing my efforts to educate you in the 1st law of probabilty have failed. ;)

Interestingly, you are going to the colour different strategy now after introducing the pseudo-normal distribution factor. I thought you intuited that this would reinforce the same again strategy.

Regarding part (b), don't forget to provide the answer in fractions. Part marks will be given for wrong answers with partially correct method so it would help to supply as much working as you need to prove your answer.

Also I note you're answer for (a) and (b) are contradicting. Your answer for (b) is supposed to be the probability of the next marble being White. You gave an answer of Black in (a) but a > 0.5 probability for White in (b).

You might also want to submit your answer by PM and I post a solution message after one week. That way anyone else who wants to respond would get the chance. I don't know how many people interested in recreational mathematics we're going to find. But the problems might have an entertainment value to some, so perhaps that would be best.

Cat
07-01-2004, 08:28 PM
There is probably some biological advantage in being able to predict our immediate futures. Part of what forms intuition is accumulated subconscious knowledge and possessing certain intellectual atributes enabling application of that knowledge.

Rincewind
07-01-2004, 11:24 PM
There is probably some biological advantage in being able to predict our immediate futures. Part of what forms intuition is accumulated subconscious knowledge and possessing certain intellectual atributes enabling application of that knowledge.

Yes but go into any leagues club any night of the week and you will see scores of people doing nothing but feed machines their hard earned lolly with a very short memory with regardintuiting their prospect of turning a profit.

What is the selective advantage of wishful thinking?

PHAT
08-01-2004, 09:38 AM
Yes but go into any leagues club any night of the week and you will see scores of people doing nothing but feed machines their hard earned lolly with a very short memory with regardintuiting their prospect of turning a profit.

What is the selective advantage of wishful thinking?

There is the psychology of random reinforcemnt. Scumbags use pokies, which use this psychology, to sucker the punters.

A great example of the poewer of random reinforcement is an experiment done with rats a few decades ago. (You cannot repeat it nowadays becuase of animal ethics legislation.) A rats placed in a watertank with no way out wil drown in about a day - they "appear" to just give up swimming. If a rat is rescued just before it drowns, it experiances a positive reinforcement to swim. If the rescued rat is later watertanked a second time, it will swim for many days until it fails physiologically, not psychologically.

From this, we might theorise,then, that there is a survival advantage for neural networks, to remember any fortuitous event and act on it, even if it is a sample of one.

Intuative probability is very much a product of this advantagous servival stratergy. It is only in "artificial" instances - ie. complex man made senarios - that hard nosed mathematical statistics can be used to show that intuition is correct when it is correct and incorrect when it is incorrect.:P

Take three chess palyers: a 100% tactical player; a 100% intuative player; and a 50/50 player. All other influences being eqil. which one will have the lowest rating?

Rincewind
08-01-2004, 04:45 PM
A great example of the poewer of random reinforcement is an experiment done with rats a few decades ago. (You cannot repeat it nowadays becuase of animal ethics legislation.)

Not in any conventional university, at least. Cox University has no Ethical Review Committee. :twisted:


A rats placed in a watertank with no way out wil drown in about a day - they "appear" to just give up swimming. If a rat is rescued just before it drowns, it experiances a positive reinforcement to swim. If the rescued rat is later watertanked a second time, it will swim for many days until it fails physiologically, not psychologically.

This is sick, even for CU. I remember hearing about a similar experiment involving feeding birds (perhaps pidgeons) where the pigeons developed all sort of perculiar behaviour as this was randomly reinforced with irregular feeding times.


Intuative probability is very much a product of this advantagous servival stratergy. It is only in "artificial" instances - ie. complex man made senarios - that hard nosed mathematical statistics can be used to show that intuition is correct when it is correct and incorrect when it is incorrect.:P

If intuition can be shown to be unreliable in controlled conditions doesn't mean it is useless. Just not as accurate as mathematical analysis. However, several factors may make mathematical analysis inappropriate to certain situations.


Take three chess palyers: a 100% tactical player; a 100% intuative player; and a 50/50 player. All other influences being eqil. which one will have the lowest rating?


The lowest rated player will be the 100% intuitive one. I don't know why it just feels right.

Rincewind
09-01-2004, 12:25 PM
No solutions received so far. So the prize for first correct answer is still available. ;)

Anyway, on the advise of a friend I've reworded the question slightly, it doesn't change my intended meaning, but it might make it a bit clearer. Here it is in full, changes italicised...

Q3

Dr Evil has a marble making machine which randomly produces a black or white marble with equal probability. He uses this machine to fill a bag with 20 marbles. If at the end of the process the bag contains only marbles of one colour then all the marbles are emptied into the crack of Mt Doom and he begins the process again.

A bag which has been prepared in this way is presented to you and you draw a marble at random from the bag, it happens to be White.

(a)
What colour marble is most likely to be drawn from the bag next? (2 marks)

(b) What is the probability that the next marble drawn from the bag will be White? (Show answer as a fraction and approximate to 8 decimal places) (6 marks)

ursogr8
09-01-2004, 12:38 PM
No solutions received so far. So the prize for first correct answer is still available. ;)



hi Barry
Good luck with finding posters who will have a try at this.
If I submitted answers I would have an expectation of 1 mark out of 8.
Can you describe my answers and how I got them?
starter

Rincewind
09-01-2004, 02:55 PM
Good luck with finding posters who will have a try at this.

Hope is the last thing to go.


If I submitted answers I would have an expectation of 1 mark out of 8.
Can you describe my answers and how I got them?

Would the first step entail inventing a machine that makes marbles? ;)

PHAT
09-01-2004, 04:02 PM
No solutions received so far. So the prize for first correct answer is still available. ;)


OK I'll send something in ten minutes.

Kevin Bonham
09-01-2004, 04:59 PM
I believe I've got the method but I'm just crunching all the numbers. There are probably many shortcuts I am missing that are making this more painful than it needs to be.

Rincewind
09-01-2004, 05:20 PM
OK I'll send something in ten minutes.

Got it, thanks.


I believe I've got the method but I'm just crunching all the numbers. There are probably many shortcuts I am missing that are making this more painful than it needs to be.

I didn't say it was going to be easy. ;)

In fact I bounced it off a friend of mine who has a BMath(Comp Sci) he got it wrong through misinterpreting the question, or selecting the wrong method, or a combination of the two. So it is not a dead easy problem.

I'm looking into a proof that says something about the the behaviour of P(n) for all n > 1. I have it at the conjecture phase so far. :( But I'm pretty confident the conjecture is right. :P Hopefully, I'll have it ready to publish with the solution.

Kevin Bonham
09-01-2004, 07:15 PM
Hi Barry, I've just sent you two solutions reaching the same result by very different methods. I'll drop onlookers a subtle hint about the general solution. Dr Evil will be carrying a very heavy bag.

Rincewind
11-01-2004, 09:46 AM
Two prospective solution received so far. Still time for other interested parties to try out their problem solving skills.

Deadline 24:00 Wednesday, 14-Jan (GMT+11)

Rincewind
11-01-2004, 02:48 PM
Make that three solvers so far. Don't delay for a chance to get in "on the ground floor" for the fad that is sweeping the online BB community.

That didn't come across to self-obsessed or needy, did it? :D

Rincewind
13-01-2004, 05:10 PM
OK, Only 30 hours to the deadline. I have solution from MS and KB. I also have a solution from DR but he has subsequently sent me an PM that he would like to revise it. So unless I hear back I will assume the previous submission is withdrawn - leaving me with two solvers.

I have also had the opportunity to prepare my solution as clear and correct as I can make it. Hopefully, it is of some use. Due to the symbology required I've published this as a PDF file and will be linking to it from my solution post.

I'm also thinking of quoting the solvers' PMs directly in the solution post. I trust this is not a breach of protocol as I don't believe the solvers would have assumed confidentially in their messages, and would assume their PM would be posted anyhow.

If anyone doesn't want me to do this, please let me know. I know Matt is away and I'll have to deal with his ire (if any) on his return. However, Matt's submission is very interesting and I really want to include it the solution post.

Kevin Bonham
13-01-2004, 07:20 PM
I'm also thinking of quoting the solvers' PMs directly in the solution post. I trust this is not a breach of protocol as I don't believe the solvers would have assumed confidentially in their messages, and would assume their PM would be posted anyhow.

I certainly assumed this - it's not explicit from your previous posts but strongly suggested. Anyway Matt doesn't believe a PM is confidential anyway (past experience) so his consent may safely be taken for granted. :D


However, Matt's submission is very interesting and I really want to include it the solution post.

That's ... disturbing.

I am worried that he may have got it right. :shock:

Cat
13-01-2004, 08:46 PM
I've just sent my solution BJC

Rincewind
14-01-2004, 12:20 AM
I certainly assumed this - it's not explicit from your previous posts but strongly suggested. Anyway Matt doesn't believe a PM is confidential anyway (past experience) so his consent may safely be taken for granted. :D

Itwas clear from your post that this was the case. It is less so from Matt's message.



However, Matt's submission is very interesting and I really want to include it the solution post.

That's ... disturbing.

I am worried that he may have got it right. :shock:

I won't say too much more prior to the deadline as I don't want to confer any information about the possible solution. But I stand by my original posting, Matt's solution in indeed noteworthy.

22:30 to go!

Rincewind
14-01-2004, 12:22 AM
I've just sent my solution BJC

Yep, message received. Three solvers registered so far. But it is not too late for someone elseto have a crack at it.

arosar
14-01-2004, 08:46 AM
This is too painful Bazza. I never paid this thread much attention - but now I'm gettin' all a bit intrigued!

AR

Rincewind
14-01-2004, 03:33 PM
This is too painful Bazza. I never paid this thread much attention - but now I'm gettin' all a bit intrigued!

Why not have a go? 7:30 to go - it's not too late.

Rincewind
14-01-2004, 11:29 PM
OK. It is the hour of reckoning. For my worked solution look at the following link. If you have any questions let me know here or by PM, whatever is your preference.

Worked Solution (http://dreadnought.bcox.id.au/maths/q3soln.pdf)

The final scores were

Matt: 6/8
Kevin: 7/8
David: 6/8

Interestingly each person came up with a new approach on the problem all of which were basically correct. However, Matt and David went astray, I think by applying too much intuition. Perhaps, that's unfair in David's case as it may have just been a clerical error.

Also it was noted that it was the exclusion of the 20/0 distribution which caused the probability to not be 0.5 This is a very interesting result and probably answers Matt's original question way back when.

The other interesting result is that when distributing an even number of things between two possibilities (say 20) the 12-8 distribution is more likely than the 10-10 distribution. This would come as no surprise to Bridge players but is an interesting general rule. With an odd-number (say 19) then 10-9 is more likely than any other single possible distribution.

Anyway, pretty good results all round. I'll now post each submission in separate emails with some short comments.

Remember, judges decisions are final yada yada yada, except as I said above I am willing to enter into correspondence.

If anyone is interested I can come up with some other maths problems, not necessarily related to probability. If you're interested let me know.

Rincewind
14-01-2004, 11:31 PM
Ummm.....
The bag of twenty is not randomly distributed beacause any 20/20 sames are missing.

One white is drawn
The remaining 19 distribution can be composed as :
1 to 19 black ( there must be at least one black )
0 to 18 white ( the first drawn white may have been the only white )

The imposible composition is; 0 black to 19 whiute.

In the case of normal B/W distribution bags of 20 marbles, the chance of having all white is given by
=2^n
=2^20
=1048576
=> 1/1048576 = 0.000000090 = P(all white) = P(all black)

However, the chance of this particular event occuring has been eliminated from the set of all posible outcomes.

Also, for normal B/W distribution bags of 20 marbles, every draw has a P=0.5 for both balck and white.

Therefore, we can add the chance of the Impossible composition (0 blcak) to the normal P(black)=0.5

Thus, for the second marble after the first white draw
P(black) = 0.50000000 + 0.00000090 = 0.50000090
P(white) = 0.50000000 - 0.00000090 = 0.49999910

Gee, I hope this makes sence

It sort of does make sense. In fact I was quite surprised as to the simplicity and insightfulness of this line of reasoning.

Unfortunately, Matt forgot one thing (the fact that removing the 2 possible distributions changed the basis of all the probabilities

from 2^-20 to 1/(2^20 - 2), but that it all.

However, this is the problem of relying too much on intuition. It can lead you to an original solution but the lack of rigour can cause you to make mistakes too. Better to hve the inspiration and then the technique to prove the insight correct.

Regarding the scoring.

(a) 2 points

(b) 4 points - the insightfulness was remarkable. Unfortunately, the final answer was slightly off and there was a calculation error in the decimal side.

1/1048576 is approximately 0.00000095 so the answer should have been 0.49999905

Total Score: 6/8

Rincewind
14-01-2004, 11:34 PM
Hi Barry,

(a) Black
(b) (2^18 )-1/(2^19)-1, ie 262143/524287, ie 0.49999990 to 8 dps.

I did this both the long way and the short way, but I did the long way first, then noticed the short way afterwards.

Short way: We know that the probability of each marble in the bag being each colour is 0.5. So to start with there are (2^20) equally likely distributions of the marbles in the order that we are going to pull them out of the bag, except that 2 of these distributions are banned. Ignoring the colour of the first marble, there are 2x(2^18-1) legal distributions in which the first two marbles are the same colour, out of 2^20 distributions that are possible (again treating redraws as not redrawn). Then cancel 2s, and multiply ((2^18 )-1)/(2^19) by (2^19)/((2^19)-1) to deal with redraws (for full details see second para of long solution below) and you have the answer.

This method leads to the general solution. Note: What this tells you is that if the chance of each marble being black or white is known to be 0.5 anyway, then drawing marbles out of the bag tells you nothing new about the distribution of the remainder - it is only the banning of monochrome results that has any impact on that.

Long way, because it's the first way I did it :( (a bit like von Neumann summing the series to solve the fly and train problem) :

As with previous solution first marble being white tells us nothing about what colour (if any) is the majority. Further the colour of the first marble tells us nothing about which of the many possible distributions of Maj-Min (19-1 down to 10-10 as 20-0 is banned) we have.

Out of all the possible distributions of marbles in the random draw there is a 2x1/(2^20) = 1/(2^19) chance that the draw will be redone and hence a ((2^19)-1)/(2^19) chance that it won't. If it is redone the redrawing has no effect on the probabilities of other outcomes relative to each other - so find these probabilities assuming the draw is not redone and simply multiply that by (2^19)/((2^19)-1) to get the correct probabilities of eventually getting each permitted outcome.

Let z = number of marbles in the Maj group, then probability of there being z marbles (ignoring redraws) is 2x20Cz/(2^20) for z=11 to 19 (the 2 is because either colour could have z number of marbles) and simply 20C10/(2^20) for z=10. (As a side note, the bag is more likely to have an 11-9 or 12-8 split than a 10-10).

(Note for uninitiates in case this is posted on the BB: nCr = number of possible combinations of r successes from a sample of n success-failure events = n!/r!(n-r)! )

(Note for even more uninitiated for same reason - n! = 1x2x3x4....xn)

For each value of z between 10 and 19, the probability of the first two marbles being the same is (z/20)x((z-1)/19) + ((20-z)/20)x((19-z)/19)

(ie Maj, Maj + Min, Min, except that for z=10 both Maj and Min groups consist of 10 marbles).

This probability simplifies to (2(z^2)-40z+380)/380, ie (((x-10)^2)+90)/190 which is, incidentally, 90, 91, 94, 99, 106 ... 171 all/190 for z=10 to 19 in order.

So for each value of z we can now obtain both the probability of their being z marbles in the largest group, and the probability of the first two marbles having the same colour if there are z marbles in the largest group. Multiplying these together and cancelling out I get:

z=10, 21879/(2^18 )
z=11, 20111/(2^17)
z=12, 31161/(2^18 )
z=13, 5049/(2^16)
z=14, 2703/(2^16)
z=15, 1173/(2^16)
z=16, 3213/(2^19)
z=17, 417/(2^18 )
z=18, 77/(2^18 )
z=19, 9/(2^18 )

Mutliplying out and adding up the total is 262143/(2^19) - but this is still assuming no redraw.

To cater for redraws multiply by (2^19)/((2^19)-1), cancel (2^19)s to get

262143/524287.

Interestingly had redraws been allowed, the probability of a white marble on the second draw becomes 262144/524288 = 0.5, ie the first marble picked being white would have had no effect on the likely colour of the second marble. The stipulation that the marbles are of different colours changes this.

Let me know how I went or how badly I explained myself. :)

Almost full marks! I like the long way as this was basically my starting point too. The short version is good too. Unfortunately with this solution there was again an error with decimal side of the calculation (probably just a transcription error).

262143/524287 is approximately 0.49999905 (8 dpl)

I assume you got carried away with the 9's and included one too many. Anyway, just subtracting a point for that the score is...

(a) 2 points
(b) 5 points

Total score: 7/8 - and our winner of round 3.

Rincewind
14-01-2004, 11:35 PM
ok, this time!

1 white ball has gone leaving 19 balls in total.

Using the formula C=n!/r!(n-r)!, where n is the total no. of balls in left in the bag (19), and r is the number of white balls, Dr Evil has produced bags in the following combinations (C)

NO. WHITE BALLS IN BAG(a), NO. BALLS(b),NO. WHITE P=axb


18/19, 19, 18
17/19, 171, 153
16/19, 969, 816
15/19, 3876, 3060
14/19, 11628, 8568
13/19, 27132, 18564
12/19, 50388, 31824
11/19, 75582, 43758
10/19, 92378, 48620
9/19, 92378, 43758
8/19, 75582, 31824
7/19, 50388, 18564
6/19, 27132, 8568
5/19, 11628, 3060
4/19, 3876, 816
3/19, 969, 153
2/19, 171, 18
1/19, 19, 1

--------------------- ---------------------

Total 524286(all balls) 262143(white)

But there is 1 bag remaining with 19 black balls so the total combination is
524286+19=524305


so the answer is

a) black

b) 262143/524305 = 0.49998188


A valiant effort working from second principles but not quite right. Your table is almost complete I would have added the following line

0/19, 1, 0

Which would have accounted for the all black possibility and lead to the result 262143/524287.

However, everything else (including your calculation of the answer to 8 decimal places) was accurate so I'm scoring your answer on a par with Matt's - on the right track but not quite right. Possibly, lack of rigour in some of the reasoning leading you astray - possibly just an oversight. Score...

(a) 2 points
(b) 4 points

Result 6/8

Kevin Bonham
15-01-2004, 12:17 AM
262143/524287 is approximately 0.49999905 (8 dpl)

I assume you got carried away with the 9's and included one too many.

:oops:

I was using a calculator which couldn't hold all the decimal places, so I had to subtract the .499999 off to get the rest, and must have simply written one two many 9s down then not checked it. Dumb.

Careless errors like that were always my weakness but at least I had the method(s) right. :?

Feel free to post more, except I'm allergic to trig, geometry and calculus.

Cat
15-01-2004, 12:33 AM
Bugger! Well done KB, it's been about 25yrs since I did my statistics and I guess my rustiness shows in my inelegant solution.

Rincewind
15-01-2004, 10:05 AM
Feel free to post more, except I'm allergic to trig, geometry and calculus.

OK geometry it is! :D

Actually, I won't try composing any more problems but I do have a couple of favorites that like minded individuals might enjoy. The first one is a geometry one. It's cute and not very difficult.

I'll post it tonight. (Perhaps I should start a new thread).

Bill Gletsos
15-01-2004, 01:32 PM
Firstly let me congratulate all of you on excellent submissions. =D> =D> =D>

Before someone asks why I didin't bother entering there were two reasons.

Firstly I was/am busy doing ratings related stuff and secondly and more importantly I had seen this problem previously in a slightly modified form and therefore did not think it was fair to put in a response.

With regards to Matt's solution let me say I have seen this reasoning applied in similar cases, although to be honest I had forgotten about it until seeing Matt's response. #-o

One feature it has is its sheer simplicity. 8)
I commend him on it. Well done Matt. =D>

One interesting aspect is the following.

From the figures it can be seen that
((2^18 )-1)/((2^19)-1) = (2^-1) - (1/(2^20 - 2^1))

To the less mathematically inclined it is far from obvious that this is true. :-s :?

Rincewind
15-01-2004, 01:58 PM
From the figures it can be seen that
((2^18 )-1)/((2^19)-1) = (2^-1) - (1/(2^20 - 2^1))

That's pretty much covered in my derivation of the elegant solution. It goes

P = (2^(n-2) - 1)/(2^(n-1) - 1)

multiply by 2/2

P = (2^(n-1) - 2)/(2^n - 2)

Separting the numerator into 2^(n-1) -1 and -1

P = (2^(n-1) - 1)/(2(2^(n-1) - 1)) - 1/(2^n - 2)

Simplifying the first term you get

P = 1/2 - 1/(2^n - 2)

QED

But you're right - it is not immediately apparent. And it is pleasing that two different lines of reasoning can reach mathematical equivalents which are not obvious. ;)

Actually I prefer the first form for calculating the probabilities but I favoured the second form in my solution as it more clearly demonstrates the monotonical increasing and bounded at 0.5 behaviour of the solution for n marbles.

BTW as a further postscript had Dr Evil ensured the existence of marbles of both colours in the bag by a different method then different probabilities might result. EG say he looks after 19 marbles have been put in and if they are all the same colour then he adds a marble of the opposite colour, else he add one randomly. This is a similar problem and a similar answer (different colour is favoured) but with a slightly different probability.

Just goes to show, you can't assume nothing.

Bill Gletsos
15-01-2004, 02:21 PM
That's pretty much covered in my derivation of the elegant solution.
But you hadn't published your elegant solution. ;)

Rincewind
15-01-2004, 02:28 PM
Then what's this? ;)


OK. It is the hour of reckoning. For my worked solution look at the following link. If you have any questions let me know here or by PM, whatever is your preference.

Worked Solution (http://dreadnought.bcox.id.au/maths/q3soln.pdf)

Bill Gletsos
15-01-2004, 02:41 PM
Then what's this? ;)


OK. It is the hour of reckoning. For my worked solution look at the following link. If you have any questions let me know here or by PM, whatever is your preference.

Worked Solution (http://dreadnought.bcox.id.au/maths/q3soln.pdf)
#-o #-o

Rincewind
15-01-2004, 08:30 PM
Q4. The Three Circles Puzzle

Three conguent circles of radius r, colinear and centres are 2r apart (ie each are touching the adjacent circle at only one point).

The point A lies on the line passing through the centres of the circles and the first cirlce, but not the middle circle. The point D is tangential to the third circle. B and C are the points where the line AD passes through the middle circle.

Find the length of the chord BC in terms of r.

The following diagram should help clear up any confusion...

http://dreadnought.bcox.id.au/maths/3circles.JPG

Send solution to me via PM before nexts Wednesday night, 21-Jan at 24:00 GMT+11.

Rincewind
19-01-2004, 07:38 AM
Not even one solution received yet. You guys are allergic to geometry, aren't you?

Have a crack at it, you might be (pleasantly) surprised.

If anyone wants a hint, send me a PM.

arosar
19-01-2004, 05:06 PM
Hey Bazza...I've been meaning to ask you man. No need to answer if you don't want to, but I think you already told us anyways. You a teacher or something. I atually thought you were in IT.

AR

Rincewind
22-01-2004, 03:45 PM
Hey Bazza...I've been meaning to ask you man. No need to answer if you don't want to, but I think you already told us anyways. You a teacher or something. I atually thought you were in IT.

Yes, I'm in IT, not a teacher.

Puzzles are a hobby though. Cryptic crosswords, maths puzzles, logicical puzzles, etc, doesn't matter much.


BTW I only got one response to the geometry puzzle. You know who you were. It wasn't right.

So here are some hints.


The answer is a rational coefficient of r.

It can be reasoned using Euclidean geometry and Pythagoras' theorem.

Key facts.

A line originating from a circle which is perpendicular to a chord of that circle, bisects the chord.

The same is true as the chord becomes diminishingly small (i.e. the perpendicular to a tangent passes through the centre).

Cat
22-01-2004, 06:33 PM
When's the new deadline BJC?

Rincewind
22-01-2004, 06:45 PM
When the Noachian deluge of entries abates. ;)

The next puzzle will be pure number theory so the sooner I get the entries the better.

PHAT
27-01-2004, 09:58 AM
When the Noachian deluge of entries abates. ;)

The next puzzle will be pure number theory so the sooner I get the entries the better.

Is this over?

Rincewind
27-01-2004, 10:37 AM
Is this over?

No. Still no entries since the massive hints I dropped. Perhaps geometry is even less popular than I thought.

I'll post the solution when I find the text for the next puzzle which is much more difficult but related to number theory so might be more popular.

BTW Welcome back. You missed the start of the Club Rapid. :(

PHAT
27-01-2004, 11:07 AM
No. Still no entries since the massive hints I dropped. Perhaps geometry is even less popular than I thought.


Gimme a day and I'll get aroound to post ing somethoing



BTW Welcome back. You missed the start of the Club Rapid. :(

Yeah :( - was lounging around Pretty Beach with the tribe and hangers-on for 2 weeks.

Cat
27-01-2004, 02:19 PM
Yes, I'd like a try too. I just haven't had time. What about a friday 6.00pm deadline?

Rincewind
27-01-2004, 02:25 PM
OK. Friday 6pm it is.

I haven't gotten around to drawing the solution. I was just going to give a textual solution perhaps this will give me enough time to draw something up. :)

ursogr8
28-01-2004, 07:27 AM
Barry...PM sent to you re solution ;)

ursogr8
28-01-2004, 12:48 PM
Barry...PM sent to you re solution ;)


BTW
When your post count got above 1000 did your title change? :confused:
Now of course you are wearing the silk (cloth) and the chess title is hidden. ;)

starter

Rincewind
28-01-2004, 02:43 PM
BTW
When your post count got above 1000 did your title change? :confused:
Now of course you are wearing the silk (cloth) and the chess title is hidden. ;)

I assume so. What does it say now? ;)

Bonus points for working out the reference.

BTW PM recceived and understood. Is the solver aware of the public posting of solutions after the deadline elapses?

ursogr8
28-01-2004, 03:04 PM
I assume so. What does it say now? ;)

Bonus points for working out the reference.

BTW PM recceived and understood. Is the solver aware of the public posting of solutions after the deadline elapses?

Barry

I have sworn off all your bait after the AP affair. No bonus points for me.


The solver has remained a read-only access for 6 months so I presume only the user-id should be revealed. This would be safe. Trust me. :cool:
Second thoughts...he has a correct solution I presume.

starter

Rincewind
28-01-2004, 04:04 PM
I have sworn off all your bait after the AP affair. No bonus points for me.

Here is a hint. It is a reference from a 70s TV show. If anyone gets it I would be amazed.


The solver has remained a read-only access for 6 months so I presume only the user-id should be revealed. This would be safe. Trust me. :cool:
Second thoughts...he has a correct solution I presume.

No hints prior to D-day.

ursogr8
28-01-2004, 06:21 PM
Here is a hint. It is a reference from a 70s TV show. If anyone gets it I would be amazed.



No hints prior to D-day.

If it is Tabatha's mum you are in big trouble.

Rincewind
28-01-2004, 06:29 PM
If it is Tabatha's mum you are in big trouble.

Tabatha's mum was Sabrina and not at all bossy. Now Sabrina's mum, Endora, she is more of a boss witch. But you have the wrong show. Here is a hint...

Make way for the Boss Witch, all hail the Empress of Evil. ;)

ursogr8
28-01-2004, 06:39 PM
Tabatha's mum was Sabrina and not at all bossy. Now Sabrina's mum, Endora, she is more of a boss witch. But you have the wrong show. Here is a hint...

Make way for the Boss Witch, all hail the Empress of Evil. ;)

Baz

Did you answer what was the collective for leash?
Did you have a solitary chidhood?
What custom title should Ascaro choose on the other thread.


There. That should divert the witch question.

starter

Cat
29-01-2004, 08:39 PM
Sent the solution BJC. Those were pretty big hints you gave, there wasn't really much else to do!

Rincewind
29-01-2004, 08:58 PM
Sent the solution BJC. Those were pretty big hints you gave, there wasn't really much else to do!

It was all I could do to get some people to respond at all.

If it is a challenge you want check out the Japanese Circles (http://mathforum.org/wagon/spring04/p999.html) problem

:)

Cat
29-01-2004, 10:04 PM
It was all I could do to get some people to respond at all.

If it is a challenge you want check out the Japanese Circles (http://mathforum.org/wagon/spring04/p999.html) problem

:)

No, thanks really!

Bill Gletsos
29-01-2004, 10:48 PM
Tabatha's mum was Sabrina and not at all bossy. Now Sabrina's mum, Endora, she is more of a boss witch. But you have the wrong show.
Tabitha's mum was Samantha not Sabrina.

Rincewind
29-01-2004, 10:50 PM
There. That should divert the witch question.

The answer is H.R. Puffnstuff. In one episode Witchy-poo was expecting a visit fom the Boss Witch and had to prepare the castle for inspection. She also had Puffnstuff held prisoner. Jimmy dresses up as the boss witch and saves Puffnstuff.

I told you I would be impressed if anyone figured it out. :wink: (I guess not everyone has HR Puffnstuff on video).

Bill Gletsos
29-01-2004, 10:51 PM
Make way for the Boss Witch, all hail the Empress of Evil. ;)
Witchiepoo from H.R. Pufnstuf?

Rincewind
29-01-2004, 10:53 PM
Witchiepoo from H.R. Pufnstuf?

Very very close. See full explanation above.

I suppose you deserve bonus points for getting the spelling of the names right. :wink:

Bill Gletsos
29-01-2004, 11:02 PM
Very very close. See full explanation above.

I suppose you deserve bonus points for getting the spelling of the names right. :wink:
I hadn't seen your post before I answered.

I wasn't aware of the full answer, but it seemed like some sort of a name from H.R. Pufnstuf. The only witch I remembered in that was Witchiepoo.

Rincewind
29-01-2004, 11:11 PM
I hadn't seen your post before I answered.

I wasn't aware of the full answer, but it seemed like some sort of a name from H.R. Pufnstuf. The only witch I remembered in that was Witchiepoo.

Yes, the Boss Witch was Witchiepoo's one-up.

I realised you didn't see my message as I saw yours when mine was displayed after posting. The time difference is 1 minute but it is probably more like 10 seconds or less. :lol:

Quite a coincidence we both decided to post at the same time though, hey?

Bill Gletsos
29-01-2004, 11:35 PM
Yes, the Boss Witch was Witchiepoo's one-up.

I realised you didn't see my message as I saw yours when mine was displayed after posting. The time difference is 1 minute but it is probably more like 10 seconds or less. :lol:

Quite a coincidence we both decided to post at the same time though, hey?
I had only recently got home from a NSWCA Council meeting.

I just happened to read the thread, made my Tabitha post and racked the brain cells for a sec trying to work out what show it was likely to be.

Rincewind
30-01-2004, 01:10 PM
Only 3 hrs 50 mins to go before 6PM Friday. Any stragglers who want to have a crack at the three circles problem better get the lead out.

ursogr8
30-01-2004, 01:36 PM
I hadn't seen your post before I answered.

I wasn't aware of the full answer, but it seemed like some sort of a name from H.R. Pufnstuf. The only witch I remembered in that was Witchiepoo.



ggray

So it is becoming painfully obvious to me that I cannot catch up to you on post count unless I adopt the tactic of jumping in to the odd thread at random and leaving an AR (GG) type post.
Good, count 1 more for me.

And the relevance to Bill and Barry's references? Now there is a puzzle. :hmm:

ANSWER > We are all just filling in time, making posts, waiting for Barry's deadline to come around.

starter

Garvinator
30-01-2004, 01:44 PM
leaving an AR (GG) type post.
starter
what is a GG type post?

ursogr8
30-01-2004, 02:05 PM
what is a GG type post?

You will not believe this GG, but I typed a response and then when I tried to post I found the thread locked. Now who could do that? :uhoh:

Garvinator
30-01-2004, 02:20 PM
You will not believe this GG, but I typed a response and then when I tried to post I found the thread locked. Now who could do that? :uhoh:
I dont have even the foggiest about what you are talking about :rolleyes:

ursogr8
30-01-2004, 02:29 PM
I dont have even the foggiest about what you are talking about :rolleyes:

Could have been Barry in his moderator role. We are on his high class thread on recreational mathematics, and we are contributing not a jot.

Kevin Bonham
30-01-2004, 02:32 PM
I've made no attempt at this one. It's probably not all that difficult but geometry just doesn't do it for me. All the same I look forward to being impressed by the answers of those who actually make an effort. Bring on the next round. :cool:

arosar
30-01-2004, 02:32 PM
Cos all other threads are boring. Even junior thread is boring. jenni's avoiding my questions and won't reveal anything. Though I think Father Bill is in trouble. He keep calling someone an s.o.b. and disptick yet all we have so far is hearsay. And I have it on good authority that the aircon situation wasn't as bad as it sounded.

Now GG, this is an AR type post!

AR

Rincewind
30-01-2004, 03:19 PM
The next puzzle is my favourite from a book titled The Canterbury Puzzles written in the style of Chaucer by Henry Ernest Dudeney. If you can find it take a look you might like it.

The puzzle is basically to come up with the lowest number of people who can ride in columns of equal lengths 64 different ways. For example, 30 people can ride in 8 different formations

1) 1 column of 30
2) 2 columns of 15
3) 3 columns of 10
4) 5 columns of 6
5) 6 columns of 5
6) 10 columns of 3
7) 15 columns of 2
8) 30 columns of 1

So what is the lowest number of riders required to be able to ride in 64 different formations?

Please provide whatever working and intermediate results you think are interesting.

Rincewind
30-01-2004, 07:07 PM
Regarding the 3 circles problem there were two solvers.

booboo who basically had the right method but made a simple error in algebra which lead to the wrong final answer. However still worth a 75% mark.

David_Richards who got the answer completely right although I did take him to task on some of his sloppy rendering of algebraic formulae in text. Still forgive and forget so 100% for David as he did get it right.

The quick answer is as follows.

This is done by bisecting BC at E and recognising AEO and ADP are similar triangles. AO is 3r and AP is 5r, DP is r so EO is 3r/5.
Now BEO is right angle at E and BO (hypotenus) is r and OE is 3r/5 therefore BE is 4r/5. The same goes for the similar triangle CEO which is conguent but inverted. So EC is also 4r/5

Therefore BC is 8r/5

If anyone wants it explained more fully let me know.

Starter, booboo will probably be able to see the error of his ways himself. I think he left of a "/r" in the first line of his algebra. If he wants further explaination then just ask.

I hope the two solvers enjoyed the problem. It's not the most difficult but a elegant answer as it is not at all obvious that the ratio of BC : r should be rational.

Next problem has already be posted above. It is much more difficult (but still solveable with High School level techniques) however I wouldn't recommend leaving it until next Friday. :wink:

Deadline, Friday, 6 Feb, 24:00 AEST.

Kevin Bonham
30-01-2004, 07:24 PM
So what is the lowest number of riders required to be able to ride in 64 different formations?

I'm not sure yet if it makes a difference but does that mean exactly 64 different formations, or 64 or more?

Rincewind
30-01-2004, 08:59 PM
I'm not sure yet if it makes a difference but does that mean exactly 64 different formations, or 64 or more?

The answer is exactly 64 formations.

Kevin Bonham
30-01-2004, 09:53 PM
The answer is exactly 64 formations.

That makes it considerably easier. I mailed a solution a few minutes after your post. Its first paragraph can now be ignored.

Rincewind
31-01-2004, 11:15 AM
That makes it considerably easier. I mailed a solution a few minutes after your post. Its first paragraph can now be ignored.

Anyone who solves this problem quickly might like to try to find the smallest integer greater than 10^9 with exactly 1000 positive divisors.

The working is basically the same but a more generalised approach is required.

Rincewind
04-02-2004, 12:31 PM
Two days to go and just two solvers thus far, both arriving at the answer from completely different directions.

One of the solvers has gone have to have a crack at the extended version of the problem. Hopefully the other will find the time to give this a go too.

Any other erstwhile (or new) puzzlers want to try their hand at either or both better get started soon. Full solution to both will be posted Saturday.

arosar
04-02-2004, 12:51 PM
Bit of a question. Why is it that when people are illiterate, they are ostracised - just about? Yet when they are innumerate - they're treated as, well, normal?

AR

Rincewind
04-02-2004, 01:10 PM
When they are illiterate they sort of 'don't count.
But when they are innumerate well, they definitely 'don't count'.

That's right. Or to say it another way...

There are basically three sorts of people: those who are innumerate, and those who are not. :D

arosar
06-02-2004, 02:40 PM
How's about this for you Bazza - http://mathworld.wolfram.com/topics/RecreationalMathematics.html?

I discovered that link when I was looking up 'eigenvalues'! Whatever the hell those are.

AR

Rincewind
07-02-2004, 11:04 AM
The day of reckoning. Sorry for the delay but I was out at a friend's place last night watching the cricket, etc.

There were two solvers of the original puzzle. Kevin and Shaun.

Kevin solved it very quickly. Probably faster than I did on my initial exposure to this problem judging his response times. He also solved it what I'll call the pure mathematical method.


The question translates to: what is the smallest integer that has exactly 64 divisors, including one and itself.

Each integer can be expressed as a product of powers of prime numbers in the form (2^a)*(3^b)*(5^c)*(7^d)*(11^e)*(13^f)*(17^g).... etc where a,b,c etc are all whole numbers >= 0.

The number of different divisors each integer has can thus be given by the formula (a+1)*(b+1)*(c+1)*(d+1)....etc. If a prime number is not a divisor of the integer at all then that prime number is raised to power zero, so including it multiplies the number of divisors by 1, ie has no effect.

We are therefore seeking the smallest number of the form (2^a)*(3^b)*(5^c) ... where (a+1)*(b+1)*(c+1)... = 64 and a,b,c etc are all >= 0

The terms (a+1), (b+1), (c+1) etc must be powers of 2 (including 2^0=1), otherwise the product (a+1)*(b+1)*(c+1)... will not equal 64 as it will have a prime factor other than 2, because 64=2^6.

Also, for the solution to be minimal, (a+1)>=(b+1)>=(c+1) etc, because if a larger prime is raised to a higher power than a smaller one, it is possible to find a lower solution by swapping the powers of these two primes.

Using these rules and knowing that (2^x)*(2^y) = 2^(x+y), we can now list which powers of 2 the numbers (a+1), (b+1), (c+1) ... can possibly be, and hence translate these to the values of a,b,c...for the different prime factors. We already know that any prime factor beyond the 6th prime (13) is out of the picture at this stage.

powers of 2 for (2,3,5 ...) are 6,0,0.... gives 2^63
powers of 2 are 5,1,0,0... gives (2^31)*3
4,2,0... gives (2^15)*(3^3)
4,1,1,0... gives (2^15)*3*5
3,3,0... gives (2^7)*(3^7)
3,2,1... gives (2^7)*(3^3)*5
3,1,1,1... gives (2^7)*3*5*7
2,2,2 gives (2^3)*(3^3)*(5^3)
2,2,1,1 gives (2^3)*(3^3)*5*7
2,1,1,1,1 gives (2^3)*3*5*7*11
1,1,1,1,1,1 gives 2*3*5*7*11*13

Multiplying these out and starting at the bottom (just a little hunch!) we get 30030, 9240, 7560, 27000, 13440, 17280, 279936 and as 2^15=32768, being lazy, we can stop now.

7560 is the lowest of these and is therefore the answer.

The prime factor result used is called the Fundamental Theorem of Arithmatic. The final part of this answer wouldn't pass muster as a mathematical proof (being lazy not being a method of deductive logic :D ) but for the purposes of this exercise it is really only a wording issue. The thing to realise is that any answer involving 2^15 or higher is going to be greater than the known solution 7560. Full marks.

Shaun also submited correct solution involving a computational method.


The answer I arrive at is 7560. As with a lot of number theory problems, a brute force attack was used. I may have come up with a more theoretical solution but I cannot find my copy of "Introduction to Number Theory". Below is the python code I used to find the answer

#Solution to Canterbury Tale Problem

import math

maxcount = 0
for i in range(1,20000):
#Only need to check factors up the sqrt of number
limit = int(math.sqrt(i))
#Divisor variable
divisor = 1
#Number of factors
divcount = 0
while divisor <= limit:
#Does divisor divide i exactly
if i % divisor == 0:
#Increment divcount by 2 as the problem calls for a lots of b
#and b lots of a
divcount = divcount + 2
#inccrement divisor
divisor = divisor + 1
#check if number is an exact square and drop divcount by 1
if limit == math.sqrt(i):
divcount = divcount - 1
#only print the highest number of divisors so far to cut down on
#screen information
if divcount > maxcount:
print i,divcount
maxcount = divcount

I didn't verify the code but the answer generated is correct so let's assume it is right. An different approach but still valid in by books. Although for the as an exercise to the reader, prove this program generates the right result. ;)

Now Shaun went on to have a crack at the extended problem. This was the lowest number greater than 10^9 with exacty 1000 divisors. For this he swapped over to the mathematical approach.


Having tracked down mu copy of "Elementry Number Theory" by David M Burton the solution becomes much clearer.
The function I was trying to derive was the tau function, and it is an indictment on my pattern recognition skills that I couldn't look at 2^3*3^3*5*7 and see that 64 = (3+1)(3+1)(1+1)(1+1)
Now that I know this the problem breaks down to finding a number of the the form p^a*q^b*r^c*... where (a+1)(b+1)(c+1)... equals 1000.
Now 1000 factors downto 2^3*5^3 so a,b,c will be made up of a combination of these factors eg a=(10-1), b=(10-1), c=(10-1)
To find the minimum N with 1000 factors I minimised the sum of a+b+c... and arrived at
N = 2^4*3^4*5^4*7*11*13
After some trial and error I came up with
N=2^9*3^4*5^4*7*11 = 1995840000 which I think is the answer

I suggested that he try other combinations and a reply came back...


OK. Attempt number two gives me 1060290000 which factorises to 2^4*3^4*5^4*7*11*17

Which is correct.

Congratulations to both solvers.


Regarding the first solution: quick way to get the right combination is to realise there are to be six factors of the form p^2^n, the first 6 primes are

2, 3, 5, 7, 11, 13

And squared we have

4, 9, 25, ...

And to the fourth power we have

16, 81, ...

We obvously don't have to worry about higher powers. Arranging all these in order you get

2, 3, 4, 5, 7, 9, 11, 13, etc

The lowest 6 multiplied together are

2 x 3 x 4 x 5 x 7 x 9 = 7560


With the extension of the puzzle you have 1000 which factors to 2 ^ 3 * 5 ^ 3

The lowest solution is
2^4 x 3^4 x 5^4 x 7 x 11 x 13 = 810,810,000 < 10^9

So we need to make it bigger. We can try replacing 5^4 * 7 with 5 * 7^4, or replace 13 with 17, or 2^4 * 13 with 2^9. Any other replacements would be larger than at least one of these three replacements. These three possibilities yield...

2^4 x 3^4 x 5 x 7^4 x 11 x 13 = 2,224,862,640
2^4 x 3^4 x 5^4 x 7 x 11 x 17 = 1,060,290,000
2^9 x 3^4 x 5^4 x 7 x 11 = 1,995,840,000

Obviously the winner is 1,060,290,000


As always, any questions let me know.

shaun
07-02-2004, 08:20 PM
An important note on my python code. Python uses whitespace to denote code blocks. Obviously the whitespace has been removed by this BB software (I think in the PM I sent to Barry). I will leave it as an exercise for the reader to work out the correct code indentation.
Python is useful for solve number theory problems (and just about any other problem) as it's long int type is only restricted by the amount of memory on your computer. For more information www.python.org is the obvious place to look.

Rincewind
08-02-2004, 09:15 PM
Anyone interested in more puzzles? I don't have any suitable ones on the top of my head but I'm sure I could find something if people would enjoy solving them.

shaun
11-02-2004, 08:19 PM
A quick trifle with a chess theme.
In a chess tournament with 8 players, each has finished on a different number of points. The number of points scored by the second placed player is equal to the sum of points of the last 4 players. What is the result of the game between the players who finished third and seventh?

Rincewind
12-02-2004, 11:27 PM
Nice puzzle, Shaun. Did anyone else have a go at this?

BTW A rec math listserv group I'm on had a good puzzle this week. It was to come up with the number of orthogonal quadralaterals (rectangles and squares) in a staircase arrangements of squares nxn in size.

For example the 2x2 case looks something like this
._
|_|_
|_|_|

and has 5 o.q.'s: 3 1x1 squares and 2 1x2 rectangles.

The 3x3 case looks something like this...
._
|_|_
|_|_|_
|_|_|_|

The answer for this one is 15 but I'll leave counting the individuals as an exercise for the reader.

The puzzle was to come up with the number for the 11x11 configuration. But I say, why stop there? You may as well do the 50x50 case.

So that is the question. How many orthogonal quadralaterals in a 50x50 staircase arrangement of squares?

shaun
13-02-2004, 02:53 PM
A quick trifle with a chess theme.
In a chess tournament with 8 players, each has finished on a different number of points. The number of points scored by the second placed player is equal to the sum of points of the last 4 players. What is the result of the game between the players who finished third and seventh?

I only had 1 reply, but it was a correct one. Congrats Barry Cox. Here is his answer.
================================================== ===
I assume we are talking about a single round robin event.

As it is a 7 round event the maximum the 2nd player could have scored is 6. 6.5 doesn't make sense as they would mean 2nd went through undefeated and therefore the first player could not have won all his games which he must have to finish on 7.

Now the bottom 4 play 6 games amongst themselves so the minimum they can total is 6. As this minimum matches the 2nd players maximum we know this must be the exact value.

For the total of the bottom 4 to equal exactly 6 they must have lost all their games to the top half of the table.

Therefore, the result of 3rd vs 7th was win to 3rd
The higher placed finisher also won in all the sixteen games

1st-4th vs 5th-8th.

arosar
13-02-2004, 03:14 PM
Hey Bazza...I am so totally hopeless in maths - but can all that above be represented in a formala of some kind? Formulae always impress me.

AR

Rincewind
13-02-2004, 06:46 PM
Hey Bazza...I am so totally hopeless in maths - but can all that above be represented in a formala of some kind? Formulae always impress me.

Alas, all mathematics is not algebra, although it seems like it is at times. :D

There is a formula for the staircase problem, but it does involve sigma notation.

Rincewind
16-02-2004, 09:26 PM
A rec math listserv group I'm on had a good puzzle this week. It was to come up with the number of orthogonal quadralaterals (rectangles and squares) in a staircase arrangements of squares nxn in size.

For example the 2x2 case looks something like this
._
|_|_
|_|_|

and has 5 o.q.'s: 3 1x1 squares and 2 1x2 rectangles.

The 3x3 case looks something like this...
._
|_|_
|_|_|_
|_|_|_|

The answer for this one is 15 but I'll leave counting the individuals as an exercise for the reader.

The puzzle was to come up with the number for the 11x11 configuration. But I say, why stop there? You may as well do the 50x50 case.

So that is the question. How many orthogonal quadralaterals in a 50x50 staircase arrangement of squares?

Anyone going to have a go at this one or is everyone mathed out for now? If I don't hear anything for 2 days I'll post the general answer for nxn configuration as well as the value for n=50.

(Shaun, a cute programmatic solution should be possible via recursion.)

Kevin Bonham
16-02-2004, 11:54 PM
Anyone going to have a go at this one or is everyone mathed out for now? If I don't hear anything for 2 days I'll post the general answer for nxn configuration as well as the value for n=50.

(Shaun, a cute programmatic solution should be possible via recursion.)

I've been having a half-hearted stab at this one but haven't solved it yet.

arosar
17-02-2004, 11:43 AM
Alas, all mathematics is not algebra, although it seems like it is at times.

Mathematics is quite funny ain't it? I remember back in high school I did Physics and this fella in class compained to our teacher. He says, "Sir, we don't wanna solve that problem cos it's too hard. It's got too many numbers in it." So the teacher turns around and gives us a new problem. This time with no numbers but only letters and funny symbols! Mate, it was virtually 'impossible' to solve.

Have you heard of that Harvard comp at all? Apparently it's the most prestigious.

AR

skip to my lou
17-02-2004, 11:58 AM
Yes, Median score = 1 out of a possible 120. :eek:

skip to my lou
17-02-2004, 12:00 PM
Not enough spare time, sorry Barry.

Rincewind
17-02-2004, 04:07 PM
Yes, Median score = 1 out of a possible 120. :eek:

That's surprising. Is this the Harvard-MIT Mathematics Competition for high school kids we're talking about?

skip to my lou
17-02-2004, 08:05 PM
No, its not that one. I'll try and find out which Harvard test it is later.

Rincewind
22-02-2004, 11:19 PM
A rec math listserv group I'm on had a good puzzle this week. It was to come up with the number of orthogonal quadralaterals (rectangles and squares) in a staircase arrangements of squares nxn in size.

For example the 2x2 case looks something like this
._
|_|_
|_|_|

and has 5 o.q.'s: 3 1x1 squares and 2 1x2 rectangles.

The 3x3 case looks something like this...
._
|_|_
|_|_|_
|_|_|_|

The answer for this one is 15 but I'll leave counting the individuals as an exercise for the reader.

The puzzle was to come up with the number for the 11x11 configuration. But I say, why stop there? You may as well do the 50x50 case.

So that is the question. How many orthogonal quadralaterals in a 50x50 staircase arrangement of squares?

Unfortunatey, no solvers this time, so it's time to put you out of your misery. :hmm: :(

To start with it's pretty easy to see (by just counting row by row) that the number of unit squares in an nxn configuration is

1 + 2 + 3 + ... + (n-2) + (n-1) + n

lets symbolise this as Sig(q=1,n)[q]

There are a few ways to look at this puzzle but the one that makes the most sense to me is to consider every rectangle (let's call squares, rectangles for the duration of this post) as being defined by its bottom left and top right corners. Then if you fix the bottom left corner as the very bottom left of the staircase (as drawn above) then you have as many rectangles as you have unit squares.

Then if you consider the diagonal 1 unit square up and 1 to the right of the very bottom and fix these as the bottom left corner of every rectangle it can be seen that the number of rectangles you can make is equal to the same as the number of unit squares in the n-1 case for each one.

Likewise moving up one more diagonal you have 3 potential bottom left corners forming the same number of rectanges as in the n-2 case and so on and so forth until you get to the nth diagonal (the treads of the staircase) which have n cases forming the bottom left corner of only 1 rectangle each.

Thus we have the following general answer

F(n) = 1 x Sig(q=1,n)[q] + 2 x Sig(q=1,n-1)[q] + 3 x Sig(q=1,n-2)[q] + ... + (n-2) x Sig(q=1,3)[q] + (n-1) x Sig(q=1,2)[q] + n x Sig(q=1,1)[q]

This can be more simply expressed as a double sigma

F(n) = Sig(p=1,n)[p x Sig(q=1,n+1-p)[q]]

Some simple cases are...

F(2) = 1 x (1 + 2) + 2 x 1 = 3 + 2 = 5
F(3) = 1 x (1 + 2 + 3) + 2 x (1 + 2) + 3 x 1 = 6 + 6 + 3 = 15

For n = 11 the answer is F(11) = 1001 (Significant in the context of the listserver group where the problem was sourced as it was the 1001st problem of the series!)

For n = 50 the answer is F(50) = 292,825

These are a little tedious to work out by hand but can be readily calculated wth Excel. For example, enter the formula =row() is cell A1 and =A1+row() in A2. Then copy A2 and paste into A3:A50. (This sets the A column up with the number of unit squares in every nxn configuration from 1 to 50.)

Then set B1 =(51-row())*A1 and copy and past that into B2:B50. Then set B51=SUM(B1:B50) and there you have it.

arosar
08-03-2004, 12:14 PM
Hey Bazza mate. Did you read last Friday's AFR? There was a review in there of some new book about the 7 hardest mathematical puzzles of all time. It prompted me to ask you, what, in your opinion, is the hardest math puzzle of all time?

AR

Rincewind
08-03-2004, 12:56 PM
Hey Bazza mate. Did you read last Friday's AFR? There was a review in there of some new book about the 7 hardest mathematical puzzles of all time. It prompted me to ask you, what, in your opinion, is the hardest math puzzle of all time?

That would depend on the judging criteria. Are these solved or unsolved problems? I would think, in the main, unsolved problems must be considered "harder" than solved ones. Then there is the question, ARE they solveable in a closed form? Is it possible to prove that it is solveable/unsolveable, etc.

Anyway, of solved problems, Fermat's Last Theorem is my favourite. It has to be the granddaddy of tricky problems which eluded solvers for generations. Stickly speaking it is a proof, not a puzzle though, so perhaps it wouldn't qualify.

arosar
08-03-2004, 01:31 PM
Unsolved.

See, this is where I got a bit lost right. This fella was yappin' on about 'conjectures' and 'theorem'. One from memory was some Riemann something.

(Actually, only just now I realise that there is a direct link to the story. So read for yourself mate. It's quite interesting. http://afr.com/articles/2004/03/04/1078378902714.html)

AR

Rincewind
08-03-2004, 02:11 PM
Unsolved.

See, this is where I got a bit lost right. This fella was yappin' on about 'conjectures' and 'theorem'. One from memory was some Riemann something.

(Actually, only just now I realise that there is a direct link to the story. So read for yourself mate. It's quite interesting. http://afr.com/articles/2004/03/04/1078378902714.html)

Thanks for the link, interesting book. I think I'd heard about it before, but hadn't seen a review.

For more info on the Riemann Zeta Function, you can look here http://mathworld.wolfram.com/RiemannZetaFunction.html

10 years ago FLT would have made the list but that would have been shown up as bogus as it was proved and many other conjectures remained unproved. It is the ones which stir the imagination which make the list not necessarily the hardest. The other problem is how can you judge which puzzles are harder than others when the solutions are unknown? I'm not sure you can.

So perhaps it should be called Seven Unsolved Puzzles.. and not The Seven Greatest Unsolved Puzzles... :p Still one for the birthday list, I think.

arosar
18-03-2004, 02:48 PM
I reckon I got the hardest maths prob of all so far in here. Which among these three will get you ahead: hard work, attitude or knowledge? Demonstrate your answer mathematically.

AR

Rincewind
18-03-2004, 04:48 PM
I reckon I got the hardest maths prob of all so far in here. Which among these three will get you ahead: hard work, attitude or knowledge? Demonstrate your answer mathematically.

Don't be a goose!

But I will tell you something interesting which is on topic.

That formula I gave you before does have a closed form without sigma notation.

It's

a(n) = ([((n+2)^5-(n+1)^5)-((n+2)^3-(n+1)^3)]/24) - (((n+2)^5-(n+1)^5-1)/30)

I got this from the Online Encyclopedia of Integer Sequences. Turns out this sequence has a name. It's called A332. ;)

It also has physical applications in combinatorial chemistry.

arosar
22-03-2004, 01:05 PM
What is it with these chess players? Jason Chan, GM Tal Shaked and some other chess player I know in Sydney all do research into AI.

http://www.cs.washington.edu/homes/tshaked/academics.html
http://www.ug.cs.usyd.edu.au/~jchan3/

AR

Rincewind
22-03-2004, 03:49 PM
What is it with these chess players? Jason Chan, GM Tal Shaked and some other chess player I know in Sydney all do research into AI.

http://www.cs.washington.edu/homes/tshaked/academics.html
http://www.ug.cs.usyd.edu.au/~jchan3/


Rightly or wrongly chess has been seen as a good example of an AI problem. So those with an interest in chess and computer science would naturally tend to investigate this problem. Also computer scientists interested in the chess problem would seek out computer literate chess players as domain experts in the field.

But what has this to do with this thread on recreational mathematics?

Alan Shore
22-03-2004, 05:52 PM
Haha, Jason has a champion email address!

Rincewind
31-03-2004, 08:30 PM
While everyone is interested in Bayes' Theorem and the probablity of god existing in the other thread, here is a cute problem for the weekly list to which I subscribe. (Last week's problem was nice too but geometrical in nature so I spared you that one :D ). This one two has to do with probability so it is timely.

You are served a plate containing 100 spaghetti noodles. You randomly grab two ends from the pile and tie them together. Then you repeat this process until there are no ends left. What is the expected number of loops at the end?

This is a really nice problem. I have a solution but would be interested in another other solutions/novel approaches, etc. I think I have the right answer but you never know...



BTW To subscribe to this list yourself, send e-mail to majordomo@mathforum.org with ONLY the following words in the message body:

subscribe macpow

Rincewind
05-04-2004, 12:23 AM
You are served a plate containing 100 spaghetti noodles. You randomly grab two ends from the pile and tie them together. Then you repeat this process until there are no ends left. What is the expected number of loops at the end?


Anyone want a hint to this one? Is so read on...


If you have a plate of 100 noodles and grab two ends and tie them together, one of two things have happened:

(a) you grabbed the opposite ends of the same noodle, in which case you have reduced the 100 noodle problem to the 99 noodle problem but the solution will contain 1 extra loop (the one you just made); or,

(b) you grabbed two ends of different noodles, in which case you have reduced to the 99 noodle problem without make any more loops.

Kevin Bonham
05-04-2004, 01:30 PM
I missed this one when you first posted it. What's the definition of a loop? Eg if I tie noodle A to noodle B, noodle B to noodle C, noodle C to noodle D and noodle D to noodle A, does that qualify?

Rincewind
05-04-2004, 01:41 PM
I missed this one when you first posted it. What's the definition of a loop? Eg if I tie noodle A to noodle B, noodle B to noodle C, noodle C to noodle D and noodle D to noodle A, does that qualify?

Yes, one loop is a closed circuit of tied noodle(s) as you describe. As we are tying unpaired ends and the noodles are assumed to have two ends each, at the end of the exercise every noodle with be a member of exactly one loop. A loop can be constructed of any number of noodles greater than zero (up to a maximum of 100 in this example, of course)

eclectic
05-04-2004, 02:26 PM
Yes, one loop is a closed circuit of tied noodle(s) as you describe. As we are tying unpaired ends and the noodles are assumed to have two ends each, at the end of the exercise every noodle with be a member of exactly one loop. A loop can be constructed of any number of noodles greater than zero (up to a maximum of 100 in this example, of course)Barry,

Does that mean that ChessLover really is a "loop" if, according to Greg Canfell (and possibly others), more than one "noodle" is contributing to its outcome ?

Then again, only one tied "noodle" might be involved ... which would still make it a "loop".

:p :p

eclectic

Kevin Bonham
05-04-2004, 09:32 PM
Yes, one loop is a closed circuit of tied noodle(s) as you describe. As we are tying unpaired ends and the noodles are assumed to have two ends each, at the end of the exercise every noodle with be a member of exactly one loop. A loop can be constructed of any number of noodles greater than zero (up to a maximum of 100 in this example, of course)

Thanks Barry. This sounds like a good problem so hold off the attack dogs for a few days and I'll have a crack at solving it.

Gandalf
05-04-2004, 11:22 PM
It's a shame I already get far too much maths at the moment. These feel like familiar problems.

Maybe one day I'll come back here and take another look. :)

Rincewind
05-04-2004, 11:34 PM
Thanks Barry. This sounds like a good problem so hold off the attack dogs for a few days and I'll have a crack at solving it.

OK, you have till Easter. After all, it's the dogs' Easter too. ;)

Rhubarb
06-04-2004, 05:58 AM
Barry,

Does that mean that ChessLover really is a "loop" if, according to Greg Canfell (and possibly others), more than one "noodle" is contributing to its outcome ?

Then again, only one tied "noodle" might be involved ... which would still make it a "loop".

:p :p

eclectic

Expected number of loops in chesslover is 3 or 4 from about 100 candidates.

By a remarkable coincidence, I think the expected number of loops from 100 noodles in this problem is quite similar. Here's hoping I'm not wrong on both counts. Barry, do you want me to PM you my reasoning so as not to possibly ruin it for Kevin and others, or should I just post it here?

[EDIT: Barry, I've just read the earlier part of the thread so have assumed PM is the way to go.]

Garvinator
06-04-2004, 10:31 AM
[EDIT: Barry, I've just read the earlier part of the thread so have assumed PM is the way to go.]
yes pm is the way to go :D

Lucena
12-04-2004, 08:05 PM
It also has physical applications in combinatorial chemistry.what the hey is that?

Rincewind
12-04-2004, 08:15 PM
what the hey is that?

Not my area but I'm guessing it has to do with the different arrangements of atoms in molecules.

Kevin Bonham
16-04-2004, 02:03 AM
TV game shows are sometimes good sources of recreational maths amusement, which is just as well because they are not good sources of anything else except for evidence of human false consciousness. Today I watched a thing called "Deal or No Deal", having heard rumours that it was one of the most spectacularly dumb shows ever seen on television, and I was not disappointed. :rolleyes: I'm not sure if the point is that the contestants don't understand probability theory or (more charitably) that people who aren't loaded prefer to earn a safe moderate amount rather than gamble on winning lots even at good odds. (Yet they also enter lotteries, which involves sacrificing a small amount to try to win lots at bad odds. Go figure.)

This one may provide passing time-wasting value for some of you. Sale of the Century used to have a winners board which worked like this: There are twelve squares which each have a prize card behind them. The prize cards come in five matching pairs, a "WIN" card and a "CARS" card. The contestant who has won that night's game picks a square and the card randomly hidden behind it is revealed. Then the contestant continues this process until one of the following happens:

(a) the contestant has turned both cards of a matching pair, in which case the contestant wins that prize.
(b) the contestant has turned the WIN card, in which case the contestant wins whatever is on the next card turned.

Obviously a contestant who turns the CARS card before the WIN card cannot win the cars. And everyone wants to win the cars, because the other prices are overvalued rubbish only offered as prizes for the sake of advertising.

If the contestant chooses to play on, then on the next night (if that contestant wins that night's game as well) the board is reduced to 10 squares with four matching pairs, the WIN card and the CARS card (unless the cars have been won, in which case it's 10 squares with five matching pairs). And so on, until on night 6 the contestant (assuming they have won 6 games straight) wins whichever of the original six prizes remains, then on night 7 the contestant wins the cash jackpot.

Puzzles (really quite easy) :
(i) What is the probability of the winning contestant winning the cars on night 1?
(ii) Assuming the winning contestant wins six nights in a row, what is the probability that they win the cars on night 6 rather than any earlier?

When I worked these out I was quite impressed with the show's design.

Feel free to PM me answers if interested. Exact fractions not required, say 4 dps would do.

Rincewind
17-04-2004, 12:23 AM
You are served a plate containing 100 spaghetti noodles. You randomly grab two ends from the pile and tie them together. Then you repeat this process until there are no ends left. What is the expected number of loops at the end?

Everyone (being Greg and Kevin) both go it right. Greg did a good job of explaining his method so I'll quote his solution (in part) here...


E(n) = the expected number of loops from n noodles.
Clearly E(1) = 1
With 2 noodles, there's a 1 in 3 chance of picking the other end of the same noodle, which leaves 1 loop + the 1 noodle problem. The 2 in 3 chance immediately reduces to the 1 noodle problem.
So
E(2) = (1/3) [1 + E(1)] + (2/3)E(1)
= 1/3 + E(1)
= 1/3 + 1

Similarly, with 3 noodles the probability of picking the other end of the same noodle is 1 in 5, which gives one loop plus the 2 noodle problem, while the 4 in 5 chance reduces to the 2 noodle problem.
E(3) = (1/5) [1 + E(2)] + (4/5) E(2)
= 1/5 + E(2)
= 1/5 + 1/3 + 1.

In general, since there are 2n noodle ends, the probability of picking the other end of the same noodle is 1/(2n-1), which gives 1 extra loop plus the (n-1) noodles problem. The probability of NOT picking the other end is (2n-2)/(2n-1), which immediately reduces to the (n-1) noodles problem.
So,
E(n) = [1/(2n-1)] x [1+E(n-1)] + [(2n-2)/(2n-1)] x E(n-1)
= 1/(2n-1) + E(n-1)[(2n-2+1)/(2n-1)]
= 1/(2n-1) + E(n-1)

So,
E(100) = 1/199 + E(99)
= 1/199 + 1/197 + 1/195 + ... + 1/7 + 1/5 + 1/3 + 1


The estimate of this is 3.284342189..., which, as both solvers pointed out, is a hell of a lot less than one might expect.

Kevin raised the interesting question of what is the number of noodles expected in the largest loop. This looks to be quite a difficult problem. I looked at it for a little bit last night and no straightforward method was apparent. If someone has a take on this question, I'd be interested.

In the mean time, look at Kevin's Sale of the Century question.

Kevin Bonham
17-04-2004, 03:11 AM
Kevin raised the interesting question of what is the number of noodles expected in the largest loop. This looks to be quite a difficult problem. I looked at it for a little bit last night and no straightforward method was apparent. If someone has a take on this question, I'd be interested.

I really should be the one doing this :wall: over that one, since I invented it.
I'm giving it a serious look at the moment. It's possible (in theory) to look at it by breaking it up into loop lengths n for n = 100 to 1 and calculating for each n the probability that there is at least one loop of length n and no loop larger than that, but it's tedious beyond belief and would require massive calculation, probably needing to write a computer program to take seven and a half million years to reveal that the answer is 42. (Actually given the mean loop length for the mean number of loops is about 30.4, 42's probably not a bad guess). For instance I don't imagine working out the probability of all the different possible ways that the longest loop can be, say, 5 noodles long precisely, would be much fun at all without an algorithm.

I'm a bit notorious for doing stuff like this. I always used to get sidetracked from maths syllabi by trying to generalise or extend any set problem that intrigued me. Teachers didn't know what to do with me and generally just let me do it. It produced some nice results but also wasted a lot of lesson time. It wasn't until I got to national summer school level that I came across people who were willing to stand up to this habit and tell me that I should stop it because I simply didn't have the skills to solve the problem in question.

Lucena
28-04-2004, 08:04 PM
Anyone here know anything about breaking vigenere ciphers?

Kevin Bonham
29-04-2004, 03:58 AM
Solution to Sale of the Century problem will be posted here sometime in the next half a week or so.

shaun
29-04-2004, 09:18 AM
Anyone here know anything about breaking vigenere ciphers?

Yes, but I'll have to find my Crypto text book (it may be at home)

shaun
01-05-2004, 06:51 AM
Yes, but I'll have to find my Crypto text book (it may be at home)

This info comes from "Cryptography and Data Security" by D.E.R Denning.
A Vigenere cipher is a Polyalphabetic Substitution Cipher. Rather than shifting each letter of the plaintext by the same amount (eg 3 in the Caesar Cipher), the amount of shift is based on a key word or phrase. eg If the key letter is A then the plain text isn't shifted at all, if it is B the plain text shifts 1 letter (X becomes Y) and so one. The Nth letter of the text is shifted by the Nth letter of the Key.
As the plain text is usually longer than the Key then the Key is repeated for the length of the message. And this is the weakness of the cipher. Examine the encrypted text for repeated blocks of letters. If they are spaced at a regular interval, then you can extimate the length of the key. Eg If the string AONL appears 9 characters apart in the encrypted text, then the key length may be 1,3 or 9 characters long (factors of 9).
Once you are reasonably confident you have found the key lengh, just perform a frequency analysis on the 1st, n+1, 2n+1... letter to find the first letter of the key. Of course repeated three letter strings usually stand for the word 'the' or 'and' and can be used to speed up the method.

Lucena
04-05-2004, 03:46 PM
This info comes from "Cryptography and Data Security" by D.E.R Denning.
A Vigenere cipher is a Polyalphabetic Substitution Cipher. Rather than shifting each letter of the plaintext by the same amount (eg 3 in the Caesar Cipher), the amount of shift is based on a key word or phrase. eg If the key letter is A then the plain text isn't shifted at all, if it is B the plain text shifts 1 letter (X becomes Y) and so one. The Nth letter of the text is shifted by the Nth letter of the Key.
As the plain text is usually longer than the Key then the Key is repeated for the length of the message. And this is the weakness of the cipher. Examine the encrypted text for repeated blocks of letters. If they are spaced at a regular interval, then you can extimate the length of the key. Eg If the string AONL appears 9 characters apart in the encrypted text, then the key length may be 1,3 or 9 characters long (factors of 9).
Once you are reasonably confident you have found the key lengh, just perform a frequency analysis on the 1st, n+1, 2n+1... letter to find the first letter of the key. Of course repeated three letter strings usually stand for the word 'the' or 'and' and can be used to speed up the method.

Thank you shaun I finally got that question right in my assignment-the reason I was getting stuck was I had the wrong key length(period)-for some reason I thought it was 11 when it was really 16 :wall: :doh:

Kevin Bonham
13-05-2004, 11:11 PM
Solution to Sale of the Century problem will be posted here sometime in the next half a week or so.

.... where two weeks equals three days for sufficiently large values of three. :eek:

This solution from Barry - exactly the same answer as mine so either we're both right or ...


Nice problem. The calculations are a little tedious and I have done them all in Excel without checking too closely, but I think their ok. Let me know how they match up.

The probability of winning the car on the first night when their are twelve cards on the board is

P(12) = 1/12*1/11 + 10/12*(1/11*1/10 + 8/11*(1/10*1/9 + 6/10*(1/9*1/8 + 4/9*(1/8*1/7 + 2/8(1/7*1/6)))))

I worked this out to approximately 0.0308 (4 d.p)

P(12) ~ 0.0308
P(10) ~ 0.0406
P(08) ~ 0.0571
P(06) ~ 0.0889
P(04) ~ 0.1667
P(02) ~ 1.0000

I assume when the last two cards are WIN and CARS then this is the excpetion to the rule of the CARS card coming out before the WIN card meaning you can't win the cars.

Therefore, the chance of winning the cars on any particular night (Q(x)) is

Q(1) = P(12)
Q(2) = (1 - P(12)) * P(10)
Q(3) = (1 - P(12)) * (1 - P(10)) * P(8)
...
Broken down by the the chance of winning the car on any given night in a run of 6 the probabilities are

Q(1) ~ 0.0308
Q(2) ~ 0.0394
Q(3) ~ 0.0531
Q(4) ~ 0.0779
Q(5) ~ 0.1331
Q(6) ~ 0.6656
-----------
Sum ~ 1.0000

So roughly two thirds of the time the cars will not be won until night six.

Rincewind
13-05-2004, 11:51 PM
Two minor corrections.

P(02) = 1

and

Sum Q(1)..Q(6) = 1.

;)

Rincewind
22-06-2004, 10:09 AM
How could believe this thread is no longer on the front page? ;)

Here is a little question some people might enjoy...

The first snow of the season begins to fall during the night. The depth of the snow increases at a constant rate through the night and the following day. At 6 am a snowplough begins to clear the road of snow. The speed of the snowplough is inversely proportional to the depth of snow. In the period from 6 am to 8 am the snowplough clears 1 kilometer of road, but it takes a further 3.5 hours to clear the next kilometer.

At what time did it begin snowing?

shaun
24-06-2004, 05:00 PM
How could believe this thread is no longer on the front page? ;)

Here is a little question some people might enjoy...

The first snow of the season begins to fall during the night. The depth of the snow increases at a constant rate through the night and the following day. At 6 am a snowplough begins to clear the road of snow. The speed of the snowplough is inversely proportional to the depth of snow. In the period from 6 am to 8 am the snowplough clears 1 kilometer of road, but it takes a further 3.5 hours to clear the next kilometer.

At what time did it begin snowing?

Is there sufficient information to solve this problem? eg Can you arrive at an answer assuming it started snowing at 6am and work from there, or does this problem require an initial depth of snow at 6am to work?

Rincewind
24-06-2004, 05:33 PM
Is there sufficient information to solve this problem? eg Can you arrive at an answer assuming it started snowing at 6am and work from there, or does this problem require an initial depth of snow at 6am to work?

There is enough information. The actual height of snow and rate of accretion is not required to determine the time that snow started to fall.

BTW It started snowing before 6am. If you had a snowplough which had a speed inversely proportional to the height of snow, you wouldn't want to start it up when there wasn't any snow or you would get a division by zero exception. :)

arosar
24-06-2004, 05:52 PM
I love these problems of yours Barry. As soon as I read the problem, I smiled and thought, "This is pretty f**kin' fascinatiing".

AR

Rincewind
24-06-2004, 06:15 PM
I love these problems of yours Barry. As soon as I read the problem, I smiled and thought, "This is pretty f**kin' fascinatiing".

And solveable with 2U high school level mathematics.

Rincewind
26-06-2004, 01:31 AM
And solveable with 2U high school level mathematics.

I suppose I should point out this includes some HSC 2U level calculus. If anyone would like a hint, let me know.

Rincewind
03-07-2004, 03:10 PM
The first snow of the season begins to fall during the night. The depth of the snow increases at a constant rate through the night and the following day. At 6 am a snowplough begins to clear the road of snow. The speed of the snowplough is inversely proportional to the depth of snow. In the period from 6 am to 8 am the snowplough clears 1 kilometer of road, but it takes a further 3.5 hours to clear the next kilometer.

At what time did it begin snowing?

One approximate solution has been proffered using mid-point approximation of the speed of the snowplough. This provided a result which was close to the right answer but not exact.

In case the calculus component of the solution is causing some disinterest I'll briefly get past that part here. If you don't want to see it, please avert your eyes now....

Lets assume the snow began to fall at time, t=0

The height of snow at time t is: h = At, where A is some constant.
Let x be the position of the snowplough, begining at t=T, corresponding to 6am
The velocity of the snowplough (dx/dt) is inversily proportional to the height of snow. IE, dx/dt = B/h = B/(At), where B is some constant.

Now let define a new constant k = B/A. Then

dx/dt = k/t

This is the sort of d.e. that is given HSC exams. Solveable by direct integration w.r.t time (t).

x = k.log(t) + D, where D is the constant of integration

Now it is convenient in these sort of problems (involving exp/logs) to define D in terms which cause the general solution to simplify. In that case let D = k.log(C), where k is an aforementioned constant (B/A) and C is a new constant. This gives

x = k.log(t) + k.log(C)
x = k[log(C) + log(t)]
x = k.log(Ct)

Now using this general solution to the problem, and the other information provided in the problem, it is possible to to determine when the snow started falling.

shaun
07-07-2004, 09:02 PM
One day to mathematicians, Igor and Pavel, meet in the street.
"How are you? How are your sons?" asks Igor. "You have 3 sons don't you? But I have forgotten their ages".
"Yes, I do have 3 sons" replies Pavel. "The product of their ages is equal to 36". Looking around and then pointing to a nearby building, Pavel says "and the sum of their ages is equal to the number of windows in that building".
Igor thinks for a minute and then responds "Listen Pavel, I cannot find the ages of your sons"
"Oh I am vey sorry" says Pavel; "I forgot to tell you that the eldest has red hair"
"Ah. Now I know" says Igor.
What are the ages of the 3 sons?

Alan Shore
08-07-2004, 02:42 AM
One day to mathematicians, Igor and Pavel, meet in the street.
"How are you? How are your sons?" asks Igor. "You have 3 sons don't you? But I have forgotten their ages".
"Yes, I do have 3 sons" replies Pavel. "The product of their ages is equal to 36". Looking around and then pointing to a nearby building, Pavel says "and the sum of their ages is equal to the number of windows in that building".
Igor thinks for a minute and then responds "Listen Pavel, I cannot find the ages of your sons"
"Oh I am vey sorry" says Pavel; "I forgot to tell you that the eldest has red hair"
"Ah. Now I know" says Igor.
What are the ages of the 3 sons?


*If you don't want to see my reasoning before attempting to solve the problem yourself, scroll poast my post*




OK, I've had a bit of a think and come up with this:

The candidates regarding the 36 ages product are [36,1,1] [18,2,1] [12,3,1] [9,4,1] [9,2,2] [6,6,1] [6,3,2] [4,3,3,] (I *think* that's all).

Next the sum of their ages are equal to the number of windows at the building Igor is gazing at. Not given to us but known to Igor. The possibilities available are: [38, 21, 16, 14, 13, 13, 11 and 10].

Therefore Igor was unable to solve immediately as he was presented with an ambiguity: the ages of 9, 2, 2 and 6, 6 and 1.

So far insufficient info until it's revealed Pavel's eldest son has red hair. Why does this give it away suddenly? I will assume before this point Igor has never seen the boys in person. Here was my first hypothesis: when Igor gazes into the windows of the building, he actually sees Pavel's boys inside. From this, Igor is able to tell simply from looking. Nice lateral thinking, however this isn't required if we take the problem in its purist sense - dealing with positive integers in ages, there are two eldest sons, not one in the [6,6,1] case. Leaving us with my answer: The boys are ages 9, 2 and 2 respectively. (Perhaps the youngest ones are twins :p)

shaun
08-07-2004, 09:32 AM
Leaving us with my answer: The boys are ages 9, 2 and 2 respectively. (Perhaps the youngest ones are twins :p)
100% correct, right down to the reasoning.

Kevin Bonham
08-07-2004, 01:10 PM
The problem is nice mathematically but does contain a small empirical flaw.

It is possible that the two six year olds in the (6,6,1) case could be siblings born less than a year apart who are not twins. So Igor doesn't really know the answer is 9,2,2 - it's just extremely likely.

Siblings of this type have a name. I could mention it, but it's just a tad racist.

Alan Shore
08-07-2004, 04:42 PM
100% correct, right down to the reasoning.

:D


The problem is nice mathematically but does contain a small empirical flaw.

It is possible that the two six year olds in the (6,6,1) case could be siblings born less than a year apart who are not twins. So Igor doesn't really know the answer is 9,2,2 - it's just extremely likely.

Siblings of this type have a name. I could mention it, but it's just a tad racist.

Kevin, how did I guess you would make a comment like this... :rolleyes:

I did consider this, however as it involves a number of windows in a building it can't involve fractions, only positive integers (and yes a window is still a window even if its been smashed into fragments as I'm sure you may have pointed out had I not mentioned it...). Even if you don't like that, I could argue the window he looked through revealed his boys and he could make that discernment himself. Now away with your pedantry :p

P.S. What's the name of those twins then? I'm curious.

Kevin Bonham
08-07-2004, 05:24 PM
Kevin, how did I guess you would make a comment like this... :rolleyes:

I truly have no idea. :lol: Looks like you've tried to return fire in the same vein so let's see how it pans out ...


I did consider this, however as it involves a number of windows in a building it can't involve fractions, only positive integers (and yes a window is still a window even if its been smashed into fragments as I'm sure you may have pointed out had I not mentioned it...).

Naaah. Even if the individual ages are fractions and even if two of them differ by less than one, then it is still quite possible for the ages to add to a whole number (something which is actually overwhelmingly unlikely whatever the age distribution). Also this would bring (9,4,1) and (6,3,2) into play. So we have to assume that by "ages", Pavel refers to the common tradition of rounding ages down to the nearest integer.


Even if you don't like that, I could argue the window he looked through revealed his boys and he could make that discernment himself.

Well, this is possible. It's kind-of cheating because that info isn't provided, but it does indeed display good lateral thinking abilities, as you commented earlier. Therefore, taking nothing away from the quality of your original solution, I give you a generous 1/2 for your attempt at counter-pedantry.


P.S. What's the name of those twins then? I'm curious.

I don't know, go ask their father. :lol:

I'll PM it to you. I'm rather regretting mentioning it at all now.

Rincewind
08-07-2004, 10:11 PM
The problem is nice mathematically but does contain a small empirical flaw.

It is possible that the two six year olds in the (6,6,1) case could be siblings born less than a year apart who are not twins. So Igor doesn't really know the answer is 9,2,2 - it's just extremely likely.

Siblings of this type have a name. I could mention it, but it's just a tad racist.

There are a number of flaws but they are reasonably minor and when you work the correct solution out you are pretty sure the assumptions you have made were reasonavble under the circumstances.

A short list of things a nay-sayer might envoke:

(1) Pavel could have had children to multiple mothers, easily two in the same year with one distinctly older than the other.
(2) The eldest boy could still have been one of the twins. After all one twin has to be born first, however small the difference. (For an amusing anecdote of determining the first-born twin check out Genesis 38:27-30 the birth of Perez and Zerah).
(3) Could be I. twins from the same mother as previously mentioned.

Anyway, I think the puzzle was well formed. Now is anyone looking at when the snow began falling or should I post the second half of my solution now?

Kevin Bonham
09-07-2004, 12:36 AM
(1) Pavel could have had children to multiple mothers, easily two in the same year with one distinctly older than the other.

Yes. There is also that one.


(2) The eldest boy could still have been one of the twins. After all one twin has to be born first, however small the difference. (For an amusing anecdote of determining the first-born twin check out Genesis 38:27-30 the birth of Perez and Zerah).

That one would be unusual because most people won't refer to twins as "elder" or "younger" when talking to complete strangers.

Several years ago I heard of a case in some African country where a major legal issue turned on some technicality whereby when twins were born, the one born second was deemed to be the eldest (as per the Genesis example but irrespective of whether they wave at the world first or not.)


Anyway, I think the puzzle was well formed.

I agree. I was just being a nuisance.


Now is anyone looking at when the snow began falling or should I post the second half of my solution now?

The snow has been falling down here for weeks, but I'm still allergic to calculus. (Disappointing really, it's a very nice problem.)

Rincewind
09-07-2004, 02:36 AM
The snow has been falling down here for weeks, but I'm still allergic to calculus. (Disappointing really, it's a very nice problem.)

Calculus and geometry?!

I've done the calculus in part one. All that is left now is some algebra and index laws, and thinking about the problem the right way. ;)

Rincewind
11-07-2004, 02:48 PM
Ok, solution, part II.

We have the general solution x(t) = k.log(Ct), and the conditions that at time t=T (corresponding to 6am) x = 0, x(T+2) = 1, x(T+5.5) = 2.

Also considering the general solution is is apparent that k > 0 and C > 0, otherwise the solution would be trivial or non-real.

Firstly consider x(T) = 0

0 = k.log(CT)
k>0 therefore 0 = log(CT)
CT = 1 ... (*)

Now consider x(T+2) = 1

1 = k.log(C(T+2))
1 = k.log(CT+2C)
from (*) CT = 1
1 = k.log(2C+1)
multiply by 2 (the reason for this will become apparent later)
2 = 2k.log(2C+1)
by index law: a.log(b) = log(b^a)
2 = k.log(2C+1)^2
2 = k.log(4C^2+4C+1) ... (**)

Now consider x(T+5.5) = 2

2 = k.log(C(T+5.5))
2 = k.log(CT+5.5C)
from (*) CT = 1
2 = k.log(5.5C+1) ... (***)

now RHS of (**) and (***) can be equated as both equal 2.

k.log(4C^2+4C+1) = k.log(5.5C+1)
divide by k (remembering k>0)
log(4C^2+4C+1) = log(5.5C+1)
raise to the power of e
4C^2+4C+1 = 5.5C+1
simplifying
4C^2 = 3C/2
divide both side by C (remembering C>0)
4C = 3/2
C = 3/8

Now substituting C=3/8 back into (*)

3T/8 = 1
T = 8/3
T = 2:40

Therefore T is 2 hours and 40 minutes after the time t=0 (ie when the snow started to fall). As T corresponds to 6am then t=0 corresponds to 3:20am.

Therefore it started snowing at 3:20am.

Looks like I'll steer clear of calculus problems in the future. This one had a very low interest level. Shaun did submit a solution which assumed no calculus was required and got an answer pretty close to that above (3:28am) but that was the only tickle. However, I have a new problem which people may prefer as it is a return to discrete mathematics. ;)

As a point of trivia this problem was taken from the NSW 2U HSC from 2000. Too nice a problem for a HSC I think.

Rincewind
11-07-2004, 03:00 PM
Mr. and Mrs. Smith went to a party attended by 15 other couples.

Various handshakes took place during the party. In the end, Mrs. Smith asked each person at the party how many handshakes did they have. To her surprise, each person gave a different answer. How many hand shakes did Mr. Smith have?

(Here we assume that no person shakes hand with his/her spouse and of course, himself/herself. Also no person shook hands with the same person more than once.)

Rincewind
17-07-2004, 01:46 AM
Note that I've move a few of the non-puzzle sub-threads from this thread to a new one titled "Goldbach Conjecture/Riemann Hypothesis/etc". Anyone wanting to discuss the many attempted solutions to these sort of mathematical oddities can post there, leaving this thread for genuine recreational mathematics.

I was encouraged by a correct solution to the handshake puzzle on the same day as I posted it. However, no other solution have been forthcoming. It seems perhaps the other bb posters are too busy or bored to bother with rec maths. Come on, the world champs are over now, where's your sense of fun?

Or if some one has a favourite math puzzle, please post it!

arosar
19-07-2004, 02:57 PM
Any of youse smart mathematical types into code-breaking? I was just reading me paper over the weekend and spotted an item about how the GCHQ posted some problems for people to solve. Apparently they got quite a flood of responses. Well, here's the link to the probs: http://www.gchq.gov.uk/codebreaking/index.html

AR

Rincewind
19-07-2004, 03:46 PM
Any of youse smart mathematical types into code-breaking? I was just reading me paper over the weekend and spotted an item about how the GCHQ posted some problems for people to solve. Apparently they got quite a flood of responses. Well, here's the link to the probs: http://www.gchq.gov.uk/codebreaking/index.html

Not strictly speaking rec math, but I can see where you are going. If only all your posts were as close to on topic as this one. ;)

Regarding the handshake puzzle, is anyone still looking at it? If not I'll post the solution sometime soon. I have a new puzzle in Game Theory which is quite interesting. You'll enjoy it arosar as it is based on the final scene from the Sergio Leone classic "Il buono, il brutto, il cattivo" - or as it is better known, "The Good, the Bad and the Ugly".

Rincewind
16-08-2004, 05:28 PM
I will keep the three way duel puzzle up my sleeve for now.

Here is a triffle for any interested puzzlers.

I'm thinking of a number which last digit (units column) is a 6. When the 6 is removed from the end and placed at the start, then the resulting number is 6 times larger than the original number

i.e. xx---xx6 = 6xx---xx / 6.

where xx---xx is exactly the same string of digits.

I'm looking for the solution which is the smallest such number. All arithmetic is in the everyday (base 10) radix. If you don't know what base 10 is then don't worry, all arithmetic you've ever seen has been to the base of 10.

If you find this too easy, substitute n for 6 above and solve for n=1..9.

Kevin Bonham
18-08-2004, 12:09 AM
Nice puzzle. I will have a crack at it very soon.

Rhubarb
18-08-2004, 12:21 AM
Yes, I'd like to have a go at this one as well.

Also, Barry, unless I missed it, you haven't yet given the answer to the handshake puzzle. I had a think for a while when you first posted and thought that I might be half a chance but then forgot about it. Any chance of you hanging on for another couple of days? :pray:

Rincewind
18-08-2004, 08:28 AM
Yes, I'd like to have a go at this one as well.

Also, Barry, unless I missed it, you haven't yet given the answer to the handshake puzzle. I had a think for a while when you first posted and thought that I might be half a chance but then forgot about it. Any chance of you hanging on for another couple of days? :pray:

No worries. I think you're right KB was the only solver of the handshake problem (very soon after I posted it) and as no one else expressed an interest in the solution until now I haven't posted it. So no problems waiting.

shaun
18-08-2004, 04:29 PM
A follow up question to Barry's problem.
What is the relationship between the numbers 1012 and 2101 (apart from location of the first/last digit)?

Rincewind
18-08-2004, 05:34 PM
A follow up question to Barry's problem.
What is the relationship between the numbers 1012 and 2101 (apart from location of the first/last digit)?

Are they adjoining rooms at the Dublin Hilton?

Rincewind
30-08-2004, 06:36 PM
Regarding the puzzle on moving the last digit to the first digit. We had a few solutions all of which were correct. I believe Shaun was alluding to a Base 3 solution in his post above.

Here is the full solution for bases 3 to 10. If you still want a crack at it, avert your eyes... now!...

Base 3
2 1012

Base 4
2 102
3 10113

Base 5
2 102342
3 101343
4 101124214

Base 6
2 1031345242
3 1020412245351433
4 10132203044
5 10112404544315

Base 7
2 103524563142
3 1023
4 101546324
5 1013042156536245
6 1011236326213520225056554303404531464416

Base 8
2 1042
3 10262054413
4 10204
5 1015
6 10127114202562304053446
7 10112362022474404517

Base 9
2 10467842
3 103
4 102274
5 10175
6 10146711624827874217726406
7 101267355850647
8 10112360675404505630337202247314618

Base 10
2 105263157894736842
3 1034482758620689655172413793
4 102564
5 102040816326530612244897959183673469387755
6 10169491525423728813559322033898305084745762711864 40677966
7 1014492753623188405797
8 1012658227848
9 10112359550561797752808988764044943820224719

If someone wants to work out at post a base 16 solution, please do.

The handshake puzzle solution was 15. Basically, the constraints leads one to deduce the person shaking 30 hands must have been married to the person shalking 0 hands. Then it follows by similar reasoning that 29 is partnered with 1 and 28 with 2, and so on. Each partnership shaking a total of 30 hands between them. The only possible answer to Mr Smith, therefore, is 15 as it cannot be matched with any other survey respondent (as he is partnered with the pollster).

Anyway, on to the Good the Bad and the Ugly, I'll post that later tonight.

Rincewind
30-08-2004, 07:09 PM
If someone wants to work out at post a base 16 solution, please do.

I'm someone, right?


Base 16
2 10842
3 10572620ae4c415c9882b93
4 104
5 1033d91d2a2067b23a5440cf6474a8819ec8e95
6 102b1da46
7 1024e6a17
8 1020408
9 101ca4b3055ee19
a 1019c2d14ee4a
b 101767dce434a9b
c 101571ed3c506b39a22d9218202ae3da78a0d673445b243040 55c7b4f141ace688b6486080ab8f69e28359cd116c90c
d 1013c995a47babe74404f265691eeaf9d
e 10125e22708092f113840497889c2024bc44e
f 10112358e75d30336a0ab617909a3e202246b1ceba6066d415 6c2f21347c40448d639d74c0cda82ad85e4268f880891ac73a e9819b5055b0bc84d1f


The base 16 solution for F is 119 digits! Enjoy!

Rincewind
30-08-2004, 09:51 PM
Lovers of old Westerns might like this one. It is set in a circular piazza in the middle of a cemetry as in the end of the Sergio Leone 1966 classic, Il buono, il brutto, il cattivo - The Good, the Bad and the Ugly. However, there the similarity ends...

Blondie, Angel-eyes and Tuco fight a 3-way pistol duel. All three know that Blondie's chance of hitting any target is 0.5, while Angel-eyes never misses, and Tuco has a 0.8 chance of hitting any target. The way the duel works is that each person is to fire at their choice of target. The order of firing is determined by a random drawing, and the firing proceeds cyclically in that order (unless someone is hit, in that case this person doesn't shoot and the turn goes to the next person). The duel ends when only one person is left unhit.

What is the optimal strategy for each of them?

Who is most likely to survive given that everyone adopts the optimal strategy?

What is the probability that Blondie will be the survivor?


NB there is a trick to this, read my second paragraph VERY carefully. :eek:

As usual, post PMs to me if you would like feedback, I'll get back to you usually pretty quickly (hours rather than days). After a while I'll post the solution here and any interesting comments/solutions I receive.

Rhubarb
31-08-2004, 09:32 AM
Barry, I just noted your new sig line "Pi is equal to exactly 3" - 1 Kings 7:23, 2 Chron 4:2.

I've got a vague recollection from reading something when I was a kid that a few thousand years ago wealthy landowners would promulgate the notion that Pi equals 3 (fully knowing that it wasn't) in order to rip off the mathematically-challenged hoi polloi when dividing land. Interesting that this appears in the Word of the Lord?

(Believers and unbelievers alike, feel free to disabuse me of my cynicsm, since I know next to nothing about the bible.)

EDIT: What I'm thinking about may have been the value 22/7.

arosar
31-08-2004, 06:40 PM
Is Math a Sport?

See: http://www.chesschat.org/showthread.php?t=168&page=2

AR

Kevin Bonham
31-08-2004, 06:52 PM
An apologist's reply to Barry's .sig may be found here (http://www.carm.org/diff/2Chron4_2.htm).

I especially like the implied cop-out of saying that the circumference was of the inside while the radius was to the outside. However you will notice that the apologist has fluffed his lines by saying "the inside of the bowl could have been 10 cubits ..." where he should have said 30, since if you take 10 cubits as the diameter rather than the circumference of the inside you not only still have the original problem, but also have a bowl with zero thickness. :rolleyes:

arosar
14-09-2004, 04:59 PM
Where's Barry?

Hey Bazza mate, what's this about the Poincare Conjecture having been solved already? You heard of it?

AR

Rincewind
14-09-2004, 05:16 PM
Hey Bazza mate, what's this about the Poincare Conjecture having been solved already? You heard of it?

It's not really my sort of maths but from what I read it appears that Perelman came up with a proof for Thurston's geometrization conjecture a year or two ago. This is a more general result but if it is true than the Poincare conjecture is also true.

Seems everyone thinks Perelman's proof is solid but I'm not sure that his has been given the official seal of approval as yet.

arosar
14-09-2004, 05:19 PM
And . . .

http://www.math.purdue.edu/~branges/

AR

Rincewind
14-09-2004, 05:29 PM
Why bother posting spurrious links to this board when no one is either going to understand or read the articles? I think I remember doing some reading into this Louis de Branges de Bourcia before. But that was concerning the Riemann hypothesis not the Poincare conjecture.

Actually I think I started a new thread to separate pure mathematics discussion from recreational mathematics.

Rincewind
16-09-2004, 08:26 AM
Lovers of old Westerns might like this one. It is set in a circular piazza in the middle of a cemetry as in the end of the Sergio Leone 1966 classic, Il buono, il brutto, il cattivo - The Good, the Bad and the Ugly. However, there the similarity ends...

Blondie, Angel-eyes and Tuco fight a 3-way pistol duel. All three know that Blondie's chance of hitting any target is 0.5, while Angel-eyes never misses, and Tuco has a 0.8 chance of hitting any target. The way the duel works is that each person is to fire at their choice of target. The order of firing is determined by a random drawing, and the firing proceeds cyclically in that order (unless someone is hit, in that case this person doesn't shoot and the turn goes to the next person). The duel ends when only one person is left unhit.

What is the optimal strategy for each of them?

Who is most likely to survive given that everyone adopts the optimal strategy?

What is the probability that Blondie will be the survivor?


NB there is a trick to this, read my second paragraph VERY carefully. :eek:

As usual, post PMs to me if you would like feedback, I'll get back to you usually pretty quickly (hours rather than days). After a while I'll post the solution here and any interesting comments/solutions I receive.

No takers? jay_vee, I didn't receive the followup PM, did you send one?

jay_vee
16-09-2004, 09:49 AM
No takers? jay_vee, I didn't receive the followup PM, did you send one?

Sorry, a little exam got in the way.

I just typed my solution here, then deleted it. But I only now remembered, that you're not a moderator (or are you?) :-), so maybe KB or someone else could help in undeleting my response at the appropriate time?

Rincewind
16-09-2004, 10:39 AM
Sorry, a little exam got in the way.

I just typed my solution here, then deleted it. But I only now remembered, that you're not a moderator (or are you?) :-), so maybe KB or someone else could help in undeleting my response at the appropriate time?

I am a moderator. I've checked it out but was hoping you would have the numbers. The question has three parts...

1. What is the optimal strategy for each of them?

2. Who is most likely to survive given that everyone adopts the optimal strategy?

3. What is the probability that Blondie will be the survivor?

Your answer addresses part 1, but not parts 2 or 3.

jay_vee
16-09-2004, 11:27 AM
I have "reply-deleted" the numbers.

Edit: Whoops, need to correct that, Hang on a second

Edit(2): Okay, "reply-deleted" the second part of the numbers.
This is getting confusing, if I can't see the posting I'm correcting :-)

Edit(3): Arrgh, another oversight... Hang on

Edit(4): Okay, this should have been it, I hope :-)

Lucena
19-09-2004, 01:01 PM
Barry, I just noted your new sig line "Pi is equal to exactly 3" - 1 Kings 7:23, 2 Chron 4:2.

I've got a vague recollection from reading something when I was a kid that a few thousand years ago wealthy landowners would promulgate the notion that Pi equals 3 (fully knowing that it wasn't) in order to rip off the mathematically-challenged hoi polloi when dividing land. Interesting that this appears in the Word of the Lord?

(Believers and unbelievers alike, feel free to disabuse me of my cynicsm, since I know next to nothing about the bible.)

EDIT: What I'm thinking about may have been the value 22/7.I thought these two sites were kind of interesting:

http://www.tektonics.org/piwrong.html

http://www.answersingenesis.org/docs/494.asp

Rincewind
19-09-2004, 03:04 PM
I thought these two sites were kind of interesting:

http://www.tektonics.org/piwrong.html

http://www.answersingenesis.org/docs/494.asp

Thanks Gareth theose pages were niteresting and even somewhat amusing in parts. I found the second one especially so in footnote [1] where it says

the ratio of the circumference of a circle to its diameter, is what has been known as an irrational number or infinite non-repeating decimal, of which the first digits are 3.1415926536 ….

This actually contains a rounding error too. Pi rounded to 10 decimal places is what they show above. The tenth decimal place is actually a 5, which is what should be shown when they are following the string of digits by ellipses.

For interest's sake, the first twenty decmial places of pi are 3.14159265358979323846...

However I find there argument regarding the use of parts in cubit measures (or, more accurately, the lack therefore) somewhat weak. In their hypothetical they use the numbers d=9.65 c=30.32 (2 dec pls). In this case the diameter is closer to 9.5 than 10 and the circumference is closer to 30.5 than 30. The concept of 1/2 a cubit is not a difficult one to grasp nor to implement so the idea that this concept would not have been culturally compatible with the authors appears strained. Nor should the authors need to be mathematicians of pythagora's ability. After all they apparetnly had access to the the bath and should have been able to measure it first hand.

pax
21-09-2004, 12:06 PM
Ok, you guys probably all know this problem. It's a classic one for probabilistic thinking. I also have a variation that is interesting. Send me your answers by PM if you don't know the problem already.

Monty Hall hosts a quiz show in which a prize is placed behind one of three doors. Goats are placed behind the remaining doors.

1. You are contestant on the show, and choose one of the three doors. Monty opens one of the other doors, showing you a goat, and asks you if you would like to switch doors. Assuming Monty always shows you a goat:
a) Do you switch doors? (yes/no/doesn't matter)
b) What is the probability of you winning the prize if you switch?

2. There are two contestants on the show. Both choose a door, and Monty opens one of the chosen doors to expose a goat. The losing contestant is dismissed, and the winner is given the opportunity to switch. Assuming Monty does not favour either contestant:
a) Should the remaining contestant switch doors?(yes/no/doesn't matter)?
b) What is the probability that the remaining contestant will win the prize if he switches doors?

Rincewind
21-09-2004, 02:04 PM
Ok, you guys probably all know this problem. It's a classic one for probabilistic thinking. I also have a variation that is interesting. Send me your answers by PM if you don't know the problem already.

It was actually posted as a poll by Javier 3 weeks ago in this thread:

http://www.chesschat.org/showthread.php?t=1184

Although your part 2 is an interesting twist.

pax
21-09-2004, 02:20 PM
It was actually posted as a poll by Javier 3 weeks ago in this thread:

http://www.chesschat.org/showthread.php?t=1184

Although your part 2 is an interesting twist.

Ah yes, quite right. I think I expressed it a little less ambiguously here.

Rincewind
26-09-2004, 01:20 AM
I am a moderator. I've checked it out but was hoping you would have the numbers. The question has three parts...

1. What is the optimal strategy for each of them?

2. Who is most likely to survive given that everyone adopts the optimal strategy?

3. What is the probability that Blondie will be the survivor?

Your answer addresses part 1, but not parts 2 or 3.

OK we had a couple of solvers. Pax and jay_vee who both agreed with my calculations... eventually. Well done guys. :clap:

The answers are...

1. Optimal strategies are:
Angel Eyes : Shoot for Tuco then Blondie
Tuco : Shoot Angel Eyes and then Blondie

Now things get interesting. Blondie has better chance surviving a 2 way duel if he shoots first. So his best bet is that one of his opponents kills the other which will give him the first shot in the resulting two-way duel. So his optimal strategy is as follows

Blondie : to fire in the air if no one has been eliminated and then shoot to kill the remaining opponent as soon as one has been eliminated.

2. Blondie is the most likely survivor

3. Blondie's survival chance in 52.2* %

For the record Angel Eyes has a 30% chance and Tuco only 17.7* %


I like this puzzle because the worst shoot has a greater than 50% chance of surviving since the two better shots are trying so hard to kill each other. He even improves his odds by intentionally missing! I wonder what Charles Darwin would have had to say about this. :)

Rincewind
29-09-2004, 08:00 PM
The Macalester College problem of the week this week has a chess theme so I thought I'd share it with you.

---
How many ways are there to place 9 bishops on a 9x9 chessboard so that they dominate the board, meaning that every square is attacked by a bishop (or has a bishop on it)?

Source: A nice new book containing many chessboard puzzles by John Watkins, Across the Board, Princeton Univ Press, Problem 7.4.
---

I think my answer is right, send me a PM if you work out a solution. I won't be posting a solution until I check my answer with the list solution next week. ;)

Those of you who are interested in receiving the Macalester College Problem of the Week here's how...

To subscribe to this list, send e-mail to <<majordomo@mathforum.org>> with ONLY the following words in the message body:

subscribe macpow

Rincewind
04-10-2004, 11:42 PM
How many ways are there to place 9 bishops on a 9x9 chessboard so that they dominate the board, meaning that every square is attacked by a bishop (or has a bishop on it)?

My initial answer was in fact way off the mark, this puzzle is tricker than it looks. I have what I think to be the actually answer now and I am reasonably confident. However, my method of coming up with the solution was not very nice. If anyone has a nice method please post it.

The answer will be coming out in the next day or two when the list's next puzzle is sent.

arosar
13-10-2004, 03:01 PM
For your reading: http://www.physicsweb.org/articles/world/17/10/2/1#pwpov2_10-04

AR

Rincewind
13-10-2004, 09:53 PM
For your reading: http://www.physicsweb.org/articles/world/17/10/2/1#pwpov2_10-04

AR

Thanks Amiel. Interesting read. Euler's equation (in it's full form) for me is really e^(i*theta) = cos(theta) + i*sin(theta) [the RHS is sometimes abbreviated to cis(theta)]. Substitute theta = pi you immediately get

e^(i*pi) + 1 = 0

I know that the late, great Richard Feynman was greatly impressed by this form in his youth (according to the biography written by James Gleick). Yes the abbreviated form has an austere beauty, but the more general form is also profound as are the identifies you can simply derive from them, like

sin(theta) = (e^(i*theta) - e^(-i*theta))/(2*i)

Rhubarb
09-11-2004, 06:17 AM
My initial answer was in fact way off the mark, this puzzle is tricker than it looks. I have what I think to be the actually answer now and I am reasonably confident. However, my method of coming up with the solution was not very nice. If anyone has a nice method please post it.

The answer will be coming out in the next day or two when the list's next puzzle is sent.
Hi Barry,

You know that I am one of the ill-fated attempters.

What's the story; what's the answer?

Rincewind
09-11-2004, 08:44 AM
What's the story; what's the answer?

Your not the only one. My first attempts were also flawed but I did get it out before the one week turnaround time with a little help from VB.

The problem was...


The Macalester College problem of the week this week has a chess theme so I thought I'd share it with you.

---
How many ways are there to place 9 bishops on a 9x9 chessboard so that they dominate the board, meaning that every square is attacked by a bishop (or has a bishop on it)?

Source: A nice new book containing many chessboard puzzles by John Watkins, Across the Board, Princeton Univ Press, Problem 7.4.
---


OK the chessboard domain can be divided into two disconnected subdomains - that of the light and dark squares. No chessplayers needs proof that bishops are constrained to only one of these domains and least of all that a static bishop can only attack squares of the same colour of that where it is placed. Here I will adopt the convention that the corner squares are light. Therefore there are 41 light squares and 40 dark squares, 81 in all.

Now the two subdomains are isometric (meaning bishop moves are at 90 degrees to one another). This allows us to rotate each subdomain by 45 degrees and convert each sub-problem into one of rooks moving on diamond-shaped boards.

The dark-squared subdomain would look like this...


_ _
_|_|_|_
_|_|_|_|_|_
_|_|_|_|_|_|_|_
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|
|_|_|_|_|
|_|_|

The light-squared one like this...


_
_|_|_
_|_|_|_|_
_|_|_|_|_|_|_
_|_|_|_|_|_|_|_|_
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|
|_|

Looking at the light-squared domain it is reasonable easy to see that 4 pieces are not going to be able to dominate the whole domain. The best you can get to is all but one square covered. So 5 pieces are going to be needed for the light-squares and the dark-squares are going to have to do with 4 pieces.

(1) The dark squares

Dominating the dark-squares with 4 pieces can only be achieved by covering every row and column of the central 4x4 squares. The number of combinations to do this is easy to determine as 4! (4x3x2x1) = 24. This can be reasoned by consider filling the centre from left to right. The first piece can go on one of 4 squares, the next one of 3 (so as to cover a new row) the next has only 2 choices and the position of the last piece is determined by the first three.

(2) The light squares

To solve this problem I called on my silicon friend. The reason is that the same method as was used for the dark squares does not work here. There are solutions with at least one piece outside of the central 5x5 squares. The reason for this is that not all the rows extend past the central squares so it is possible for the 3rd and 7th rows and columns to be completely dominated by bishops in other central squares and by one bishop outside of the centre.

Anyway so my code just arranged 5 bishops on the first 5 squares and moved them through all combinations on squares, calculated to see if the board was dominated and if so add 1 to a counter. You'll find my code at the end of this message.

The answer the code produced was 2964

(3) Total combinations

So total combinations are 24 x 2964 = 71136.

This corresponded to the answer that came back from the macpow list. A copy of that is also attached after the code.



Function look9by9() As Integer
Set fs = CreateObject("Scripting.FileSystemObject")
Set z = fs.CreateTextFile("c:\testfile.txt", True)
Dim arr(8, 8) As Integer
Dim a As Integer
Dim b As Integer
Dim c As Integer
Dim d As Integer
Dim e As Integer
Dim i As Integer
Dim j As Integer
Dim x As Integer
For a = 0 To 36
For b = a To 37
For c = b To 38
For d = c To 39
For e = d To 40
For i = 0 To 8
For j = 0 To 8
arr(i, j) = 0
Next j
Next i
For i = 0 To 8
arr(xpos(a), i) = 1
arr(xpos(b), i) = 1
arr(xpos(c), i) = 1
arr(xpos(d), i) = 1
arr(xpos(e), i) = 1
arr(i, ypos(a)) = 1
arr(i, ypos(b)) = 1
arr(i, ypos(c)) = 1
arr(i, ypos(d)) = 1
arr(i, ypos(e)) = 1
Next i
found = True
For x = 0 To 40
If arr(xpos(x), ypos(x)) = 0 Then
found = False
End If
Next x
If found Then
z.WriteLine (a & ", " & b & ", " & c & ", " & d & ", " & e)
cnt = cnt + 1
End If
Next e
Next d
Next c
Next b
Next a
z.Close
look9by9 = cnt
End Function
Function xpos(cell As Integer) As Integer
Select Case (cell Mod 4)
Case 0
If cell = 0 Then
xpos = 0
ElseIf cell = 40 Then
xpos = 8
Else
xpos = 4
End If
Case 1
If cell < 11 Then
xpos = 1
Else
xpos = 5
End If
Case 2
If cell < 20 Then
xpos = 2
Else
xpos = 6
End If
Case 3
If cell < 29 Then
xpos = 3
Else
xpos = 7
End If
End Select
End Function
Function ypos(cell As Integer) As Integer
Select Case (cell Mod 5)
Case 0
ypos = 4
Case 1
If cell < 34 Then
ypos = 3
Else
ypos = 8
End If
Case 2
If cell < 25 Then
ypos = 2
Else
ypos = 7
End If
Case 3
If cell < 16 Then
ypos = 1
Else
ypos = 6
End If
Case 4
If cell < 7 Then
ypos = 0
Else
ypos = 5
End If
End Select
End Function




An interesting problem, and I hope you find my solution equally interesting.

Color the board in the usual fashion (although I don't know of a convention for which color goes in the corner for odd-dimensioned boards, so I will call that color "odd" and the other "even").

Since each bishop only attacks squares of the same color it is on, we can consider the two colors separately.

Of the odd squares, consider the 25 squares which form a 5x5 diamond. Covering these with bishops is just like covering a 5x5 board with rooks. Four of them can at best cover four rows and four columns, and the intersection of the uncovered row and the uncovered column will not be attacked or occupied. So five bishops on odd squares are necessary.

Now consider the even squares. There is a similar 4x4 diamond in the middle. Furthermore, there are squares on all four rows and all four columns outside this diamond. Therefore, all four rows and all four columns must be covered. So all the four remaining bishops must go in the even diamond, on different rows and columns. There are 4 ways to place a bishop in the first row, 3 ways in the second, etc., so there are 4! = 24 ways to place the even bishops.

Counting the ways of placing the odd bishops is more difficult. Certainly placing them on all the rows and columns of the diamond (5! = 120 configurations) will work, but it is also possible to place one or two bishops outside the diamond, or have some on the same line inside the diamond. This is true because only the central three rows and columns have squares outside the diamond. It is only necessary to cover all five rows and the central three columns. Because of the need to cover all five lines in some direction, it is not possible to have doubled-up bishops or bishops outside the diamond in both directions.

The valid positions for the odd bishops are all the positions that can be reached from those first 120 configurations by moving the bishops in the outermost columns of the diamond to any positions along their rows, for either way of defining rows and columns. To count these positions correctly requires using inclusion-exclusion to avoid over-counting. For a given definition of "rows" and "columns":

There are 2*4*6*4*2 = 384 ways of placing the 5 bishops onto different rows which fail to guard all three central columns.

There are 3*5*7*5*3 = 1575 ways of placing the 5 bishops onto different rows which fail to guard two particular central columns. But this includes 384 ways which fail to guard all three central columns, so there are 1191 ways which fail to guard those two columns but guard the third.

There are 4*6*8*6*4 = 4608 ways of placing the 5 bishops onto different rows which fail to guard one particular central column. But this includes 384 ways which fail to guard all the central columns, and 1191*2 ways which fail to guard that column and one other, so there 1842 ways which fail to guard just this one column.

There are 5*7*9*7*5 = 11025 ways of placing the 5 bishops onto different rows, irrespective of the columns. This includes 384 ways which guard no central columns, 1191*3 which fail to guard two central columns, and 1842*3 which fail to guard one central column. This leaves 1542 acceptable ways of placing the bishops to guard all 5 rows and all 3 central columns.

There are two ways of defining which lines are the rows. But of the 1542 arrangements for each definition of rows, 120 arrangements guard all 5 rows and columns and would be counted twice. So there are 1542*2 - 120 = 2964 total ways of arranging the odd bishops.

Since the odd and even bishops are entirely independent, there are 2964
* 24 = 71136 total ways of arranging the bishops so they attack or occupy every square.

Rincewind
14-11-2004, 09:56 PM
OK, no chess theme this time but there is one of snails.

There is a 20 foot high paper thin wall and a snail determined to get over it.

She begins first thing in the morning on the first day and by night fall has climbed 3 feet. She rests at night and slips due to gravity 2 feet. The next morning she begins again and climbs another 3 feet, during the night she rests and slips back 2 feet.

She continues this way until she reaches the top of the wall and then proceeds to climb down the other side. All the while climbing during the day and resting at night. Assuming the days and nights are 12 hours apiece, how many DAYS will it take the snail to climb from the bottom of the wall all the way over and back down to the bottom on the other side?

Send me your solutions as PMs and I will publish those I receive with my solution in a week or so.

Bruce, wait till you finish your exam. ;)

Rincewind
17-11-2004, 09:12 PM
I've had a few attempted solvers so far. And while most are close and getting closer, there have been no solutions which match mine as yet.

I would like to put the solution up in a couple of days so if you're interested please have a go and send me a PM with your solution. Remember the prestige of first solver is still up for grabs on this one. ;)

skip to my lou
17-11-2004, 09:17 PM
:( no time sorry

Rincewind
17-11-2004, 09:36 PM
:( no time sorry

Yep, you have a lot going on at the moment and puzzles should be at the bottom of your priority list.

Rincewind
25-11-2004, 07:46 PM
There is a 20 foot high paper thin wall and a snail determined to get over it.

She begins first thing in the morning on the first day and by night fall has climbed 3 feet. She rests at night and slips due to gravity 2 feet. The next morning she begins again and climbs another 3 feet, during the night she rests and slips back 2 feet.

She continues this way until she reaches the top of the wall and then proceeds to climb down the other side. All the while climbing during the day and resting at night. Assuming the days and nights are 12 hours apiece, how many DAYS will it take the snail to climb from the bottom of the wall all the way over and back down to the bottom on the other side?

Several posters replied on this puzzle making one of the most responded to yet. The first solver was Shaun followed closely by kegless. Kegless' response was (I thought) clear and concise and will serve as the general solution.



For the snail, if it slips 2 feet in 12 hours doing nothing and climbs 3 feet uphill in 12 hours with gravity, it would theoretically climb 5 feet in 12 hours in zero gravity, and hence would climb down 7 feet in 12 hours with gravity going downhill.

At the end of 17 days, the snail has climbed uphill 17 feet. At the end of daytime on the 18th day, the snail is at the top of the paper-thin wall. Now, when it goes to sleep, let's assume it starts sliding down the other side of the wall (since it gives a nice round answer - there are slightly different answers if on the night of the 18th day, the snail either stays on top of the wall - quite painful for the snail I imagine - or slides back down the first face).

After night on the 18th day, the snail has slipped 2 feet down the other side of the wall. It now travels down the wall at 9 feet per full day and hence reaches the bottom at the end of exactly 20 full days.

As you can see the journey take a full 20 days. The crux being determining the downwall daytime progress of the snail correctly as 7 feet. It's a trick one was the puzzle seems to be about determining the day that the snail crosses over from the front to the back of the wall.

Anyway, I don't have another puzzle at the moment but will keep on the lookout and will hopefully one will turn up shortly.

Meanwhile, if anyone is interested in short proofs in pure maths you might like a crack at the following (if you haven't seen it before). It only requires High School level maths...


For m and n both postive. Consider m/n as an approximation to SQRT(2). Show that (m+2n)/(m+n) is a better approximation to SQRT(2). (Hint: First show that SQRT(2) lies between m/n and (m+2n)/(m+n) ).


Any questions sned me a PM or post here. I don't expect a huge response to this one. But stay tuned a true rec math puzzle will be posted soon (I hope).

Rincewind
26-11-2004, 11:26 PM
For m and n both postive. Consider m/n as an approximation to SQRT(2). Show that (m+2n)/(m+n) is a better approximation to SQRT(2). (Hint: First show that SQRT(2) lies between m/n and (m+2n)/(m+n) ).

For anyone thinking about this there is an extension I just came up with.

Consider 1 < s <= 2. For m and n both positive. Consider m/n as an approximation to s (NB m/n <> s). Show that (m+(s^2)*n)/(m+n) is a better approximation to s.

[1st Hint: First show that s lies between m/n and (m+(s^2)*n)/(m+n)]
[2nd Hint: It might be easier to consider s=SQRT(2) first].

Rincewind
27-11-2004, 01:32 PM
OK, here is a puzzle proper, please respond via PM.

There are 5 men, each with a black or a white disc on his forehead (which he cannot see). A man with a white disc always tells the truth; statements made by any man with a black disc are always false.The following statements are made:

A says: `I see 3 white discs and 1 black.'
B says: `I see 4 black discs.'
C says: `I see 1 white disc and 3 black.'
E says: `I see 4 white discs.'

What color disc does each of the 5 men have?

shaun
28-11-2004, 04:13 PM
I only saw the above puzzle when I went to post the following tale :eh:

This morning while returning from a nephews wedding I stopped off at a little second hand bookshop in Taralga. On the shelf I found a first edition (1939), with dust jacket, of "Among These Mates" by Chielamangus, which I purchased for the sum of $12. Inside I found the following puzzle, which I have paraphrased
=====
Three men, named A,B, and C have allowed crosses the be painted on their foreheads. They are seated at a round table and are not allowed to communicate with each other. Each one knows that the colour of the cross is either white or blue. A prize is offered to the first of the three who can either see a WHITE cross on the other two or else correctly name the colour of his own cross. Mr A, who seems the best reasoner of the three sees that B and C both have BLUE crosses. After a little thought he correctly names the colour of his own cross and receives the prize. What was the colour of his cross and what was the process of reasoning?
=====

Now as this may be an easy puzzle for a bonus 10 points: Where is Taralga? and who is the strongest chess player to live in close proximity?

Rincewind
19-12-2004, 12:38 AM
There are 5 men, each with a black or a white disc on his forehead (which he cannot see). A man with a white disc always tells the truth; statements made by any man with a black disc are always false.The following statements are made:

A says: `I see 3 white discs and 1 black.'
B says: `I see 4 black discs.'
C says: `I see 1 white disc and 3 black.'
E says: `I see 4 white discs.'

What color disc does each of the 5 men have?

There were a couple solvers but no recent correspondence so I guess there will be no more. Ian Rout responded for the first time and his solution was expressed very clearly and (as far as I could tell) correctly so his solution is attached...


My answer to men with discs on heads:

1. If E is telling the truth then everybody has white and B would have white and be lying (also C), so E has black.

2. If A is telling the truth then he has white. E accounts for the one black he sees so A-D are all white. Again B and C would have white and be lying, so A has black.

3. If B is telling the truth then C and D are both black. This means C is black but is telling the truth (he sees B as the one white) so B has black.

4. If C is telling the truth then D is white (since C sees one white and A, B and E are black) which also fits everybody else. On the other hand if C is black then a white D means C is black and telling the truth or a black D means B is black and telling the truth.

So A, B and E are black, C and D are white.

However, Shaun once again captured the yellow jersey. :clap:

I'm on the look out for another suitable problem. In the meantime, if anyone can estabish the Riemann hypothesis, please let me know via PM. ;)

Rhubarb
20-12-2004, 08:50 PM
Did anyone else watch The Elegant Universe? I quite liked the New Yorker, engaging and non-patronising. To the point: there were the genius physicists, but then the maths-based guy, EdW, came along and resolved the five string theories into the 11th dimension.

I particularly like the idea that the Big Bang is the result of nothing more than a minor prang between 4-space mem(branes). That shit's going on all the time in 11-space. Gives one perspective what?

Rincewind
20-12-2004, 08:58 PM
Did anyone else watch The Elegant Universe? I quite liked the New Yorker, engaging and only slightly dorky. To the point: there were the genius physicists, but then the maths-based guy, EdW, came along and resolved the five string theories into the 11th dimension.

I particularly like the idea that the Big Bang is the result of nothing more than a minor prang between 4-space mem(branes). That shit's going on all the time in 11-space. Gives one perspective what?

No missed it but I wouldn't mind the DVD for crustmas. ;)

Ironically, I was probably to focused on study at the time to realise it was on. :(

Regarding the physicist/mathematician thing, that is basically why we have mathematicians. If the physicists were all able to do the maths better than the maths-guys, then all the mathematicans would be out of a job.

Rhubarb
20-12-2004, 09:24 PM
Regarding the physicist/mathematician thing, that is basically why we have mathematicians. If the physicists were all able to do the maths better than the maths-guys, then all the mathematicans would be out of a job.Of course. All science is reducible to physics. All physics is answerable to mathematics.

Of course, if physicists were as good at mathematics as mathematicians, mathematicians would just get a philosophy degree.

Rincewind
20-12-2004, 09:30 PM
Of course. All science is reducible to physics. All physics is answerable to mathematics.

Of course, if physicists were as good at mathematics as mathematicians, mathematicians would just get an arts degree.


I came across the following quote recently which I liked as it links physics and maths, but in a different way...

God may not play dice with the universe, but something strange is going on with the prime numbers - Erdös

Rhubarb
20-12-2004, 09:51 PM
Yes, a long time ago I watched a doco with my Dad on Erdös (air-dish, we called him). Hungarian I think - he died a few years ago. I still have the very extensive obituary by The Australian somewhere. I recall he was incredibly prolific - total speed freak who only slept 1-2 hours a day - with an oeuvre comparable only to Euler.

Regarding the quote: God is not only playing dice; he or she is seriously stuffing with our minds.

Rincewind
20-12-2004, 10:18 PM
Yes, a long time ago I watched a doco with my Dad on Erdös (air-dish, we called him). Hungarian I think - he died a few years ago. I still have the very extensive obituary by The Australian somewhere. I recall he was incredibly prolific - total speed freak who only slept 1-2 hours a day - with an oeuvre comparable only to Euler.

Regarding the quote: God is not only playing dice; he or she is seriously stuffing with our minds.

I really must subscribe to Aerial magazine.

Rhubarb
20-12-2004, 10:37 PM
I really must subscribe to Aerial magazine.
Okay, but don't fly too close to the sun.

Rincewind
20-12-2004, 11:25 PM
Okay, but don't fly too close to the sun.

That is the art. ;)

shaun
21-12-2004, 08:36 AM
=====
Three men, named A,B, and C have allowed crosses the be painted on their foreheads. They are seated at a round table and are not allowed to communicate with each other. Each one knows that the colour of the cross is either white or blue. A prize is offered to the first of the three who can either see a WHITE cross on the other two or else correctly name the colour of his own cross. Mr A, who seems the best reasoner of the three sees that B and C both have BLUE crosses. After a little thought he correctly names the colour of his own cross and receives the prize. What was the colour of his cross and what was the process of reasoning?
=====

Now as this may be an easy puzzle for a bonus 10 points: Where is Taralga? and who is the strongest chess player to live in close proximity?

As for this puzzle Barry is the winner. A also has a blue cross and works this out as follows. If he had a White cross then B and C would see 1 white and 1 blue. B or C could then assume their own cross must be blue as otherwise someones hand would have gone straight up having seen 2 white crosses. But as B or C's hand did not go up (albeit a little more slowly) choosing Blue, A reasons his cross cannot be White so it must be Blue.
As for the bonus questions: Taralga is north of Goulburn on the road to Oberon. And the strongest player in the area (as far as I can tell) is Oskar Hellmann.

Rincewind
09-02-2005, 09:15 PM
The distance between A and B is 999 km. Poles are put up along the road at 1 km intervals indicating the distances to A and to B (0,999),(1,998),...(999,0).

How many signs have only 2 distinct digits?

pax
10-02-2005, 10:49 AM
Three men, named A,B, and C have allowed crosses the be painted on their foreheads. They are seated at a round table and are not allowed to communicate with each other. Each one knows that the colour of the cross is either white or blue. A prize is offered to the first of the three who can either see a WHITE cross on the other two or else correctly name the colour of his own cross. Mr A, who seems the best reasoner of the three sees that B and C both have BLUE crosses. After a little thought he correctly names the colour of his own cross and receives the prize. What was the colour of his cross and what was the process of reasoning?

I think the better phrasing of this problem is:
"Three intelligent men, named A,B, and C have allowed crosses the be painted on their foreheads. They are seated at a round table and are not allowed to communicate with each other. Each one knows that the colour of the cross is either white or blue, and that there is at least one blue cross. A prize is offered to the first of the three who can correctly name the colour of his own cross. Mr A, who seems the best reasoner of the three sees that B and C both have BLUE crosses. After a little thought he correctly names the colour of his own cross and receives the prize. What was the colour of his cross and what was the process of reasoning?"

You don't need the "or can see a white cross" bit if you know there is at least one blue cross. You also need to assume they are good reasoners, otherwise the solution isn't robust. I think the version I have seen says "equally intelligent men" who come up with the answer simultaneously.

Rincewind
11-04-2005, 11:40 PM
The pole puzzle was a bit of a schermozzle. But here is a cracker right out of the box.


Alice: I'm thinking of a polynomial with nonnegative integer coefficients. Can you tell me what it is?

Bob: Well, I need more info than that. Can I ask you for some values of the polynomial?

Alice: That seems reasonable. How many would you like?

Bob: Well, N+1 would be nice, where N is the degree of your polynomial, for then I could just solve N+1 equations in N+1 unknowns.

Alice: That would take too long, both for me and for you. Moreover, you don't know the degree and I don't want to reveal it. But I am willing to tell you two values of the polynomial for integer arguments that you choose.

Can Bob determine Alice's polynomial P(x) asking Alice only twice for integer values of P(x)?

Source: CMJ p. 100 Mar 2005, where it is attributed to I. B. Keene at the University of Michigan.

Rincewind
16-04-2005, 11:41 AM
5 days and nary a nibble. Come on guys (and gals), the answer is quite short and accessible to all.

Rincewind
23-04-2005, 02:44 PM
Still nothing. Anyone want the solution or will I leave it up here as an unsolved mystery?

Spiny Norman
23-04-2005, 06:56 PM
Still nothing. Anyone want the solution or will I leave it up here as an unsolved mystery?

What's a polynomial ? <chuckles> Its 25 years since I did Pure Maths in HSC! I've forgotten most of it. :eek:

Rincewind
24-04-2005, 11:57 AM
What's a polynomial ?

http://mathworld.wolfram.com/Polynomial.html

In this problem we are obviously talking about a polynomial in one variable (univariate) and with non-negative integer coefficients. You seem to know something about programming, Frosty, so let me word it in programmer parlayance.

Determine the value of every A[n] where A is an array of integers and it is given than none of them are negative. You may call the function P(x) twice for information. P(x) is defined as


function P(int x) returns int
val = 0
for i = 0 to N
val = val + A[i] * (x^i)
next i
return val
end function

where N, the number of elements in the array A, is not known.

Does this make sense?

Spiny Norman
24-04-2005, 09:35 PM
Sorry RW, I've spent five minutes looking at it and I'm still none the wiser. :hmm: Applied Maths was more my strong point (I got an 'A' in HSC for Applied, whereas only a 'C' for Pure Maths). I'll be interested to see the solution tho'.

Rincewind
24-04-2005, 10:09 PM
Sorry RW, I've spent five minutes looking at it and I'm still none the wiser. :hmm: Applied Maths was more my strong point (I got an 'A' in HSC for Applied, whereas only a 'C' for Pure Maths). I'll be interested to see the solution tho'.

Me too. I'll leave it for a bit longer as the programmer version might be more accessible to some and actually gives a few hints which were more discreetly delivered in the original. I'll post the solution after Friday.

alexmdc
25-04-2005, 12:22 PM
Does Bob hear the answer to his first argument before asking the second time? If this is the case then I think there's a solution.

Rincewind
25-04-2005, 12:35 PM
Does Bob hear the answer to his first argument before asking the second time? If this is the case then I think there's a solution.

Alex, I think you're on the right track. ;)

alexmdc
25-04-2005, 01:01 PM
Here's what I got:

If the polynomial is P(x) = ... + cx^2 + bx + a
First ask for P(1). This gives you the sum of the coefficients, let's say N. Then ask for P(N). Now you can work out a, since a <N and P(N) = kN + a.
Then work out P'(1) = P(1) - a and P'(N) = (P(N) - a) / N
Repeat to find b, c, etc until P'''(1) = P'''(N) (how ever many differentations you need) and thats it!

Well it worked on my examples anyway

Rincewind
25-04-2005, 01:16 PM
Here's what I got:

If the polynomial is P(x) = ... + cx^2 + bx + a
First ask for P(1). This gives you the sum of the coefficients, let's say N. Then ask for P(N). Now you can work out a, since a <N and P(N) = kN + a.
Then work out P'(1) = P(1) - a and P'(N) = (P(N) - a) / N
Repeat to find b, c, etc until P'''(1) = P'''(N) (how ever many differentations you need) and thats it!

Well it worked on my examples anyway

That's the idea. Well done. Just one minor point causes your solution a slight problem in one special case (but doesn't invalidate it).

P(1) could be identically equal to one of the coefficients if it is a one term polynomial (e.g. if P(x) = 5, then a = P(1) = 5). When given the value of P(5) = 5, by your algorithm you get P(x) = x, which is not consistent with P(1)=5.

I'm sure you could write a more elegant algorithm to overcome this issue but the minor correction of a second guess of P(1)+1 avoids this problem all together. ;)

An even more elegant solution however might be to make a second guess of the next power of 10 greater than P(1). The all the answers can just be read off by breaking that number into equal number of digits.

Rincewind
27-04-2005, 04:45 PM
BTW Pax also entered a correct soln by PM. :clap:

Spiny Norman
27-04-2005, 06:43 PM
BTW Pax also entered a correct soln by PM. :clap:

... :doh: ... all the problem solving is making me depressed ... mainly because I can't solve 'em! :boohoo:

arosar
30-06-2005, 04:47 PM
bump

AR

Garvinator
11-08-2005, 03:25 AM
Is this the thread you are after kegless?

Rhubarb
16-08-2005, 05:06 PM
Yes thanks, gggg. What would we do without you?

Barry, I'm having difficulties solving the problem I had in mind, and I don't want to post it until I'm fairly certain. I may have to enlist the help of my Dad.

Just as an appetitiser - and admittedly it's an insubstantial and almost trivial appetiser - I was watching the Wallabies take on the Boks for the Nelson Mandela Plate a few weeks ago (the first in their current three-match losing streak :( ). After the Saffas' first intercept try, I found myself distracted by Nelson's prison number, 46664, writ 50 feet high on the field. By the time the Wobblies had allowed another intercept try, I'd figured out how many palindromes there were between 1 and 100,000.

Rincewind
16-08-2005, 07:01 PM
While on the topic of palindromes, I sent the following to kegless but thought it might be of interest to others.


Discussing palindromes always reminds me of the following puzzle.

Define the act of palindromisation as follows.
(1) If number is a palindrome then it has been palindromised, stop.
(2) Otherwise, reverse the order of the digits and add it to the first number
(3) go to step 1

e.g. The number 11 is already palindromised. The number 12, in not but when 12 + 21 is performed the result 33 is a palindrome. We say 12 can be palindromised in 1 iteration.

Now I conject there exists some numbers which defy all attempts to be palindromised. However, I am unaware of any proof of this. If we except that such numbers exist as 'Bazza's conjecture' it is easy to prove that if only one such number exists then an infinite set of such numbers must also exist.

Anyway, the task is fortunately not the prove Bazza's conjecture but to determine the lowest number which seems to satisfy it.

I heard this puzzle many years ago (around 25 is my guess). I believe it appeared in an issue of Omni or Scientific American.

jase
17-08-2005, 10:57 AM
Not sure why I waded into this thread, but here I am...with time to kill...

Baz, can you clarify the task a little for me? I'm unsure how literally to read your conjecture - I have assumed given the topic that numbers must be double figures, to satisfy the potential for palindromisation with 1 iteration, and worked towards a number that would be triple figures in 1 iteration. Not that applying step 2 to create a three digit number would satisfy the problem, it just seemed as good a starting point as any. 19.

But there's probably more to it and I haven't looked deep enough for what is being asked.

Rincewind
17-08-2005, 01:05 PM
Not sure why I waded into this thread, but here I am...with time to kill...

Baz, can you clarify the task a little for me? I'm unsure how literally to read your conjecture - I have assumed given the topic that numbers must be double figures, to satisfy the potential for palindromisation with 1 iteration, and worked towards a number that would be triple figures in 1 iteration. Not that applying step 2 to create a three digit number would satisfy the problem, it just seemed as good a starting point as any. 19.

But there's probably more to it and I haven't looked deep enough for what is being asked.

Yes all single digit numbers would already be palindromised. (IE zero iterations). 19 would take 2 iterations 19 -> 110 -> 121. Most numbers will palindromise rather quickly (say less than 10 iterations) some have been through 1000s of iterations without producing a palindrome.

Your task (if you choose to accept it) is to find the lowest of these non-palindromising numbers.

pballard
17-08-2005, 10:50 PM
While on the topic of palindromes, I sent the following to kegless but thought it might be of interest to others.

Discussing palindromes always reminds me of the following puzzle.

Define the act of palindromisation as follows.
(1) If number is a palindrome then it has been palindromised, stop.
(2) Otherwise, reverse the order of the digits and add it to the first number
(3) go to step 1

e.g. The number 11 is already palindromised. The number 12, in not but when 12 + 21 is performed the result 33 is a palindrome. We say 12 can be palindromised in 1 iteration.

Now I conject there exists some numbers which defy all attempts to be palindromised. However, I am unaware of any proof of this. If we except that such numbers exist as 'Bazza's conjecture' it is easy to prove that if only one such number exists then an infinite set of such numbers must also exist.

Anyway, the task is fortunately not the prove Bazza's conjecture but to determine the lowest number which seems to satisfy it.

I heard this puzzle many years ago (around 25 is my guess). I believe it appeared in an issue of Omni or Scientific American.

Well I got an answer which stays non-palidromic up to 1000 digits, but I must confess (a) I did it using a brute force computer program, (b) I have no idea why this particular number should generate a non-palidromic sequence, and (c) I have no proof whether or not this particular sequence is *infinitely* non-palidromic. But writing the program was fun, so what the heck.

--
Peter

Rincewind
17-08-2005, 11:17 PM
Well I got an answer which stays non-palidromic up to 1000 digits, but I must confess (a) I did it using a brute force computer program, (b) I have no idea why this particular number should generate a non-palidromic sequence, and (c) I have no proof whether or not this particular sequence is *infinitely* non-palidromic. But writing the program was fun, so what the heck.

That is the object of the exercise. If you like you can PM me the answer but I think it is probably unnecessary. I remember when I looked at this problem all those years ago I wrote some arbitrary length integer routines and a program to look for the number in 6502 assembler language. Which was fun. The program has long since been lost as has the Apple ][+ which ran it. :)

pballard
18-08-2005, 10:01 PM
While on the topic of palindromes, I sent the following to kegless but thought it might be of interest to others.

Discussing palindromes always reminds me of the following puzzle.

Define the act of palindromisation as follows.
(1) If number is a palindrome then it has been palindromised, stop.
(2) Otherwise, reverse the order of the digits and add it to the first number
(3) go to step 1

e.g. The number 11 is already palindromised. The number 12, in not but when 12 + 21 is performed the result 33 is a palindrome. We say 12 can be palindromised in 1 iteration.

Now I conject there exists some numbers which defy all attempts to be palindromised. However, I am unaware of any proof of this. If we except that such numbers exist as 'Bazza's conjecture' it is easy to prove that if only one such number exists then an infinite set of such numbers must also exist.

Anyway, the task is fortunately not the prove Bazza's conjecture but to determine the lowest number which seems to satisfy it.

I heard this puzzle many years ago (around 25 is my guess). I believe it appeared in an issue of Omni or Scientific American.

BTW you can also attempt this for other base number systems...

For base 2, the problem gets a lot easier, and "Bazza's Conjecture" can be proven.

I'm not sure if it's provable for base 3 and higher. It certainly gets more difficult to prove.

--
Peter

Rincewind
29-09-2005, 07:59 AM
The following is the current Macalester Problem of the Week. I usually don't solve these as they don't spark my interest. But then again it could be I only attempt the ones for which I can see a straightforward path to a solution. I wasn't going to attempt this one either but I had some time to kill and was cleaning out my inbox and so I figured I give it a go. Here it is in the format as written by the macpow list owner, Stan Wagon.

Consider the equation (a^a)^n = b^b where we seek solutions in positive integers and a = b = 1 is considered a trivial solution. How many values of n are there for which the equation has no nontrivial solution?

I think other readers here might like to give it a go. It will fill in time until kegless get his problem together. I have a solution and if you would like to cmopare notes send me a PM.

Those of you who are interested in receiving the Macalester College Problem of the Week here's how...

To subscribe to this list, send e-mail to <<majordomo@mathforum.org>> with ONLY the following words in the message body:

subscribe macpow

Kevin Bonham
29-09-2005, 02:23 PM
I like that problem. I hope I'll find time to have a go at it in the next week or so.

Rincewind
12-10-2005, 06:24 PM
It's been two weeks but if you still want to look at the problem avert your eyes now...


The equation is equivalent to

a^(an) = b^b

now for an integer solution there must be of the form of some common factor, c.

We let a = c^p and b = c^(p+q)

where c, p and q are all positive integers we get

c^(pan) = c^((p+q)b)

so equating the indices we get

pan = (p+q)b

now substituting for a and b again and dividing by c^p (ie a) we derive

pn = (p+q)c^q

to avoid trivial solutions we must have c>1. Now one solution to this equation is if we let q=1 and p=c=(n-1) Then we have LHS = RHW = n(n-1).

This means there is atleast one non trivial solution for any n except where n = 2. The reason n=2 is discounted is because then c = n-1 = 1 and we have just derived a trivial solution.The only case left to consider is n=2.

Then we get

2p = (p+q)c^q

For an integer solution we need p+q = 2p (ie p = q) and c^q = 1. This can't work as c^q cannot equal 1. So the other option is q = 0 and c^q = p. But this only works for p = 1, c = 1 which is a trivial solution. Therefore there are no non-trivial solutions for n=2.

Rincewind
12-10-2005, 06:28 PM
The reason the previous solution was put up is there is a new problem this week which I liked. It stumbled on the solution quite by accident. i'll give the harder form of the problem, for the easier form substitute for 7 everywhere you see 31.


Find 31 (not necessarily distinct) positive integers, at least one of which is greater than 1040, such that the sum of their squares is 31 times the product (of the 31 integers).


Of course all integers = 1 is a solution except for the clause that one of the numbers must be > 1040. Have fun.

Kevin Bonham
12-10-2005, 09:46 PM
It's been two weeks

Time flies. Sigh. The answer is neat.

Kevin Bonham
14-10-2005, 06:48 PM
I did something yesterday that seemed very rich with recreational math possibilities - consultants working for Telstra polled me for market research and their polling had an online component. At one point I was given a list of four possible priorities in life (eg "freedom, independence", "time with family", "sense of belonging") and asked to pick which of the four was most and which was least important to me. When I finished this I got another similar question, then another, then another, maybe about a dozen in all, often recycling some of the priorities I had already ranked (but never the same set of four).

I don't know if the idea is to produce a complete ranking or not but this made me think about how effective such an algorithm would be.

Let n>4 be the number of items to be ranked by offering the subject groups of four items from which to pick a highest and a lowest. Some of the questions that could be asked - for different values of n:

* What is the smallest number of selections that could possibly produce a complete sort assuming that the subject never changes their mind about the relative position of two items?

* What is the largest number of selections that could be required to produce a complete sort (assuming ditto)?

* (I think this one is especially interesting). Is it possible to always produce a complete sort without ever re-offering two items between which a preference has been expressed (thus removing the changed-mind issue)? (It is OK to re-offer two items together that were both left in the middle.)

The answers for n=5 are 2, 3 and no.

Rincewind
20-12-2005, 10:22 AM
Here is one of my own design. For m and n in {1,2,3,...}, show that

pballard
20-12-2005, 12:26 PM
Here is one of my own design.

Nice one.

Solution in white:


Assume n>m and n=m+a where a is positive (a=0 is trivial solution)

Use 1 + m/i = (i+m)/i, 1 + n/i = (i+m+a)/i

Now evaluate the LHS and RHS products and they turn out to be equal:

RHS = (1+m+a) / 1 * (2+m+a) / 2 ... * (m+m+a) / m
= (1+m+a) * (2+m+a) ... * (m+m+a) / [1 * 2 ... * m]

LHS = (1+m) / 1 * (2+m) / 2 ... * (m+a+m) / (m+a)
= (1+m) * (2+m) ... * (m+a+m) / [1 * 2 ... * (m+a)]
Factors m+1 ... m+a appear in both numerator and denominator, so cancel...
= (1+m+a) * (2+m+a) ... * (m+a+m) / [ 1 * 2 ... * m ]
= RHS

Bill Gletsos
04-01-2006, 05:18 PM
Worlds largest prime number found.

It is a Mersenne prime known as M30402457 - that's 2 to the 30,402,457th power minus 1.

http://www.smh.com.au/news/world/world-largest-prime-number-identified/2006/01/04/1136050482916.html

Kaitlin
04-01-2006, 05:24 PM
ahhh yes.. infinitly ture :smoker:

Lucena
04-01-2006, 05:52 PM
Worlds largest prime number found.

It is a Mersenne prime known as M30402457 - that's 2 to the 30,402,457th power minus 1.

http://www.smh.com.au/news/world/world-largest-prime-number-identified/2006/01/04/1136050482916.html

I noticed the reporter saw fit to explain what a prime number is. :hmm:

shaun
04-01-2006, 08:34 PM
I noticed the reporter saw fit to explain what a prime number is. :hmm:

Probably a better effort than a reporter in an Indian paper (possibly The Hindu although I cannot source the article) when reporting on a faster method for determining if a number is prime or not.
"Have you ever wondered if there is a fast way of deciding if a number such as 16374529304763752034875492 is prime or not?"

Lucena
04-01-2006, 10:48 PM
Probably a better effort than a reporter in an Indian paper (possibly The Hindu although I cannot source the article) when reporting on a faster method for determining if a number is prime or not.
"Have you ever wondered if there is a fast way of deciding if a number such as 16374529304763752034875492 is prime or not?"

:D

Rincewind
04-01-2006, 11:29 PM
Probably a better effort than a reporter in an Indian paper (possibly The Hindu although I cannot source the article) when reporting on a faster method for determining if a number is prime or not.
"Have you ever wondered if there is a fast way of deciding if a number such as 16374529304763752034875492 is prime or not?"

Ha. Even prime. I get it. ;)

I recall a paper I looked at a few years ago where some indian guys had come up with an algorithm to determine primeness in p-time. I did know enough of the background to know if there was a flaw in their logic. But it seemed ok to my limited understanding. Still, there is p-time and then there is P-TIME.

If anyone is interested I have a hardcopy of the paper and can dig up a reference when I return home.

shaun
05-01-2006, 06:53 AM
Ha. Even prime. I get it. ;)

I recall a paper I looked at a few years ago where some indian guys had come up with an algorithm to determine primeness in p-time. I did know enough of the background to know if there was a flaw in their logic. But it seemed ok to my limited understanding. Still, there is p-time and then there is P-TIME.

If anyone is interested I have a hardcopy of the paper and can dig up a reference when I return home.

The story I paraphrased was reporting on exactly that discovery.

Rincewind
13-01-2006, 04:10 PM
The story I paraphrased was reporting on exactly that discovery.

Was it a few years ago? I've since tracked down the article.

Agrawal, M., Kayal, N. and Saxena, N. (2002) "PRIMES is in P"

Don't know if it has appeared in a journal as I downloaded the article from the website of the Indian Institute of Technology Kanpur.

Rincewind
26-01-2006, 11:13 AM
The Macalester Problem of the Week was a real beauty this week. If your so inclined give it some thought, you won't be disappointed. If you want to ask for clarifications you can do so in this thread but if you want to check your solution please PM me.

Alice, Bob, Charlie, and Diane are prisoners under the supervision of warden Stan. One day the warden takes the ID cards from each prisoner and places them in different lockers in a locker room. The locker room consists of four numbered lockers each with a curtain instead of a door. The curtains are marked 1, 2, 3, and 4. On the next day the prisoners will be taken, one at a time, into the locker room, where they can choose a curtain and look behind it. If they see their own ID card, they are said to be successful. Otherwise, they get to open a second curtain and again, if they see their own ID card, they are successful; otherwise they are failures. As they leave the locker room they cannot communicate with the others. And as they enter the locker room they have no way of telling if a previous prisoner was successful or has looked into any specific locker.

If all four prisoners are successful, then they all be released; otherwise, back to the cells for everyone.

The prisoners know the protocol and can get together in advance to decide on a strategy. For example, they might decide that each should choose two lockers at random. Such a strategy would mean that each prisoner succeeds with probability 1/2, and so the group of four is successful with probability 1/16, or 6.25%. Find a strategy whose probability of success is over 40%.

Rincewind
28-01-2006, 12:45 PM
No solutions as yet. :(

There is a strategy to increase the odds to 1/6. This is for prisoners A and B decide to chose from lockers 1 and 2; and prisoners C and D from lockers 3 and 4.

This picks up the following combinations

A B C D
B A C D
A B D C
B A D C

4 from a possible 4! (24) combinations gives the odds of success as 1/6.

However there is a much better strategy which improves on this A LOT.

qpawn
28-01-2006, 06:03 PM
This is somewhat of a tangent:

I have a degree in straight maths: calculus, optimisation, matrices etc.

I have done some of the hardest maths known to man. But I have one serious limitation: I can only do maths out of a textbook. I cannot problem solve at all.

I nearly failed reasoning and data in year 12 because I had no clue how to do this "pill problem" where you divide up these pills. I had to do a unit with problem solvingt to get my points for the degree. I failed all the problem solving: absolutely zero marks. I got 90% for the book stuff in the unit. I passed the exam. Overall, I scraped home with 56 %.

I don't have any particular dislike of prob;lem solving. I just get nowhere in it. I stare at the problem and my mind is totally blank. I never work out any way to start. I can't see how the problem relates to anything I have worked on in the unit.

This leads me to a criticism of the Victorian senior maths curriculum. In every unit there is at least 66% problem solving. So, where the hell does that leave someone like me? Should I have dropped maths at year 10? You could have the curious outcome of dropping maths at year 10 to avoid problem solving, then finding a degree with mostly book maths and passing it.

I also blame the Victorian maths curriculum from go to woe. Over 13 aggregate years of maths education how many excursions did I do to further my matehmatical imagination? That's right - none. Then I get in my report card " you need to expand your mathematical thinking beyond what's taught including problem solving". Duh. Of course I am no good at expanding my mathematical reasoning after 13 years of "do the 6 textbook qs on the right hand side by Monday".

I repeat what I said. I am the worst math problem solver who has ever lived. I would have more chance of swimming faster than Ian Thorpe.

I haven't really tried any 0of the questions here. I don't know that there is any npoint. For me the killer is starting the problem. If I can get some concrete start on it I have some chance.

Rincewind
28-01-2006, 06:27 PM
I'm a bit biased as my speciality is applied maths. So using math techniques to solve real problems is what I do. I guess one theory is problem solving is about one's brain connecting things which are not obviously related and finding a way to relate them. Perhaps there is a physical brain hard-wiring which cannot be (easily) taught which facilitates this sort of thinking. Maybe your brain just doesn't work that way. I don't know if excursions would help in that case. But that is just a blind guess, so don't take it personally.

As for the VCE maths curriculum. I guess they consider problem solving an integral part of the teaching outcomes. (no pun intended)

Can I ask what line of work you find yoursef in and if you use the skills learned from your maths degree in it?

qpawn
28-01-2006, 06:41 PM
I have not used my maths at all. I am training under a Rhodes scholar to edit books. He runs a group called Learningguild [one word] which has a website if you put it in google.

My theory about my inability to problem solve in maths is that I am a pretty linear thinker - I need everything to be neatly in order from a to b to c before I can do anything with it. Book maths is often like this; problem solving ususally isn't. In my maths I did some difficult applied maths that was similar to computer programming. I used software to form the objective function and constraints and got full marks in a demanding task! Perhaps I think more like a computer programmer than a mathematician despite having a qualification in the latter and none in the former.

Rincewind
28-01-2006, 07:29 PM
My theory about my inability to problem solve in maths is that I am a pretty linear thinker - I need everything to be neatly in order from a to b to c before I can do anything with it. Book maths is often like this; problem solving ususally isn't. In my maths I did some difficult applied maths that was similar to computer programming. I used software to form the objective function and constraints and got full marks in a demanding task! Perhaps I think more like a computer programmer than a mathematician despite having a qualification in the latter and none in the former.

I did a major in Computing Science and my experience is there as many ways of writing a program to accomplish a task as there are programmers in the room. I suspect if there are certain programming types that would suit you (or me or anyone) and others which would not. My problem with programming is maintaining my motivation in doing the trivial part as I usually tackle the tricky piece first and once I have them worked out leave the program half written. :(

eclectic
28-01-2006, 09:21 PM
qpawn might find this link interesting:

http://www.maths.tcd.ie/undergraduate/prospectus/index.php?file=typesofmath

pballard
30-01-2006, 12:01 PM
Alice, Bob, Charlie, and Diane are prisoners under the supervision of warden Stan. One day the warden takes the ID cards from each prisoner and places them in different lockers in a locker room. The locker room consists of four numbered lockers each with a curtain instead of a door. The curtains are marked 1, 2, 3, and 4. On the next day the prisoners will be taken, one at a time, into the locker room, where they can choose a curtain and look behind it. If they see their own ID card, they are said to be successful. Otherwise, they get to open a second curtain and again, if they see their own ID card, they are successful; otherwise they are failures. As they leave the locker room they cannot communicate with the others. And as they enter the locker room they have no way of telling if a previous prisoner was successful or has looked into any specific locker.

If all four prisoners are successful, then they all be released; otherwise, back to the cells for everyone.

The prisoners know the protocol and can get together in advance to decide on a strategy. For example, they might decide that each should choose two lockers at random. Such a strategy would mean that each prisoner succeeds with probability 1/2, and so the group of four is successful with probability 1/16, or 6.25%. Find a strategy whose probability of success is over 40%.


A clarification question... in invisible ink, just to be sure I'm not spoiling anything...


After a prisoner has looked in a specific locker, is the curtain left open?


Please just answer "yes" or "no" for now, I don't want any other clues.