Solving a question

Question:  Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m>1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ? 

Answer:

N = 1,506,009,006,001,500,000,000 = (2^8)*3*(5^9)*(7^4)*(11^4)*(13^4) (Prime Factorization of N)

Assuming that A and B are the players.The problem reduces to find winning strategy for players A & B with a set of numbers (exponents of prime factors of N in the question) written as a set (8,1,9,4,4,4) = N, where any individual member of set can be reduced whole or part in an individual move (eg: N/p^m can again be factorized and written as a set, which will reduce the exponent of "p" in resultant number by "m") and the first person to reach (0,0,0,0,0,0) wins the game.

If we assume that player A is the first mover, then A can execute a strategy which guarantees his win. (or First mover can win the game if the player plays with the following strategy)

Strategy - 

Step 1: A's first move - Divide N by 13^4 (or equivalently can divide by 7^4 or 11^4 as first move) 

Step 2: Express the exponents of each of prime factors of the resultant number in binary format. For any move by B to reduce the primary factor of any of the number (by division), A could divide by a calculated factor of the number (N) so that XOR sum of the binary representation of all the exponents of factors of the resultant number is 0000 (XOR sum without carry -> 1+1 = 0, 0+0 = 0, 1+0 = 1, 0+1 = 1 eg: 1+1+1+1 =  (1+1)+(1+1) = 0+0 = 0)

Reasoning for the logic: The final desired state of winning position can be represented by 0000 (Winning position). As a first mover, A divides by a calculated number so that the XOR of sum of binary representation of the prime exponents of the resultant number is 0000. Whenever it is A's turn to play, he makes sure that whatever move B makes, player B can never win because he is disturbing a winning position 0000 (set by A in previous move). It can be proved that A can always find moves to move to a winning position (here 0000 represented as the XOR sum of binary representation of individual prime exponents) whatever move B plays. And B can only move to a "non winning" position by his play. 

Step 3: Continue Step 2 until B is forced to execute (0,0,0,0,1,1)->(0,0,0,0,0,1) (or any related non winning move) from where A can divide the resultant N by the lone prime factor to win the game

Demonstration: 

All winning moves can be listed with this logic. But I feel that it is only necessary to state the winning logic for any move by the second player. A possible demonstration of the game is represented below resulting in A winning the game is STEP 5. N0 is the initial number. Ni(A,B) is the result of the i th step of A or B respectively. The above result is quite general and can result in winning solution for any generalized such game.

Note: The solution was inspired from an article on NIM game from the book "Adventures in problem solving" by Shailesh Shirali, published by University Press, India

Steps	Player A	Player B
1	N1A=N0/13^4	N1B=N1A/7^2 (B divides by 49)
2	N2A = N1B/9^2 (Then A divide by 81)	N2B = N2A/2^7 (B divides by 128)
3	N3A=N2B/5^9 (Then A divides by 195,312,5)	N3B=N3A/7^2 (B divides by 49)
4	N4A = N3B/9^2 (Then A divides by 81)	N4B=N4A/3 (B is forced to divide either by 2 or 3 which she does by 3)
5	N5A=N4B/2 = 1 and A wins the game (Then A divides by the remaining lone factor 2 and wins the game)

Light bulbs problem

Imagine a room with 50 light bulbs all connected to separate switches. Switches have two positions ON and OFF which controls the light bulb's state in a similar way. All switches are initially OFF. Now a restless genie is playing with the switches inside the room. Genie fiddles with any of the switches at random and toggles its state. This, the genie does 50 times and then leaves the room. Now the question is - how many light bulbs are ON on an average at the end of the genie episode?

I saw this question in a Quantitative finance discussion board.

I will sketch my solution to the problem and suggest some of properties and generalizations of the question.

