tag:blogger.com,1999:blog-3722233.post8085135334376235626..comments2024-07-08T08:20:09.315-05:00Comments on Computational Complexity: A nice dice problem- Part ILance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-15982492277307391232024-01-08T06:15:01.789-06:002024-01-08T06:15:01.789-06:00I'd say well known since you can buy a pair of...I'd say well known since you can buy a pair of Sicherman dice, say at https://www.mathartfun.com/dSpecial.html.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36507383216629385552024-01-08T01:46:44.372-06:002024-01-08T01:46:44.372-06:00Z3 found a solution in <1 second. https://ideon...Z3 found a solution in <1 second. https://ideone.com/oXXw7C<br /><br />Die 1<br />1 2 2 3 3 4 <br />Die 2<br />1 3 4 5 6 8 Elfarouk Harbnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89274589104450917802024-01-07T21:56:30.457-06:002024-01-07T21:56:30.457-06:00You're right -- I was solving the wrong proble...You're right -- I was solving the wrong problem. (I misread the question as "is there a set of non-uniform probabilities for the usual labels" instead of "is there a set of non-standard labels with uniform probabilities")Clément Canonnenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74538307587486786562024-01-07T21:43:50.947-06:002024-01-07T21:43:50.947-06:00(a) A hint is to think about how irreducible facto...(a) A hint is to think about how irreducible factors of the polynomial<br /> (z^1+z^2+z^3+z^4+z^5+z^6)^n with rational coefficients might play a role in this.<br /><br />(b) A solution is (1,3,4,5,6,8) and (1,2,2,3,3,4).<br /><br />(c) In terms of hardness of problems, our good friends, Don Knuth, Oren Patashnik and the late Ron Graham<br />considered it to be an exam type problem -- serving nicely as a take home exam (not for in-class assessments under time pressure).<br />In terms of source; (not sure about the paper mentioned but it appeared in GKP (Concrete Mathematics) as exam problem 36 in Chapter 8, on page 431. The way it has been phrased in this post, might be slightly more challenging because no initial configuration was provided.Evangelos Georgiadisnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37423117517330096802024-01-07T21:23:48.549-06:002024-01-07T21:23:48.549-06:00(Bill) Why that polynomial? You are correct that t...(Bill) Why that polynomial? You are correct that the answer involves polynomials. But the problem is asking if there is a_1,...,a_6,b_1,...,b_6 such that (x^{a_1} + ... + x^{a_6})(x^{b_1}+...+x^{b_6}) is equal to (x^1 + ... + x^6)^2 but not in the obvious way. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8328245816046563382024-01-07T21:21:18.670-06:002024-01-07T21:21:18.670-06:00Thanks for the link! I didn't know it was ther...Thanks for the link! I didn't know it was there since I didn't know they were called Sicherman dice. I think having a Wikipedia link is a necc but not suff condition for a problem to be well known. So is this dice problem well known? The Jury is still out. Lance didn't know it, so thats evidence for no. (OH- This is bill.) Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39970691702019064552024-01-07T21:19:59.449-06:002024-01-07T21:19:59.449-06:00(Bill) The labels on the dice have to be POSITIVE ...(Bill) The labels on the dice have to be POSITIVE naturals, so you have not solved the problem as stated.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4828168530633067672024-01-07T20:26:10.090-06:002024-01-07T20:26:10.090-06:00Unless I have made a mistake (very possible/not un...Unless I have made a mistake (very possible/not unlikely), this is impossible: this corresponds to factoring the polynomial $x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9+3x^{10}+2x^{11}+x^{12}$ as the product $p(x)q(x)$ of two degree-6 polynomials with no constant term and positive coefficients. And there is only one factorization of this type...Clément Canonnenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79235716651193403522024-01-07T19:57:26.266-06:002024-01-07T19:57:26.266-06:00Die 1: 0,1,2,3,4,5
Die 2: 2,3,4,5,6,7Die 1: 0,1,2,3,4,5<br />Die 2: 2,3,4,5,6,7EGnoreply@blogger.com