superprismatic Posted November 4, 2010 Report Share Posted November 4, 2010 This problem is related to my earlier post, "Fix The Bad Bits". Find a 1000-long bit stream which satisfies the following relations: Si + Si+85 = Si+327 (mod 2) Si + Si+446 = Si+965 (mod 2) Si + Si+32 = Si+481 (mod 2) Si + Si+106 = Si+933 (mod 2) Si + Si+447 = Si+709 (mod 2) Si + Si+138 = Si+311 (mod 2) Si + Si+308 = Si+343 (mod 2) Si + Si+279 = Si+414 (mod 2) Here, Si is the ith bit of the bit stream. Each relation must be satisfied for all i which make all of its indices fall within [1,1000]. Quote Link to comment Share on other sites More sharing options...
0 araver Posted November 4, 2010 Report Share Posted November 4, 2010 Besides the obvious 0-string, right? Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted November 4, 2010 Author Report Share Posted November 4, 2010 (edited) Besides the obvious 0-string, right? Yes! Thanks, I forgot to mention that. The stream must not be all zeros. Edited November 4, 2010 by superprismatic Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted November 5, 2010 Report Share Posted November 5, 2010 (edited) Yes! Thanks, I forgot to mention that. The stream must not be all zeros. Nice problem. There are less than half a million valid vectors out of 21000 possible binary vectors, which makes this problem very interesting indeed. Thanks for posting this, I enjoy it very much. Here are 3 answers 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 Edited November 5, 2010 by bushindo Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted November 5, 2010 Author Report Share Posted November 5, 2010 Nice problem. There are less than half a million valid vectors out of 21000 possible binary vectors, which makes this problem very interesting indeed. Thanks for posting this, I enjoy it very much. Here are 3 answers 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 Thanks, I'm glad you liked the problem. As usual, I'd like you to give a short description of your attack strategy. I'm especially interested in how you got your ballpark (and correct) estimate of the number of solutions. Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted November 5, 2010 Report Share Posted November 5, 2010 (edited) Thanks, I'm glad you liked the problem. As usual, I'd like you to give a short description of your attack strategy. I'm especially interested in how you got your ballpark (and correct) estimate of the number of solutions. Strategy and a general solution I approached this using linear algebra. We can rewrite the relations in the OP as a single relation by adding them all together and subtracting Si to the other side. Si + Si+85 = Si+327 (mod 2) Si + Si+446 = Si+965 (mod 2) Si + Si+32 = Si+481 (mod 2) Si + Si+106 = Si+933 (mod 2) Si + Si+447 = Si+709 (mod 2) Si + Si+138 = Si+311 (mod 2) Si + Si+308 = Si+343 (mod 2) Si + Si+279 = Si+414 (mod 2) becomes 0 = ( 8 * Si + Si+85 + Si+327 + Si+446 + Si+965 + ......... + Si+279 + Si+414 ) mod 2. (Equation 1) Off course, for certain index i, we need to drop some terms in the equation above as they are not inside the array, and modify the multiplier 8 before Si. The problem is now converted into the matrix equation (A * x) mod 2 = 0 (Equation 2 ) where A is a 1000 x 1000 matrix with 0's everywhere and 1's at the positions indicated by Equation 1. The term x is a binary 1000-dimensional vector that *could* be the solution to the OP. Now, the problem is that we need to find the null-space of A, which can be done by doing gaussian elimination on A in base-2 arithmetic (easier than it sounds). The first time that I did this, A had a null-space with rank 19, meaning that there are 219= 524288 possible vectors that satisfy Equation 2. The issue is that not all of them is a solution to the OP, since in compressing 8 relations to 1 relation in Equation 1, we are under-constraining the problem. In the last post, I simply sampled some vectors from the 524288 possible ones and keep the ones that satisfy the OP. We can go a bit further and find a general solution by constructing A in Equation 2 so that it is no longer under-constrained. That would require a much larger matrix A, though. Another approach is to recognize that all solutions to the OP form a subspace of the rank-19 null-space in the previous paragraph. Some quick code shows that it is a subspace with rank 17, and that all of the 217 solutions can be found with the following S = ( a1 B1 + a2 B2 + ........ + a17 B17 ) mod 2 where a1 = 0 or 1, and B_i is one of the 17 basis vectors that I attach in this post. basis_vector.txt Edited November 5, 2010 by bushindo Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted November 8, 2010 Author Report Share Posted November 8, 2010 Strategy and a general solution I approached this using linear algebra. We can rewrite the relations in the OP as a single relation by adding them all together and subtracting Si to the other side. Si + Si+85 = Si+327 (mod 2) Si + Si+446 = Si+965 (mod 2) Si + Si+32 = Si+481 (mod 2) Si + Si+106 = Si+933 (mod 2) Si + Si+447 = Si+709 (mod 2) Si + Si+138 = Si+311 (mod 2) Si + Si+308 = Si+343 (mod 2) Si + Si+279 = Si+414 (mod 2) becomes 0 = ( 8 * Si + Si+85 + Si+327 + Si+446 + Si+965 + ......... + Si+279 + Si+414 ) mod 2. (Equation 1) Off course, for certain index i, we need to drop some terms in the equation above as they are not inside the array, and modify the multiplier 8 before Si. The problem is now converted into the matrix equation (A * x) mod 2 = 0 (Equation 2 ) where A is a 1000 x 1000 matrix with 0's everywhere and 1's at the positions indicated by Equation 1. The term x is a binary 1000-dimensional vector that *could* be the solution to the OP. Now, the problem is that we need to find the null-space of A, which can be done by doing gaussian elimination on A in base-2 arithmetic (easier than it sounds). The first time that I did this, A had a null-space with rank 19, meaning that there are 219= 524288 possible vectors that satisfy Equation 2. The issue is that not all of them is a solution to the OP, since in compressing 8 relations to 1 relation in Equation 1, we are under-constraining the problem. In the last post, I simply sampled some vectors from the 524288 possible ones and keep the ones that satisfy the OP. We can go a bit further and find a general solution by constructing A in Equation 2 so that it is no longer under-constrained. That would require a much larger matrix A, though. Another approach is to recognize that all solutions to the OP form a subspace of the rank-19 null-space in the previous paragraph. Some quick code shows that it is a subspace with rank 17, and that all of the 217 solutions can be found with the following S = ( a1 B1 + a2 B2 + ........ + a17 B17 ) mod 2 where a1 = 0 or 1, and B_i is one of the 17 basis vectors that I attach in this post. I really like the way you combined the equations to find that dimension 19 null space and sampled to get the dimension 17 one which was actually needed. I would never have thought to do that! That's one more technique which may come in handy in unstable environments (e.g., over the reals) rather than using SVD. Thanks for giving me that tool. I would have just performed gaussian elimination on the full 8000 × 1000 matrix A to start with. That's a very pedestrian way to do it, though. One of the reasons I ask how people approach problems is to learn some new things. Thanks! Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
This problem is related to my earlier
post, "Fix The Bad Bits". Find a
1000-long bit stream which satisfies
the following relations:
Si + Si+85 = Si+327 (mod 2)
Si + Si+446 = Si+965 (mod 2)
Si + Si+32 = Si+481 (mod 2)
Si + Si+106 = Si+933 (mod 2)
Si + Si+447 = Si+709 (mod 2)
Si + Si+138 = Si+311 (mod 2)
Si + Si+308 = Si+343 (mod 2)
Si + Si+279 = Si+414 (mod 2)
Here, Si is the ith bit of the bit
stream. Each relation must be satisfied
for all i which make all of its indices
fall within [1,1000].
Link to comment
Share on other sites
6 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.