Let us label the task of genie randomly playing with switches as a trial. The question asks us to find the average number of bulbs with an odd number of switch toggles after sufficiently large number of trials. (First (odd) toggle of the switch changes its state from OFF to ON, Second (even) toggle changes from ON to OFF and so on..) Let us concentrate on an arbitrary switch and corresponding light bulb. There is 1/50 chance that it will be toggled and 49/50 that it is left untouched in a single instance of an arbitrary trial. This chance is independent of the number of instances and number of trials, and also on what is happening to the other light bulbs. (I had earlier though that a single light bulb cannot be analyzed in isolation as its state at the end of a trial is thought to be dependent on what states other light bulbs are. That is a light bulb cannot be ON say 35 times, if another light bulb is ON more than 15 times in a very very freakish trial. But the average case allows us to disregard this dependence in a single trial and to find the distribution of trials of a single light bulb spread over multiple trials. This independence over large number of trials allows us to focus on state of a single light bulb.

Note that in this solution we seek the probability distribution of number of toggles of a single light bulb spread over multiple trials. Other equivalent method (which was discussed in the forum thread) is non intuitive. Here (in my reasoning) we intuitively think of what happens to a light bulb in many trials (average case calculation) and find the probability of its states.

The process followed by the single light bulb is the binomial one (as discussed - independence criterion over multiple trials allows us to model with binomial distribution) with p=49/50 (prob of no toggle) and q=1/50 (prob of toggle) and n=50. Now the question is to find the probability of this light bulb to have odd number of switch toggles at the end of a trial.  This is the sum of probabilities of 1 toggle, 3 toggle, 5 toggle etc in multiple trials. Let P(n) denote probability of n toggles. Hence Podd = P(1)+P(3)+P(5)+...+P(49)

Podd = C(50,1)q^1p^49+C(50,3)q^3p^47+.C(50,5)q^5p^45+...+C(50,49)q^49p^1

This is calculated as 1/2*((p+q)^50-(p-q)^50), where p and q are as defined.

Podd = 1/2*(1-(48/50)^50) = 0.43505710323898

Now after sufficiently large number of trials, an arbitrary light bulb is ON with probability Podd. Now the distribution ON and OFF light bulbs in each trial is again a binomial distribution. Expected number of ON light bulbs is 50*Podd = 50*0.43505710323898 = 21.7528551619

We find that on average, we expect only less than half light bulbs to be ON after a trials. This may initially seem counter intuitive - How can less than 25 light bulbs be on if I randomly twiddle with switches 50 times in a 50 bulb array? But solution is found to be correct with a simple computer simulation, with the sample code pasted below.


#include
#include

int IMAX = 50; //Global definition of Random MAX to be used in this program
int IMIN = 0; //Global definition of Random MIN to be used in this program

int main()

{
 int bulb[50],i,j,k,m; //All int variables including index are defined
double l=0,n=0; //Variables for calculation of probability
{ //We run the trial 1000 times
 for(j=0;j<1000;j++) { for(i=0;i<50;i++) {bulb[i]=0;} //initialize array before every trial
 for(i=0;i<50;i++) {k = IMIN+rand()%(IMAX-IMIN); bulb[k]++;} //random switching simulation
 for(i=0;i<50;i++) { if((bulb[i]%2)!=0) {l++;}}
}
printf("%lf",l/1000);
}
}


Now to generalize the question with an infinitely large array of light bulbs (or countable infinity of anything), we find that the Podd = (e^2-1)/e^2

What of the outcome of twiddling with a fixed array an very large number of time, say a 50 array with 1000 random switchings? What is the solution in the limit case? I give this problem to the reader who may find it trivial to solve in the above reasoning.

Hari S Warrier

My Bike Rx 135

As a 12 year old boy with an incessant curiosity as is nature for boys with my type scientific bend, I was fascinated with machines in general and automobiles in specific. I remember the times when one of our relatives, who repaired mechanical watches for pleasure, had shown me the workings of an automatic watch. I did not understand anything of substance regarding the working of a mechanical watch then, but I remember me curious as ever making numerous visits to his home, and watching wide eyed, him dexterously dissect watches to its parts and work on it carefully and slowly as if its a piece of very fine jewelry. The watch bug caught me. 

Out of my interest I read a book on watch repair, but the book was for advanced practitioners and thus was only useful for me to understand basic principles of watches and watch repairing. That hobby did not progress much, but I must have spent close to a hundred hours reading and re reading the watch repair book (authored by Br. Berkmans, and published by Kerala Bhasha Institute, 1988), lest some thing useful might come out of it or the familiarity of the pages will help me understand watches better. I continue to maintain an uncommon interest in workings of fine mechanical objects and needless to say if I could afford, would only buy a mechanical automatic watch of great pedigree.

Now coming to automobiles, when I was 12 or 13 I had drawn my version of an assembly line for automobiles as seen in big car plants. My concept was flawed but the essence of automation and progressive step by step building of a complex object in serial order in an assembly line as an idea came to my mind quite easily. I had asked my father (who was a Mechanical engineering teacher at a college) about the concept of torque, momentum etc as soon as I learned it from my 8th text book. With enough knowledge as deemed required, I tore open a mechanical time piece, extracted the parts to make a crude single ratio gear with 1:15 drive ratio, connected this gear to a 1.5 V DC mini motor prime mover and put this all inside a toothpaste cardboard box with wheels as Vicks tops. It worked well, climbing the 30% gradient with ease. I wanted to make sort of crude gear box with selectable set of gears and had worked out the ratios, but my lack of dexterity with small wheels and general lack of larger motive power (9 v motor for better power) prevented me from building a working example of it. I had this set of automobile disassembled, put into a box for many years, and reaching into it under the bed and working on it was my favorite pass time till about age 14, if I was not playing outdoor games with other children.

Then fast forward to year 2006. I was earning salary as software engineer and I wanted to buy bike. Just a sudden decision. We friends, have practically covered every part of Chennai and TN on bus and train, but buying a bike for personal transportation for me was the natural outgrowth of new independence, freedom to spend own money and escape from the travails of public transport in Chennai. First of all, I did not want to buy a brand new bike, I had only a limited use of 1-2 year in mind and was not keen on the huge depreciation in value if I decide to dispose of the vehicle some time in future. I had narrowed down my choice to Yamaha RX series, very specific at that on first instance itself. This is also not surprising given that Yamaha has a cult following among youth in India and a RX100 was the dream bike of many of youngsters for almost a decade. A new RX 135 was retailing for 53k at the time which was the last of the batch of RXs ever sold in India, but this was quite a huge sum for me to spend looking at an uncertain future in the city and with my higher studies plans. I bought 2 weeks of Yellowpage papers to search for used bike ads. So in one of the yellow pages papers I saw a very simple 2 line ad advertising to sell Yamaha 1999 model, 2nd user, for 14k at velachery a suburb near north Chennai. I Immediately called owner, who was of my age, just graduated from college and a typical Tamil guy. fixed up a meeting and took the bus first out of my office to velachery. I reached the house late in the evening. I met owner, his father and mother. They showed me the bike. There was lying a beautiful piece of machinery with Yamaha silhouette, classic color scheme, the same old raw machines look (black in color, Rx 135) but laden with dust and leaning on the side wall. It was evident that bike was lying unused for quite some time. Miraculously it started in first kick, I smelt the exhaust (there were no mechanics other than my mechanical intuition and I was pretty confident of my mechanical sense), revved the bike and took it for a small 'first ride. The bike stalled several times and I had to call owner to start it from one nasty stall, when he sort of managed to start the bike and pushed and rode it back to house. Despite all these, I was in love with the bike and wanted to buy it purely based on sound engine, and good price. A price was immediately negotiated at 13.5k, I fixed up a day and promised to buy the bike. Later I paid the money and rode this bike through heavy Chennai traffic, 15 full KMs of ride to Nungambakkam, where I was then staying. The longest I drove before in a bike was mere 250 m (so a good achievement and again I was confident that good sense of riding in bicycles was enough to learn bikes instantly).

Bike and me meshed well pretty fast. I must have spent close to 3-4k in buying new tires, putting new electricals, battery etc. The bike served me well in Chennai for the entire 1 year. It was a hoot to drive with immense pickup, great sound, and good acceleration in all gears (this is what makes RX series famous). I loved riding the bike anytime of the day, say putting it out from home, taking it out of stand, putting in side stand, admiring its slanted side stand stance all were my pass time hobbies. Bike had some hiccups for sure, it went completely bonkers when it rained heavily and refused to start at all when fully wet. We had a particularly testing time, once after a 12PM movie where me and my friend must have kicked the starter lever in desperation more than a 100 times in torrential rain. But these nagging wet starting issues aside, I had no significant reliability problems to write about. After Chennai stint, I brought it back to Thrissur and drove it in Kerala roads for some months. Here we got a new paint job done at 1250 cost. Then in my Delhi university days, the bike became my companion for many extensive intra Delhi trips and must have run 3-4k KMs in that busy student year alone. I took it from Delhi to Gurgaon, Noida etc many times. Then Gopu my brother, ruined the bike with an ill adviced oil change and the engine froze as the regular side oil was not filled up. We had to change the cylinder and piston. Gopu used the bike in SPA, and had a small accident which dented the bikes front. Bike survived all this and again served me admirably well during my trips from Dwarka to Gurgaon office of Tata Capital Ltd on many occasions.

Finally I returned back to Kerala, and had also bought a new P220 bike. Oldie RX 135 was seen as crude and outdated model and was never in my outright favor again. But I wanted to get the bike back to Kerala for emotional sake and just use it occasionally here for enjoyment. At this time, due to extended periods of non usage, the bike was hard to start and had silencer problem, oil problem, carburetor problem etc. We had even thought of abandoning it all together at the time of shifting to new house. I wanted to unlock its fair price to sell, so it came time to sell the bike. Gopu must have spent many 200rs to refurbish the bike just before some prospective buyer came to look for it. Gopu had also used it sporadically, in my absence, at Delhi. But the bike never regained its Chennai or Delhi glory days. We had put an asking price of 10k only and by Gopu's record, he had received more than 60 responses and more from a classifieds site, all interested in buying the bike. all this in response to our simple classifieds ad soliciting buyers to RX 135. A good bike enthusiast came, a Kannadiga of Tamil origin, who appreciated the bike and bought it for 10k in ready cash. So I had bought it is 2004 for 13.5 k and sold it in 2010 for 10k, a bike of much lesser utility and in a state of low maintenance. Undoubtedly this is proof that the bike still elicit huge demand from bike lovers and it is heartening to see that I once was just one among the fanatical bike lovers and still is, though my tastes have evolved with technology and time and also with purchasing power. Now my dream bike is an R6 which I hope to earn post my masters study in UK/Singapore.

But in my heart of heart, a special corner is reserved for the first full automobile possession of mine, the black Rx 135.

Eddington's cricket Puzzle

                                                          Eddington's Cricket Puzzle

The name of famous British astrophysicist Arthur Eddington was first introduced to me at the age of 10 in my school class VI. We studied a text book titled "Pancha Maha Pratibhakal" (Five Great Talented Men) about the lives of 5 Indian scientists (Prafulla Chandra Ray, C V Raman, Srinivasa Ramanujan. J C Bose and Subrahmanyan Chandrasekhar). Eddington was the antagonist, in the way it was portrayed in the biography of S Chandrasekhar contained in the aforementioned text book. 

I have to say a little about theoretical physicist, Subrahmanyan Chandrasekhar.  Chandra (short name for Chandrasekhar, and the usual way he was addressed) was a prodigy in mathematics and physics. Astounding scientific talent abounded in his family. His maternal uncle was the Nobel Laureate C.V. Raman. At the age of 18 as an undergraduate at the Presidency College Madras, Chandra wrote a paper which developed new applications of Fermi Statistics. As a 19 year old from British India, Chandrasekhar worked out with the help of a handful of texts at his disposal on his long  ship journey to Britain, the first definitive study of evolution of stars. He arrived at the surprising conclusion that 'The life history of a star of small mass must be essentially different from the life history of a star with large mass. For a star of small mass, natural white dwarf stage is an initial step towards extinction. A star of large mass cannot pass into the white dwarf stage and one is left speculating on other possibilities'. He was prudent enough not to publicly state or publish his explorations on the 'other possibilities' (mathematical explorations of relativity theory was in its infancy in 1920's, with the golden age of cosmology almost 3 decades away). Given his formidable mathematical talent, it is quite conceivable that Chandra would have sketched a derivation or at least speculated the inevitability of singularity at the end of life for a star with mass few times the Sun. 

Chandrasekhar on and off worked on his theory about White Dwarfs and after finishing his PhD at the Cambridge University (where Arthur Eddington was professor and the leading authority on stellar evolution), Chandra finally developed an exact theory of star collapse of stars with mass few times that of Sun, and presented the results at the proceedings of Royal Astronomical Society in 1935. This paper discussion was immediately followed by Eddington's paper titled "Relative Degeneracy" which roundly disputed Chandrasekhar's work on White Dwarfs as physically unrealistic. The strangest aspect of this rebuttal paper by Eddington, was the way in which he continuously monitored progress of Chandra's theoretical development of stellar mass limits. The pre-planned denouncement of Chandra's work on the same day of presentation in retrospect, can only been seen as "sheer mean spirited duplicity". 

Some speculate that racial prejudice was to be one of the reasons for such an act. Other scholars state that Chandra's mathematical derivation left grounds for physical speculation on the basis of Quantum Mechanics theory (then in its infancy - but after the triumphant derivation of Electron equation by P.A.M. Dirac, and Von Neumann's work on the mathematical foundations of Quantum Mechanics, the field was on much firmer theoretical grounds) which may have (based on theoretical speculations at the time) precluded such a fate for a massive star. Whatever be the reason, Chandra was bitterly disappointed that none of the "Giants of Science" publicly supported his theory of stellar collapse, but only privately confirmed the correctness of his research. Eddington's intransigence to accept revolutionary extension to the theory of stellar evolution may have triggered Chandrasekhar's decision to leave England. It is ironic that Chandrasekhar received the Noble prize in Physics in 1983 precisely for his work on stellar evolution while Eddington, given his reputation, never won a Nobel prize in his storied scientific career.

I have come across one of Chandrasekhar's earlier papers about Brownian Motion and Stochastic Processes and its application to solution of problems in Stellar Physics, the only paper of his that I could read and understand even a tiny bit. I was wonder struck by the mathematical prowess and clarity of thoughts with deep physical insights and the authoritative lucid mode of presentation of as fundamental a topic as the study of stochastic processes, displayed in abundance in the paper. Chandrasekhar is also known to change his fields of study every decade or so. His modus operandi was roughly 1) Select a new field of study - mostly a disorganized field with a need for theoretical unification 2) Make a literature survey and the current state of the development 3) Study the main problems and make fundamental contributions extending/unifying the theory 4) Write an authoritative book which extends and summarizes all of what is known and developed about the field and then go back to step 1. Possible only for a scientist possessing such a monster mind. He was a true scholar indeed.

After reading more about Eddington, I can now say that with his wealth of results and supreme intellect, he could have been a sure shot Nobel prize winner. (Eddington may have died relatively young for award of Nobel prize). He was also noted for his complete mastery of Relativity Theory and his philosophical speculations about science. He is also the scientist who reportedly replied thus when told by a journalist that only 3 people in the world understood general theory of relativity. His retort was "Who is the third one?"

Little did I know that Arthur Eddington was also a puzzle enthusiast and some of his puzzles were genuine brain twisters. One of the best puzzles I have ever come across is Eddington's Cricket Puzzle. 

First of all the puzzle is as follows.

THE PUZZLE

An Imaginary Scoreboard
Atkins 6
Bodkins 8
Dawkins 6
Hawkins 6
Jenkins 5
Larkins 4
Meakins 7
Perkins 11
Simkins 6
Tomkins 0
Willkins 1
Extras 0
Total 60


BOWLING
Pitchwell: 12.1-2-14-8
Speedwell: 6-0-15-1
Tosswell: 7-5-31-1


CLUES:


1. The Batsmen have scored only in singles and 4s.
2. All of them were clean bowled. No one was caught or run out. There were no no balls or 'short' runs.
3. Speedwell and Tosswell bowled 6 and 7 overs respectively at a stretch.
4. Pitchwell opened the bowling, with Speedwell coming in at the other end for the next over.
5. The overs were of 6 balls each.


QUESTIONS:


1. Which bowler dismissed which batsmen?
2. Who was not out?
3. What were the Fall of Wickets?

I love solving good puzzle, the more logical, the better it is to me. I was thinking on solving cricket puzzle for some days, once I even sketched the solution but some of my answers were not logically sound. My theory was that, this being a beautiful jigsaw of logic, its derivation should occur naturally.

Later I got enough time to solve it and here is my solution.

I have'nt seen any other detailed solutions on the internet and would not want to spoil the genuine thrill of solving this beautiful puzzle. 

Hence I will only provide a brief sketch of solution as follows.

I sketched my solution thus. 

Step 1 - Order of bowling can be deduced.
Step 2- Tosswell's bowling analysis can be found. 
Step 3 - We will get some deductions once the run flurry in Mr Tosswell's overs are taken to its logical conclusion. 
Step 4 - From the deduction in the above step we can work out the runs analysis of each of the batsmen. 
Step 5 - We can then workout the fall of wickets, who got whom out and the last man standing  with straight forward reasoning.

My answers are 

Q 1: Mr Jenkins was dismissed by Speedwell and Mr Bodkins by Tosswell

Q 2: Mr Tomkins was not out

Q 3: Fall of wickets - 6/1, 12/2, 18/3, 23/4, 31/5, 41/6, 44/7, 58/8, 59/9, 60/10