superprismatic

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.

By this logic, the answer to part 2 must be 1 because once you make a circle, another circle is not a different regular elliptical. Is that correct?

1. Infinite. You can make one square an infinite number of ways -- the size of a face; and you can make an infinite number of different sized triangles. 2. Infinite. You can make two disjoint circles an infinite number of ways and an infinite number of different sized concentric circles. Yes, they are both of size Aleph-one.

Yes! Thanks, I forgot to mention that. The stream must not be all zeros.

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].

Yes, but I don't know how that helps solve the problem.

I have take a 1000-long bit stream which satisfies the following 11 relations (Si is the ith bit of the bit stream): Si + Si+11 = Si+48 (mod 2) Si + Si+22 = Si+96 (mod 2) Si + Si+44 = Si+192 (mod 2) Si + Si+30 = Si+275 (mod 2) Si + Si+244 = Si+297 (mod 2) Si + Si+214 = Si+341 (mod 2) Si + Si+88 = Si+384 (mod 2) Si + Si+60 = Si+550 (mod 2) Si + Si+488 = Si+594 (mod 2) Si + Si+428 = Si+682 (mod 2) Si + Si+176 = Si+768 (mod 2) and performed the following modification on it: Each bit has either been flipped (with probability 0.35) or left as is (with probability 0.65) independently of the other bits. The resulting stream is: 00010000110111101011001000011000010110000101001001 00011100000010100101001101010110011011101111101110 10100101010010000101111011101011010110001111001000 10010110100111100111110110000101000010010101100100 10010001010110110101010110111001010011011111111001 11101001111101111001000111010100111100101010001111 11100011011101010001110010000011111101011100101010 00110010110110001101001001000000100001110101001010 10000010011110001111111100100110010010000110110111 11110010111110101100000000111011010011001101010001 10100000001011001000100111101010001000001000001001 10111001111110001111101001100001011010010100110000 01110000101001111000111000111011010000110111011110 01100101001100000101111010100000101000111100001000 10000111110100001111000010100100101111001100011110 00101010110010010110100100100101011010100000110101 01011000001011001111010111001110100101000010111110 00001101100101100011100000110010010010111110001010 01010001000000011100000000011110010110101011001100 10011100001101100011100100011101001000010111001101 [/code] Find the original stream.

Thanks. I also wrote a quick subroutine to carry out the steps between choices. I was in a bit of a hurry, so I just made random choices thinking that the search tree would bush too much. I didn't realize that the number of empty holes grows quickly. Even with my random choices, I got to 55 in a few seconds! Thanks again for the nice explanation.

Please give a heuristic explanation of how you did this. I'm pretty sure you wrote a program to find your solution(s), so you must have thought up a strategy for it. I would appreciate a quick outline of the strategy.

Bushindo and araver got it!

I can't tell you that you are right unless you answer both parts of the question correctly.

Great, that's right! Now I've got a similar puzzle in 4 dimensions. Take a gander!

