tag:blogger.com,1999:blog-3722233.post6882571169428038992..comments2021-10-18T17:43:52.487-05:00Comments on Computational Complexity: Find an 8-digits number such that ....Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-26295686954973896622020-08-26T21:34:00.181-05:002020-08-26T21:34:00.181-05:00D'oh! Never mind my comment.D'oh! Never mind my comment.Bassam Abdul-Bakihttps://www.blogger.com/profile/03467628092593406179noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67590321872987395602020-08-26T21:31:05.250-05:002020-08-26T21:31:05.250-05:00I got the answer by guessing. Never thought about ...I got the answer by guessing. Never thought about the convergence approach. Can someone explain why d_0+...+d_6=8?Bassam Abdul-Bakihttps://www.blogger.com/profile/03467628092593406179noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45316314579871246792018-04-24T18:24:33.799-05:002018-04-24T18:24:33.799-05:00First we exclude possibility of digit above 6, mea...First we exclude possibility of digit above 6, meaning d_0+...+d_6=8. Then for each value of d_7, we're distributing 8 tokens into d_7 (if d_7 appears more than once) or d_7-1 (if d_7 appears once) identical bins, which aren't too many. Each way of distribution gives the digits modulo permutation. Then permutation is obtained by definition and can be verified in O(8).<br /><br />Example, for d_7=3 once distribution is 3 3 2, i.e. digits are 3 3 3 2 0 0 0 0. By definition they should be permuted to 3 0 0 0 3 1 0 4, contradiction.<br /><br />d_7 < 3 or d_7 > 6 could be quickly excluded.Shen-Fu Tsaihttps://www.blogger.com/profile/07625590071644558102noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25652584064914226792018-04-24T12:27:49.100-05:002018-04-24T12:27:49.100-05:00Nice. It seems to converge for any starting choice...Nice. It seems to converge for any starting choice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10021743365615006972018-04-24T06:35:50.075-05:002018-04-24T06:35:50.075-05:00... other nice questions could be:
- is there a f...... other nice questions could be:<br /><br />- is there a fast algorithm to calculate a solution on a number in base B ?<br />- what happens if there are more digits than the base used?<br />- what is the complexity of finding if there is a solution on a given number in which some digits are already specified ...<br /><br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37944743675771562262018-04-24T06:12:27.438-05:002018-04-24T06:12:27.438-05:00Note that for the 8-digit number the solution is u...Note that for the 8-digit number the solution is unique; for larger bases e.g. 16-digit hex numbers, we can have multiple solutions:<br /><br />500001000010022A<br />500001000010103A<br /><br />... but all with 5 distinct digits.<br /><br />Clearly I didn't spend the whole night checking it, but used a 5 minute minizinc program :-)<br /><br />include "globals.mzn";<br />array [0..15] of var int : num;<br />constraint count_eq( num, 0, num[0] );<br />constraint count_eq( num, 1, num[1] );<br />constraint count_eq( num, 2, num[2] );<br />constraint count_eq( num, 3, num[3] );<br />constraint count_eq( num, 4, num[4] );<br />constraint count_eq( num, 5, num[5] );<br />constraint count_eq( num, 6, num[6] );<br />constraint count_eq( num, 7, num[7] );<br />constraint count_eq( num, 8, num[8] );<br />constraint count_eq( num, 9, num[9] );<br />constraint count_eq( num, 10, num[10] );<br />constraint count_eq( num, 11, num[11] );<br />constraint count_eq( num, 12, num[12] );<br />constraint count_eq( num, 13, num[13] );<br />constraint count_eq( num, 14, num[14] );<br />constraint nvalue( num[15], num );<br />%constraint num[1] != 2; << <br />%constraint num[15] != 5;<br />solve satisfy;Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17440913444851515552018-04-24T00:57:00.867-05:002018-04-24T00:57:00.867-05:0000000000
10000008
30000016
41001015
40110033
40012...00000000<br />10000008<br />30000016<br />41001015<br />40110033<br />40012023<br />50011213<br />50101132<br />50101132<br />50101132<br />...rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49661942131329480052018-04-23T14:08:16.419-05:002018-04-23T14:08:16.419-05:00I found a solution by hand search branching first ...I found a solution by hand search branching first on d_7, then on the position for the value in d_7. Not sure how the name of the person who posed the problem would serve as a clueBram Cohenhttps://www.blogger.com/profile/03952121644359153139noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80224983375245566792018-04-23T12:32:41.956-05:002018-04-23T12:32:41.956-05:00I've started from evaluating d_7. It is obviou...I've started from evaluating d_7. It is obviously >1, since if it is 1, the only possible number is 11111111 which is not good. On the other hand, since sum of d_i from 0 to 6 is 8, d_7<=5 (0+1+2+3+4>8). Also, d_6=0, since else we'll need to repeat some number 6 times (as d_7!=6). <br />d_7=2 felt too low. I tried d_7=3. Playing around with it, I got the feeling that even if I manage to put the numbers, I'll use all of 0,1,2 thus violating d_7 rule. For d_7=4 I found something close to the answer pretty fast:<br />40______ -> 40_1____<br />d_5 got to be 0: <br />40_1____ -> 4001____<br />Putting 2 into d_0 and thus 1 into d_2:<br />4001____ -> 4001_1_2<br />Now we can put d_1=3 and d_3=1, acquiring<br />4001_1_2 -> 40011132<br />The problem is, I've used 0,1,2,3,4 which means d_7=5. Luckily, it can be fixed easily<br />50101132Anonymoushttps://www.blogger.com/profile/14163326659666838764noreply@blogger.com