- CiteSeer
Contents
1. preprint D Zeilberger Opinion 36 of Doron Zeilberger Don t ask what can the computer do for me but rather What can I do for the computer http www math temple edu zeilberg Opinion36 html D Zeilberger Opinion 37 of Doron Zeilberger Programming computers to do math is at least as much fun as proving theorems http www math temple edu zeilberg Opinion37 html D Zeilberger Theorems for a price Tomorrow s semi rigorous mathematical culture Notices Amer Math Soc 40 1993 978 981 reprint Math Intell 16 1994 11 14 A S Fraenkel Scenic trails ascending from sea level Nim to alpine chess in Games of No Chance R J Nowakowski Ed Cambridge Univ Press Cambridge UK 1996 W T Gowers The two cultures of mathematics in Mathematics Frontiers and Per spectives V Arnold et al Eds Amer Math Soc Providence 2000 E R Berlekamp J H Conway and R K Guy Winning Ways for Your Mathemat ical Plays Academic Press London 19822. wasted the second half of his life trying to prove the Riemann Hypothesis So let s be more modest and try to find a fast algorithm in log n for k rowed Chomp where k is fixed Even this is probably impossible So let s be even more modest and try to do it for k 3 granted that we already know how to do it for k 2 Even this seems to be impossible at least 172 DORON ZEILBERGER for me So what is a poor mathematician to do The case k 2 is known and trivial while the case k 3 is probably impossible This is just one instance of the human mathematician s predicament of walking the TIGHTROPE BETWEEN THE TRIVIAL AND THE IMPOSSIBLE One may define the cutting edge of research as that x for which doing x e is utterly trivial while doing x e is impossible It is not unlike designing a math exam for my calculus students If I give them the kind of tests that I used to take and even much easier ones they will all flunk On the other hand if Ill ask them to find 2 2 2 3 and problems like that and allow calculators most of them will get an A It is non trivial to design a test that is of just right level of difficulty to produce a bell shaped curve This trivial for k 2 impossible for k 3 curse brings to mind the Three Body Problem One way out of the impossibility dead end is to abandon the quantitative and go to the qualitative as did Poincar This leads to another cultural divide Th
3. N 3 then the initial game position is be De be De be bs be De be bg be De 1 Supported in part by the NSF The Maple package Chomp3Rows is available from Zeilberger s website http www math temple edu zeilberg 168 0196 8858 01 35 00 Copyright 2001 by Academic Press All rights of reproduction in any form reserved THREE ROWED CHOMP 169 The first player may choose to play 4 3 in which case the game position becomes be be be be be Be Be be be de or he may choose to play 2 2 which shrinks the chocolate bar to X X X X X 2 X and so on The Two Cultures of Mathematics Existential and Constructive Nineteenth century mathematicians were honest When they tried to prove that something existed they tried to find it explicitly Then came Hilbert who turned math into theology by proving existence using the Law of the Excluded Middle Of course 20th century mathematicians were forced to cheat because they ran out of computing time and memory allocation in their tiny PC between their shoulders Now that we have much more powerful silicon brains to aid us we can afford again the luxury of being honest and actually finding the desired objects at least whenever it is theoretically possible Of course in finite combinatorics there is no philosophical objection to using indirect arguments but it is still much more satisfying to exhibit the object rather than just proving its ex
4. a b and by P b if a b 2 So we have that P b 1 and P b imply P b and P i i 1 b 1 imply P b Since P 1 is true this completes the induction What Is the Computational Complexity of 2 Rowed Chomp First note that when we fix the number of rows and play k x n Chomp and only let the number of columns n get larger then the naive algorithm is no longer exponential in n but rather is O n But in order to represent a position in k rowed Chomp we only need O log n bits hence the naive algorithm is still exponential in the size of the input for any fixed number of rows and hence doubly exponential for general Chomp On the other hand the algorithm of Proposition 0 for 2 rowed Chomp is clearly linear in the bit size of the input both for deciding whether it is a P or N position and for finding a winning move in the latter case Impossible Dream Find a polynomial time algorithm in the bit size of the input for Chomp In particular such an algorithm would quickly i e in time polynomial in logn and k find the winning first move in a k x n Chomp whose existence is guaranteed by Gale s clever strategy stealing argument Since the above dream is impossible we have to find more realistic dreams We should not be like the fictional Uncle Petros from Apostolos Doxiadis s novel who wasted his life trying to prove the Goldbach Con jecture and like the real Paul Cohen who is rumored to have
5. and type read Chomp3Rows and follow the instructions given there In particular to get a list of the main procedures type ezra while to get a list of all procedures type ezrai To get help on any particular procedure type ezra ProcedureName for example for help with Losers type ezra Losers The main procedure is Losers a k It inputs a symbol a and an integer k and outputs the set of all symbolic losers 6 y in the con jugate notation i e the conjugate partition is 3 2 1 such that a lt k For example if you type Losers a 5 you would get 1 0 2 1 1 0 2 a 2J 3 0 3 3 2 0 3 1 SIs 4 0 4 4 1 4 4 3 0 4 2 4 5 0 5 5 1 3 5 2 a 4 This means that the only losers when a 1 are 1 0 2 and 1 1 0 i e 3 1 1 and 2 2 1 the only losers when a 2 are those of the form 2 a 2 a gt 0 or in the usual notation 4 a 2 a 2 etc My computer Shalosh B Ekhad was able to go as far as k 115 and in order to save time this pre computed table is built in in the procedure T115 Using the pre computed data encoded in T115 a k procedure PTable k extends the table given in WW p 599 from k lt 26 to k lt 115 However note that the table in WW is really implicitly sym bolic even though its authors may not have been aware of it and it looks numeric It turns out that whenever the ith column ends with a 0 it
6. means that there are only finitely many losers with y i but whenever it does not 178 DORON ZEILBERGER end with a 0 it always happens to end with a repeated integer In reality as rigorously shown by Chomp3Rows these two repeated last entries really repeat ad infinitum implying a symbolic loser In addition Ptable 115 extends this all the way to y lt 115 But in order to play Chomp effectively it is not enough just to know what the losing positions are One should also know what is a winning move if you are lucky to be at an WV position This information is furnished by typing WINNERS a b k Here a and b are symbols letters and k is a positive integer This will return a table U where U is the set of symbolic winners arranged in the form of pairs winner loser where winner is a symbolic winner and loser is the winning move to be performed For example typing op WINNERS a b 1 yields table 1 1 1 1 1 O52 3 1 0 0 1 1 a 1 a 1 1 1 2 0 1 0 2 1 0 3 b 1 0 2 1 2 a b 1 1 0 1 1 b 1 1 1 0 which means e g the last term that 1 1 b 1 is a symbolic winner and the winning move is to make it into 1 1 0 You can also play 3 Rowed Chomp fast with the computer by typing PlayChomp POS where POS is the initial position For example try Play Chomp 100000 20000 115 This would be hopeless in a brute force numeric progr
7. of possible positions is finite and the game graph is acyclic This is part of the lovely theory of combinatorial games Readers not familiar with this beautiful theory are strongly advised to read Aviezri Fraenkel s lively and very lucid introduction ST First one draws the game graph of the game This is a directed graph whose vertices are all possible game positions and there is a directed edge between the vertex corresponding to position P and the vertex cor responding to position P if P is reachable from P in one legal move Having drawn that graph you label all the sinks vertices with out degree 0 by P for Previous player wins because if it is your turn to move and you are there then you lost because you can t go anywhere Next label all vertices that have at least one edge leading to a vertex by M for Next player wins Then if you see a vertex all of whose edges lead to N labelled vertices label it P Continue to alternately label the vertices M and P until you finish If the directed graph of the game is finite and has no cycles then it is easy to see that the above procedure always terminates Now let s apply this to Chomp How many possible positions are there The intermediate positions in an M x N Chomp are integer partitions non increasing sequences of positive integers A gt A gt gt A with A lt N and r lt M It is well known and easy to see that their numbe
8. we should not waste our time hammering screws but when we see a screw rather than look for a screwdriver or try to use our mighty hammer to awkwardly hammer it just leave it alone There are so many challenging nails around where our ham mer can be used to advantage that we should keep a lookout for them and try to nail them thereby hopefully improving our hammering skills It would be premature to try and find a computer proof of the Riemann Hypothesis so let s try first to teach the computer how to do research in say 3 rowed Chomp Whenever we have a class of human theorems where the arguments repeat themselves it is a good candidate for teaching a com puter So the main justification for developing the package Chomp3Rows was as an tude in computer generated research As we ll get better and better at it very soon we will be able to tackle the Riemann Hypothesis and other biggies I call people like me mathematical engineers and I am sure that this culture of mathematical software engineering will soon be mainstream making the following dichotomy obsolete The Two Cultures of Mathematics Problem Solvers and Theory Builders W T Gowers TC in a fascinating though somewhat defensive article described these two cultures lamenting that theory builders are still the topdogs and problem solvers the underdogs Luckily this is no longer true In fact he himself a problem solver by his own avowal is a living proof
9. Advances in Applied Mathematics 26 168 179 2001 doi 10 1006 aama 2000 0714 available online at http www idealibrary com on IDEAL Three Rowed CHOMP Doron Zeilberger Department of Mathematics Temple University Philadelphia Pennsylvania 19122 E mail Zeilberg math temple edu Recevied August 25 2000 accepted September 28 2000 A meta pseudo algorithm is described that for any fixed k finds a fast O log a algorithm for playing 3 rowed Chomp starting with the first second and third rows of lengths a b and c respectively where c lt k but a and b are arbitrary 2001 Academic Press How to Play CHOMP David Gale s famous game of Chomp Ch starts out with an M by N chocolate bar in which the leftmost topmost square is poisonous Players take turns picking squares In his or her or its turn a player must pick one of the remaining squares and eat it along with all the squares that are to its right and below it Using matrix notation with the poisonous square being entry 1 1 and the initial position consisting of the whole bar i l lt i lt M 1 lt j lt N then picking the square ig jy means that one has to eat all the remaining squares i j for which both i gt ig and J j hold The player that eats the poisonous leftmost topmost square loses Of course picking 1 1 kills you so a non suicidal player will not play that move unless forced to For example if M 4 and
10. am that implements the naive algorithm But even if you are a numerical person and are only interested in say a table of all losers in a 3 x 115 game of Chomp then find ing and storing the losers and winners symbolically is much more efficient than listing explicitly all 25 266 916 cases If you are also willing to start with non rectangular positions with arbitrarily large top two rows for example 10000000 1000000 115 then the numeric program would be hopeless Very often clever symbolic com putations can save lots of numerical efforts Conversely symbolic computation can learn a lot from numerics in efficiency and speed Hence another challenge for the future would be to bring together the two cultures of computation numeric and symbolic Future Work It would be worthwhile to extend Chomp3Rows to k row Chomp where the lengths of the last k 2 rows are fixed but the top two rows are arbitrary Another interesting problem is to find automatically the more refined Sprague Grundy function rather than just P N status Finally it is hoped that the present methodology might extend to perturbation expan sions of Wythoff s game a k a Fibonacci Nim and other combinatorial games Ch Ma Op36 Op37 SR ST TC WW THREE ROWED CHOMP 179 REFERENCES D Gale A curious Nim type game Amer Math Monthly 81 1974 876 879 P Cartier Mathemagics A tribute to L Euler and R Feynman
11. e Two Cultures of Mathematics Quantitative and Qualitative But proving existence uniqueness and ergodicity will never get us to the moon nor will it predict the planetary orbits for the next ten thousand years For that mathematicians took advantage of the fact that planets are much lighter than the Sun and used perturbation expansion starting with the solution of the 2 body problem This leads to the following The Two Cultures of Mathematics Exact and Approximate The approximate culture gave rise to numerical analysis and its theo retical parent approximation theory It is approximate mathematics that is the most useful in the sciences The whole edifice of Feynman dia grams was designed to find series expansions that go from a trivial 6 Gaussian functional integral to an impossible 3 and beyond functional integral Its practical effectiveness and amazing agreement with experiment is due to the lucky coincidence that the fine structure constant is fairly small roughly 1 137 The default in physics is perturbative and when ever a non perturbative answer is found like in Nati Seiberg s astounding tour de force that lead to the Seiberg Witten invariants and to much more it is a cause of celebration in physics and in this case also in math because of its far reaching implications in topology Speaking of quantum field theory most of it is non rigorous and this brings to mind another cultural divide
12. elty is that the com puter does general reasoning for infinitely many cases by using symbol crunching rather than mere number crunching Another nice thing is that for any fixed cy the computer finds iteratively the P positions Every time THREE ROWED CHOMP 177 it finds a new amp position it evaluates whether this is it by checking using generating functions that all positions with c lt cy are taken care of If this is not the case and it has two consecutive P positions c a B and co amp o 1 Bo it conjectures that co a a Bo is a symbolic loser representing an infinite sequence of P positions and then tries to prove its conjecture If it is unable to prove it it just keeps on going A priori we don t have a meta proof that it would always succeed so unlike WZ the ory this is only a pseudo algorithm But once we succeed we don t have to worry about its pseudoness since once the pudding has came out let s just enjoy it and eat it and not worry whether we were justified in trying out the recipe on a priori grounds This is the beauty of human research It is always a gamble If you know beforehand that your ideas are guaranteed to work out then it is a routine exercise not research A User s Manual for the Maple Package Chomp3Rows As with all my packages it is available from http www math temple edu zeilberg Once you have downloaded it as Chomp3Rows go into Maple
13. istence One of the most gorgeous existence proofs of all times is the following gem of David Gale Ch THE CHOMP EXISTENCE THEOREM In a Chomp game that starts with an M by N chocolate bar with MN gt 1 there exists a winning move for the first player David Gale s One Line Proof Consider the minimal move of only removing the square at the bottom rightmost corner M N If it is a winning move then it is a winning move Otherwise it is a losing move But in the latter case this means that your opponent has a good counter move It is immediate that any position reachable from the new position with MN 1 squares is also reachable from the initial position with MN squares Hence the first player could have gotten to that position right away 170 DORON ZEILBERGER This famous but not famous enough proof can be used in practice as follows I first play with Kasparov pretending that I am Deep Blue and make the above trial move of removing the bottom right corner If he resigns then it is a good move otherwise he would make a good counter move that I can use when I play with you This idea is called strategy stealing in WW How to Find the Winning Move Of course there exists an algorithm for finding the winning move and more generally of deciding whether any given Chomp position is winning or losing and finding a winning move in the former case This is true for all combinatorial games where the number
14. ith a b gt 2 are N What are the smallest positions with c lt 1 that are P We see that all the four cell positions 4 0 0 3 1 0 2 2 0 2 1 1 are M Among the five cell positions 5 0 0 4 1 0 are N since the former can be answered by 1 0 0 and the latter by 2 1 0 We already know from the 2 rowed case that 3 2 0 is P and now we see that 2 2 1 3 1 1 are both 9 since all the positions reachable from them are WV do it So now we have two new members of the amp club 2 2 1 and 3 1 1 But these two factoids entail an infinite number of new memberships in the N club namely 2 a 2 8 1 for all a gt B gt 1 as well as 2 a 2 1 for a gt 1 Also from the fact that 3 1 1 is P we get that 3 2 1 3 3 1 are M as well as 3 a 1 1 for a gt 1 Now it is easy to see do it that these positions exhaust all the possible positions with more than 5 cells and c lt 1 Hence PROPOSITION 1 The only P positions a b c with c 1 are 2 2 1 and 3 1 1 Every N position with c 1 and at least 6 cells is at least in one of the forms 3 2 1 3 3 1 4 4 1 1 0 2 a 2 B 1 gt B gt 0 a B gt 0 where a gt B gt 0 and the winning moves are 174 DORON ZEILBERGER respectively 3 2 1 gt 3 1 1 3 3 1 gt 3 1 1 44 a 1 1 gt 3 1 1 2 a 2 8 1 gt 2 2 1 Note that there turned out to be onl
15. of the respectability of problem solvers having won the Fields medal Since computers are more suited for problem solving than theory building at least for some time to come I believe that problem solving will become more and more important but with a twist It would be a total waste of time for a human to solve a problem directly The mainstream activity of late 21st and 22nd century mathematics would be meta problem solving programming the computer to solve problems that we humans would never have a chance to prove by ourselves So Gowers s two breeds 176 DORON ZEILBERGER of mathematicians will both die out and give place to the Mainsteam Culture of Future Mathematics Programming Computers to do Math Back to 3 Rowed Chomp Since we are restricting attention to 3 rowed Chomp it is more conve nient at least for the computer to look at the conjugate partition i e the column lengths and write down how many 3 s how many 2 s and how many 1 s So from now on position a b c will be denoted by c b c a b if c gt 0 If c 0 and b gt 0 then it will be denoted by b a b and if b c 0 then we simply write a In order not to confuse these two nota tions we will use circular parentheses for the former and reserve square brackets for the latter For example 5 4 2 is 2 2 1 in the new notation while 4 1 is 1 3 and 6 is 6 In the sequel a and 8 will denote general non negati
16. r is So for example when M O N we have an exponential size graph and hence an exponential time and exponential memory algorithm for labelling it and doubly exponential in bit size When M N there is a trivial winning move Choose to chomp at the square at location 2 2 leaving a symmetric L shaped shape and then use the copy cat strategy of aping your opponent s move to the other arm of the L shape Another trivial special case is when we only have 2 rows We have PROPOSITION 0 A 2 rowed Chomp position is P iff it is of the form a a 1 a gt 1 i e where the top row has one more square than the bottom row THREE ROWED CHOMP 171 If a b a b gt 0 is a Chomp position that is winning i e b 4 a 1 then if a b gt 2 a winning move is to go to position b 1 b and if a b 0 to go to position b b 1 Proof We really have two statements here P a a a 1 is a F position for all a gt 1 P b a b is an V position for every a such that a gt b gt 0 and a b 1 Furthermore the winning move is a a 1 if a b and b 1 b ifa b gt 2 The proof is by joint induction P 1 is trivially true The positions reach able from a a 1 are a 1 a 1 and a a 2 a a 3 a 0 each of which are M positions because of P b for b lt a Hence b for b lt a imply P a But also P b is implied by P b 1 if
17. r of cases grows larger and larger as we will see below once we let Shalosh B Ekhad take over One hope would be that there would emerge a pattern valid for arbitrary c that a human would be able to prove by induction or otherwise However this miracle is probably as unlikely as a closed form solution to the Three Body Problem Neither I nor Shalosh were able to detect such a pattern and while Shalosh suc ceeded using the Maple package Chomp3Rows to be described soon to first conjecture and then all by itself prove Proposition cg for cg lt 115 characterizing the positions of the form a b cg no discernible global pattern emerged as a function of cg at least not to us THREE ROWED CHOMP 175 So Why Is It Interesting Gregory Chaitin standing on the shoulders of Kurt G del and Alan Turing taught us that most results are either undecidable or uncompressible Whenever there is a pattern it means that the result is compressible hence was trivial all along and we just did not know it So we humans are des tined to only prove trivial results since any result once proved is trivial for the very reason that we low tech humans were able to prove it The only way to transcend this triviality predicament and to be able to prove semi trivial results is to ask the computer to help us see Op36 Op37 In other words we have this powerful hammer called the computer that can hammer so many different nails Of course
18. this time involving the broader community of people who use mathematics as opposed to full time mathematicians THREE ROWED CHOMP 173 The Two Cultures of Doing Mathematics Rigorous and Non rigorous According to Pierre Cartier s charming and fascinating article Ma pro fessional mathematicians should pay more attention to the latter since Ma p 1 There is another way of doing mathematics equally successful and the two methods should supplement each other and not fight Yet another way is to compromise and do semi rigorous math as I proposed in my cele brated manifesto SR Back to Chomp But the term approximation is not appropriate in this context since everything is discrete A position is either P or N Perturbation is more pertinent An arbitrary 3 row Chomp position can be described as a b c where a b c are the lengths of the top middle and bottom rows respec tively and of course a gt b gt c gt 0 When c 0 we are back to 2 row Chomp so the next thing to try is to characterize the P positions when c 1 Let s try and do it We know that b 1 b 1 is M since chomping the bottom cell the sole cell of the bottom row leads to the P position b 1 b 0 We also know that 1 1 1 is M since the position 1 0 0 is reachable from it We also know that a 0 0 for a gt 1 is M since we can get to 1 0 0 from it From the 2 rowed case we know that a a 0 and a b 0 w
19. ve integers Let s look at two rowed Chomp once again In the new notation the P positions are a 1 These entail that a 0 and a 2 6 are always W positions and we call them symbolic winners We also have the winning move function f q 0 1 1 and f a 2 B fa 1 In order to formally prove the above statement and its analogs for c 1 2 we could use induction like we did in the human ramblings above but we can also prove that the defining property is satisfied The symbolic winners are disjoint from the symbolic losers assume that a 1 a B 2 then 6 1 a contradiction and that their union is the set of all possible positions Using generating functions this is equivalent to the formal power series D owt D A ha 1 w w e w w EN a 7 x x2 having non negative coefficients While I don t have a general algorithm for deciding this for arbitrary formal power series and even for arbitrary rational functions in fact the general problem is undecidable the simple rational functions that show up in this problem all have their denominator 1 x 1 y and then one can use Maple s conversion to partial fractions and use an obvious necessary condition and I don t care whether or not it is sufficient it worked fine for me to prove that this is indeed the case The reader is urged to study the source code of the Maple package Chomp3Rows to see how it is done in practice The nov
20. y 2 members of when c 1 so we did not need induction On the other hand when c 0 the 2 rowed case there were infinitely many members so we had to resort to induction Now we are ready to graduate to the case c 2 From the positions for c 0 we know that b 1 5 2 all belong to W you chomp off the last row and from 3 1 1 P we know that 3 2 2 M and from 2 2 1 P we know that 2 2 2 N Hence the smallest according to the number of cells position is 4 2 2 since all the possible moves lead to W positions Now this fact implies that 4 3 2 4 4 2 are W positions The smallest P position is 5 3 2 which immediately implies that 5 4 2 N and 5 a 3 2 N for a gt 1 The smallest position that is not covered by the above is 6 4 2 and we can directly verify that all the possible moves from 6 4 2 lead to M positions So 6 4 2 P Continuing we get that also 7 5 3 M and we humans would be soon led to conjecture the following PROPOSITION 2 A Chomp position a b 2 is P iff a b 2 Now this is a genuine proposition since it contains infinitely many state ments 4 2 2 P 5 3 2 P 6 4 2 Nevertheless we humans can easily prove it by induction like we did prove Proposition 0 for c 0 the two rowed case Why won t you do it right now We can continue in this vein but I doubt that any human can go beyond c 10 since the numbe
Download Pdf Manuals
Related Search