```Date: Feb 28, 2013 4:51 AM
Author: Martin Brown
Subject: 8x8 bit patterns

I have a little puzzle where I think the answer is that it is not possible but having tried all the tricks I can think of cannot prove it.The problem arises from considering the possible bit patterns in an 8x8 JPEG encoding square and searching for one that includes all possible states for subsampling up to 2x2 - that is 2x1, 4x1, 2x2ie 0000, 0001, ...., 1111and00  00  00 ........... 1100, 01, 10,            11It would be really nice if it did 1x4 as well.It is obvious that the 4x1 subsampling requirement means that the final solution if it exists must be a permutation of the nibbles 0,1,...,15It is also obvious that taken as pairs and interpreted as 2x2 subsampled there are 16x15 possible states of which those involving 0,5,10,15 will have duplicate 2x2 subsampling patterns if used together. Using any pair taken from this set prevents a solution.ie4x1		2X20	00|00   0001  	15	01|01   0001	1Whereas4x1		2x20	00|00	0000	01	00|01	0001	1The best I have been able to obtain by a directed brute force attack is any number of solutions getting 11/15 of the 2x2 states and all of 4x1. I am still not convinced my algorithm is working correctly.This is based on computing the 2x2 patterns for all the pairs and then combining them efficiently to try and maximise coverage in both domains.The 4x1 pair {0,7} is represented as 2x2 {1,3} and bitmasks are used to compute worthwhile continuations and cull all branches already worse than existing solutions.A complete solution should represent 0..15 in both domains 2x2 and 4x1. But alas I can't find one :(I can't help thinking there should be some clever parity based argument to show that it is impossible to do better. Any suggestions?Thanks for any enlightenment.-- Regards,Martin Brown
```