The first 625 letters of the beginning of a famous American literary piece are written into a 5×5×5×5 hypercube, H, in the following way: H(1,1,1,1) gets the first letter, H(2,1,1,1) gets the second letter, H(3,1,1,1) gets the third letter, H(4,1,1,1) gets the fourth letter, H(5,1,1,1) gets the fifth letter, H(1,2,1,1) gets the sixth letter, H(2,2,1,1) gets the seventh letter, H(3,2,1,1) gets the eigth letter, H(4,2,1,1) gets the ninth letter, H(5,2,1,1) gets the tenth letter, H(1,3,1,1) gets the eleventh letter, H(2,3,1,1) gets the twelfth letter, ... etc. In other words, the indices increment in a reverse odometric manner. Then, for each of the 4 dimensions, the 5 faces (which are cubes) are permuted amongst each other, using a 5-long permutation -- the same permutation is used for each dimension. The resulting hypercube of letters, written out in the same reverse odometric manner, is NTDAIDEMIATHFRORAADNREEAR DLAEMREEONOMNHWSNGLEANTEH TOGTHROBROAIOVWOUASDIHNYL TLLSOREEONSORWOHEOTRWFROR SECAEOROSFOMWRFURKSSOOMBY ITMWENTHAFLLHIREDILLEFEMD ELEFRFOTEBICATSEVRNSROTRE RMEEVANOERELNMAORRFEHEESS URLCENTTIANGTILRPHUPACOEF TACREUSIRNESDHTUNSDAENIKL RENOLLEWIHMEOULTEGTOOROFF NGPIPDESDUDDIONNARYLEAEND REHDTWHAYREUOCNIGINDAMPNO URNCDSVIUOMAVRETAANIQUNAY DWKNAYOERAIPIELEAEWDERODN POSUTEFNHTROEWRHOTGSTIUHG THHDERREOMRELOOISYWIRLAEG LYNTCMEIERGMHNITIDSIAHOER YITDEMBNEGNDEARRAEAPHSECA KDLAEMBEECRIMEBEBNHTSITAW INAPPMYGTAORSTIDTEERTTIUM SATIHOTNNDMBCAHLYRNOOOEDR NGPIPFSAOSTHNYLTAMAECAEER SSRITVIOEMMYGTAOOEDRMBCAH GRPNIINAPPONOEMAPLRYNTEEG [/code] What is the literary piece? What is the permutation needed to unscramble the above hypercube of letters?

Here's a square array of letters with the rows and columns numbered: 123456789 1 AGDICBHFE 2 DAGCFEBIH 3 GDAFIHECB 4 BHEADCIGF 5 HEBGAIFDC 6 IFCHBAGED 7 CIFBEDAHG 8 EBHDGFCAI 9 FCIEHGDBA [/code] We can reorder the rows and columns with the same permutation to convert the above array into one with constant diagonals: [code] 398274165 3 ABCDEFGHI 9 IABCDEFGH 8 HIABCDEFG 2 GHIABCDEF 7 FGHIABCDE 4 EFGHIABCD 1 DEFGHIABC 6 CDEFGHIAB 5 BCDEFGHIA Find a permutation which, when applied to both the rows and columns of the binary array 11111111112222222 12345678901234567890123456 1 10010111010010000101100111 2 00011100101001101001100111 3 00101011000101110011110001 4 10011010100100110010111001 5 01110011110001011000010110 6 00010101100111101011001001 7 00110101110110111010000001 8 01011001010111000010111100 9 10011111100001000111001010 10 11011001101000000100101111 11 10101001101010000110011011 12 11001100010101101110000110 13 11101110100010010101110000 14 00100110110011110101001010 15 11001011011010100001011001 16 11010110111000011001010100 17 00000111011011111100010100 18 01100111000101010010001111 19 11101000001110001100110110 20 01000000111101001111110100 21 11100010010110110010100110 22 01101000001110101101101010 23 00010100011100110111001011 24 01110010101000101010111001 25 10111101001001011001010100 26 10100000011111011100101001 [/code] will convert it into [code] 10001010011010111101000101 11010100101111000110100001 10001111000110111000000111 10110110011001101011000100 11101000101001101000111100 11100100010101100000111110 01101001010111011101001000 10101100011110110101000010 11001001110000000111111001 00000010010111111110110001 01011001011001010011000111 10010101110100001011001101 10010000000110110111001111 10010111001001010000111101 00110111110011000110101000 01001110100011101100011100 00101001111100001011010110 01110101101000101110010010 11000111100100010001110110 01011000110110001001111010 00100011001110010011111001 00110111001011110110100000 01110010111000100100001111 11011100000010001001111011 00111010100101110000110011 01101011101001011110000010

Correct. Nice Going! I'll be posting a much more difficult related problem soon. I hope you try it.

Here's a square matrix of letters with the rows and columns numbered: 123456789 1 AGDICBHFE 2 DAGCFEBIH 3 GDAFIHECB 4 BHEADCIGF 5 HEBGAIFDC 6 IFCHBAGED 7 CIFBEDAHG 8 EBHDGFCAI 9 FCIEHGDBA [/code] We can reorder the rows and columns with the same permutation to convert the above matrix into one with constant diagonals: [code] 398274165 3 ABCDEFGHI 9 IABCDEFGH 8 HIABCDEFG 2 GHIABCDEF 7 FGHIABCDE 4 EFGHIABCD 1 DEFGHIABC 6 CDEFGHIAB 5 BCDEFGHIA Find the permutation which, when applied to both the rows and columns of the following matrix, will convert it into one which has constant diagonals: 11111111112222222 12345678901234567890123456 1 AZSJKCPTYQFDRVBHXOEWNLMGUI 2 BATKLDQUZRGESWCIYPFXOMNHVJ 3 IHARSKXBGYNLZDJPFWMEVTUOCQ 4 RQJABTGKPHWUIMSYOFVNECDXLZ 5 QPIZASFJOGVTHLRXNEUMDBCWKY 6 YXQHIANRWODBPTZFVMCULJKESG 7 LKDUVNAEJBQOCGMSIZPHYWXRFT 8 HGZQRJWAFXMKYCIOEVLDUSTNBP 9 CBULMERVASHFTXDJZQGYPNOIWK 10 KJCTUMZDIAPNBFLRHYOGXVWQES 11 VUNEFXKOTLAYMQWCSJZRIGHBPD 12 XWPGHZMQVNCAOSYEULBTKIJDRF 13 JIBSTLYCHZOMAEKQGXNFWUVPDR 14 FEXOPHUYDVKIWAGMCTJBSQRLZN 15 ZYRIJBOSXPECQUAGWNDVMKLFTH 16 TSLCDVIMRJYWKOUAQHXPGEFZNB 17 DCVMNFSWBTIGUYEKARHZQOPJXL 18 MLEVWOBFKCRPDHNTJAQIZXYSGU 19 WVOFGYLPUMBZNRXDTKASJHICQE 20 EDWNOGTXCUJHVZFLBSIARPQKYM 21 NMFWXPCGLDSQEIOUKBRJAYZTHV 22 POHYZREINFUSGKQWMDTLCABVJX 23 ONGXYQDHMETRFJPVLCSKBZAUIW 24 UTMDEWJNSKZXLPVBRIYQHFGAOC 25 GFYPQIVZEWLJXBHNDUKCTRSMAO 26 SRKBCUHLQIXVJNTZPGWOFDEYMA [/code] In other words, after the permutation is applied, the matrix becomes: [code] ABCDEFGHIJKLMNOPQRSTUVWXYZ ZABCDEFGHIJKLMNOPQRSTUVWXY YZABCDEFGHIJKLMNOPQRSTUVWX XYZABCDEFGHIJKLMNOPQRSTUVW WXYZABCDEFGHIJKLMNOPQRSTUV VWXYZABCDEFGHIJKLMNOPQRSTU UVWXYZABCDEFGHIJKLMNOPQRST TUVWXYZABCDEFGHIJKLMNOPQRS STUVWXYZABCDEFGHIJKLMNOPQR RSTUVWXYZABCDEFGHIJKLMNOPQ QRSTUVWXYZABCDEFGHIJKLMNOP PQRSTUVWXYZABCDEFGHIJKLMNO OPQRSTUVWXYZABCDEFGHIJKLMN NOPQRSTUVWXYZABCDEFGHIJKLM MNOPQRSTUVWXYZABCDEFGHIJKL LMNOPQRSTUVWXYZABCDEFGHIJK KLMNOPQRSTUVWXYZABCDEFGHIJ JKLMNOPQRSTUVWXYZABCDEFGHI IJKLMNOPQRSTUVWXYZABCDEFGH HIJKLMNOPQRSTUVWXYZABCDEFG GHIJKLMNOPQRSTUVWXYZABCDEF FGHIJKLMNOPQRSTUVWXYZABCDE EFGHIJKLMNOPQRSTUVWXYZABCD DEFGHIJKLMNOPQRSTUVWXYZABC CDEFGHIJKLMNOPQRSTUVWXYZAB BCDEFGHIJKLMNOPQRSTUVWXYZA