Monthly Archives: October 2013

sol 426

Posted on by

During this several months trek of Curiosity, I have noted how difficult it is to track its progress by viewing the raw image gallery. It seems that the progress of a hundred meters or so completely changes the perspective of the near and mid ground, so that it’s difficult or impossible to place the future or past position of Curiosity in the images made on successive sols.

Nevertheless, it is always rewarding to review these images, and sol 426 presents some very interesting vistas, which do illustrate the problem I mention, since it seems that there was a displacement during that sol between two sessions of image taking.

First of all, there was a series of 22 images from the Mastcam which form a nearly 360 degree panorama encompassing a high resolution view of the “riverfront” as I think of the edge of the low lying dune fields fronting Mt. Sharp, since this is what its appearance suggests.

You can click on it, and it is not too unwieldy, since it is skinny. If you pan along it at full size, it’s just rocks, rocks, rocks! But that’s Mars. You can see a lot of detail, as Curiosity is much closer to the “river” than it was at Glenelg, and this is very exciting, if you’ve been following the mission.

These images were recorded around 2013-10-17 19:35:44 UTC, and make an interesting comparison to a lower resolution, or really lower magnification, Mastcam view made around 2013-10-17 23:24:38 UTC, so about 4 hours later, apparently after another short traverse. Here is that view.

If your anything like me, you’ll find it very difficult to correlate these two ( composite ) images, taken just hours apart. There is a link, though, in several NAVCAM images taken around the same time as the second, smaller, panorama. Here is a portion of one of them, truncated to emphasize its correlation with the panoramas.

Now here is an approximate overlay of that same NAVCAM image, further truncated, on top of the second panorama, which was reduced in scale to match ( at full size. )

Finally, here is a side by side comparison, again with the NAVCAM image at the same scale, with the high magnification panorama. I’ve marked some correspondences, as I see them, but note these are distorted by the displacement in position between the acquisition of the images. I would just comment that you would never spot this correspondence with a casual perusal, since you would naturally try to correlate the foregrounds of both images.

Well, there’s more where that came from! So … later.

On the road

Posted on by

The foothills of Mount Sharp have been a backdrop for Curiosity’s movements since it landed, and it’s movements in the first few months did not significantly change the perspective. Now with the traverse to the southwest towards a “base camp” for the ascent of Mount Sharp, we can see a shift in the view.

Here is a section of a recent sol 421 panorama compared with the corresponding portion of a sol 3 panorama made at the landing site. As I estimate them, the blue lines are radials from the landing site, and they appear as vertical lines in the sol 3 panorama, and the same for the green lines and the sol 421 panorama.

Here is the Hirise view of the location, which is the basis for some of the progress maps periodicially published on the MSL web page. I’ve drawn in an estimate of the lines of sight in the panoramas, as seen from above.

 

Spot it! … a combinatoric cornucopia

Posted on by

I came across the Spot it! card game a few months ago, and it didn’t take long to start wondering about the mathematics of the deck design. Here is the game with three cards displayed. Every pair of cards has exactly one matching pair of symbols, as illustrated here where the three pairings share a chess knight, a cat, and a dog.

There are 8 cards that have knights on them, and a little consideration shows that the 8×7 other symbols on these cards must be unique ( since each pair of cards has one match. )  Then there must be 57 symbols, on this fact alone. If there are 57 cards, then each of the 57 symbols can be accounted for if they each appear on 8 cards.

I got this far, then found the blog, BOWMAN IN ARABIA with the article, Math Circle Problem: Analysis of the Game “Spot it!”,  which outlines an algorithm for finding decks of PX(P+1) + 1 cards and the same number of unique symbols, with P+1 symbols on each card, for P prime.

I added a note about a solution for P=4, and I surmised that P = 2N works along with P prime. I wrote ( and refined,  with considerable effort, ) a “brute force” search program, and verified that P=6 does not yield a solution, and proceeded to P=9, expecting the same. However, this search yielded numerous solutions. ( I let it run for several days, thinking that it would stop at 7! solutions, based on simple extrapolation. However, it was still going strong at that point and I terminated the run. ) I then surmised that PN + 1, P prime, yields solutions, and this seems to be corroborated from what I read, and is evidently related to the “Sylow subgroups” of the Symmetric groups (aka permutation groups. )

You could say that’s the end of it, but there are a lot of “pfathinatin” details to be observed in the structure and properties of these solutions. Let us first return to the commercially available SPOT IT! deck, and then consider some other simple cases.

In fact, there are 55 cards in this deck, and it is observed that it must be obtained simply by removing two cards from the mathematically ideal solution. This is verified by the following image of a canonical arrangement of the cards, with the two “missing” cards ( they are not there when you buy them! ) … supplied by the logic explained:

On the left is the arbitrarily chosen ABCDEFGH card, whose 8 symbols are given canonical status. Note that in each of the 8 rows of 7 cards, each card contains the same symbol from the “key card” , with A=knight, B=balloon, etc. ( The “key symbol” is given upright orientation in each case. )

The top row defines 8 canonical sets of 7 symbols, ( excluding the knight, )  one of which must appear in each of the cards of every row. The second row, or “B=balloon” row, arranged in arbitrary order, defines a canonical index into each of these sets, based on the row position of its member symbols. This index is important in algorithms for constructing “solutions”,  i.e. valid SPOT IT! decks.

Then … each subsequent row is arranged so that the symbols matching the left-top-most card, the second key card, are in the same order as the “B=balloon” row, thus forming a 7X7 array of cards, excluding only the “A=knight” cards, indexed in a canonical way by the seven non-knight symbols on the two key cards. Wonderful!

Well, note that we come up with two “holes” in a very natural way, and can fill them in according to the symbol missing in their row from each of the “A row” cards, and this has been done, at great cost of manual labor.

General Principles

But let us return to a simpler case to illustrate some general considerations. The very simplest nontrivial case is 3 ( 2X1 + 1 ) cards with 2 symbols on each card, AB, AC, BC. However, this is a bit too simple, and the next case of 7 ( 3X2+1) cards with 3 symbols on each card is interesting but not too complicated.

It suffices to illustrate the geometric model, where each card is a vertex of a 6-d simplex ( noting that a 3-d simplex has 4 vertices, e.g. ) and each symbol corresponds to a 2-d simplex, or triangle, connecting all of the vertices representing cards with the same matching symbol.

Thus, the whole problem of constructing a deck of N X (N+1)+1 cards is seen to be equivalent to an EDGE COLORING problem on an N X (N+1)-simplex. We require the edges to be colored ( in this case) with 7 colors, such that the edges of 7 2-simplexes ( triangles) have the same (unique) color, and each vertex is shared by 3 of these.

Not sure where that gets us, but it does seem to be a helpful visualization.

Duality

In consideration of the idealized SPOT IT! deck, it appears that just as every pair of cards shares a unique symbol, so every pair of symbols shares, or appears on, a unique card. Thus every deck can be specified in a dual fashion, with a solution that corresponds to itself or another deck.

For the case of N=3 we can see a SELF-DUAL solution if we label each card with a,b,c,d,e,f,g as follows

a=ABC b=ADE c=AFG d=BDF e=BEG f=CDG g=CEF

… indicating which symbols occur on each card. Then the symbols can be specified by the set of cards on which they occur:

A=abc B=ade C=afg D=bdf E=beg F=cdg G=cef

… and we see that we have the same specification with interchange of upper and lower case. I promise you that I typed these out according to the definition, and not by rote! For higher values of N, the solutions are not all self-dual, and I haven’t explored the necessary arrangements.

Permutation of symbols

It seems clear that any solution derived by permuting the symbol values of an existing solution is valid, and will not necessarily involve the same cards, as defined by the symbols appearing on them. In the case of 7 symbols appearing 3 times each on 7 cards, we can easily permute them and “orthonormalize” them to arrive at the 7! = 5040 different results:

$ for i in `perm ABCDEFG`; do tr ABCDEFG $i <ABC | orsort; done | sort | uniq -c

168 ABC ADE AFG BDF BEG CDG CEF
168 ABC ADE AFG BDG BEF CDF CEG
168 ABC ADF AEG BDE BFG CDG CEF
168 ABC ADF AEG BDG BEF CDE CFG
168 ABC ADG AEF BDE BFG CDF CEG
168 ABC ADG AEF BDF BEG CDE CFG
168 ABD ACE AFG BCF BEG CDG DEF
168 ABD ACE AFG BCG BEF CDF DEG
168 ABD ACF AEG BCE BFG CDG DEF
168 ABD ACF AEG BCG BEF CDE DFG
168 ABD ACG AEF BCE BFG CDF DEG
168 ABD ACG AEF BCF BEG CDE DFG
168 ABE ACD AFG BCF BDG CEG DEF
168 ABE ACD AFG BCG BDF CEF DEG
168 ABE ACF ADG BCD BFG CEG DEF
168 ABE ACF ADG BCG BDF CDE EFG
168 ABE ACG ADF BCD BFG CEF DEG
168 ABE ACG ADF BCF BDG CDE EFG
168 ABF ACD AEG BCE BDG CFG DEF
168 ABF ACD AEG BCG BDE CEF DFG
168 ABF ACE ADG BCD BEG CFG DEF
168 ABF ACE ADG BCG BDE CDF EFG
168 ABF ACG ADE BCD BEG CEF DFG
168 ABF ACG ADE BCE BDG CDF EFG
168 ABG ACD AEF BCE BDF CFG DEG
168 ABG ACD AEF BCF BDE CEG DFG
168 ABG ACE ADF BCD BEF CFG DEG
168 ABG ACE ADF BCF BDE CDG EFG
168 ABG ACF ADE BCD BEF CEG DFG
168 ABG ACF ADE BCE BDF CDG EFG

… showing that the 5040 permutations of the symbol tags, ABCDEFG, result in 168 repetitions each of 30 different 7 card decks, each a solution of the SPOT IT! specification.

ABC is a file containing the original 7 card solution

$ cat ABC
ABC ADE AFG BDF BEG CDG CEF

 

This takes a minute to run on CYGWIN, even with todays mind-bogglingly fast processor speeds, because of the shell level logic. ( “perm” and “orsort” are C programs I wrote. )  So this is my excuse for not offering results for higher values of N.

Generating solutions 

As I mentioned above, my first investigation of the SPOT IT! problem involved writing programs to generate solutions for small values of N, where N is the number of symbols on each card of a deck comprising N X ( N-1 ) + 1 cards. I led off this discussion with a canonical arrangement of the actual commercial SPOT IT! deck,  which  provides the framework for this effort, as noted.

The cards containing two symbols, designated A and B, can be specified in a canonical arrangement which labels all the available symbols, and the solution for a full deck entails specifying additional cards, each with N of these symbols on it, that complete the deck and satisfy the unique matching condition.

Here is the top portion of the image above with numerical indexes overlayed on the symbols, according to the scheme explained:

The symbols on the A row ( other than A=knight ) are labeled according to the position of their occurrence in the second ( B=balloon ) row, which is not labelled because every label corresponds to the position of the card, 1 thru 7. Each card of the A row is labelled with a different color, indicating its column.

The third, or C=zebra, row has each symbol labeled according to its color and value in the A row. It so happens that for this case of N=8, once the C row is specified, the solution is unique. Using the color to indicate a column, as noted, the labeling generates the array specification:

… and these are the terms in which my program generates solutions. That program found 120 unique solutions in these terms, of which this one happens to be the 14th:

1 2 3 4 5 6 7
2 3 6 1 7 5 4
3 6 5 2 4 7 1
4 1 2 7 6 3 5
5 7 4 6 2 1 3
6 5 7 3 1 4 2
7 4 1 5 3 2 6

1 3 5 7 2 4 6
2 6 7 4 3 1 5
3 5 4 1 6 2 7
4 2 6 5 1 7 3
5 4 2 3 7 6 1
6 7 1 2 5 3 4
7 1 3 6 4 5 2

1 4 7 2 6 5 3
2 1 4 3 5 7 6
3 2 1 6 7 4 5
4 7 5 1 3 6 2
5 6 3 7 1 2 4
6 3 2 5 4 1 7
7 5 6 4 2 3 1

1 5 2 6 3 7 4
2 7 3 5 6 4 1
3 4 6 7 5 1 2
4 6 1 3 2 5 7
5 2 7 1 4 3 6
6 1 5 4 7 2 3
7 3 4 2 1 6 5

1 6 4 5 7 3 2
2 5 1 7 4 6 3
3 7 2 4 1 5 6
4 3 7 6 5 2 1
5 1 6 2 3 4 7
6 4 3 1 2 7 5
7 2 5 3 6 1 4

1 7 6 3 4 2 5
2 4 5 6 1 3 7
3 1 7 5 2 6 4
4 5 3 2 7 1 6
5 3 1 4 6 7 2
6 2 4 7 3 5 1
7 6 2 1 5 4 3

The C row matches, and I spot checked the D, E, etc. rows, which according to my logic must necessarily match.

And now a true confession. Note that the C row array specification is symmetric about the major diagonal. I.e. we have  1, 22, 333, 4664, 51515, etc. reading from the left column up to the right, proceeding from top to bottom. I noticed that the solutions, starting from this canonical form and using brute force search, had this form for small N, up to N=5. I found that for N=8, e.g., the brute force search bogged down hopelessly, searching through fruitless combinations, so I restricted the search to these symmetrical C row arrays, and was able to proceed up to N=9. It rankles me, but I haven’t been able to prove that this condition is necessary, however evident it seems that it must be true.

Concomitant to the symmetric C row array, we see that the other row arrays are each formed by a permutation of the columns of index values into the canonically order sets of symbols defined by the A and B rows. This is a purely empirical observation, but it certainly seems to be true in general, and so I stand in perplexity.

More on enumeration of solutions

I commented above under the “Permutation of symbols” heading,  that brute force enumeration, which I carried out for the case of 3 symbols per card, is not practical for larger values. Note that with 4 symbols per card we have 13 instead of 7 unique symbols, and 13!  =  6227020800, as compared to 7! = 5040.  However, some straightforward reasoning allows us to proceed.

Starting with the case of N=3 symbols per card, we can observe that we must have a unique ABx card, and there are then 5 choices for the third symbol, x, on that card, and each of these cases is equivalent, since the labelling of the symbols is arbitrary. Also every deck containing a different ABx card is different, so there are 5 equinumerous sets of unique decks, all different.

So it suffices to enumerate the decks containing an ABC card. We note there must be an AD card, which must be ADE, ADF, or ADG, and following the same reasoning as above, these define 3 equinumerous sets of unique decks, so now we have 15 sets of decks, each equinumerous with the deck containing ABC, ADE, and we can anticipate from the earlier enumeration of 30 unique 3 symbol decks that each of these sets has 2 unique decks.

So continuing, with ABC, ADE, we must have AFG, and we must have a BDx card, which can be BDE or BDG, so the two possible decks are :

ABC ADE AFG BDF BEG CDG CEF
ABC ADE AFG BDG BEF CDF CDG

… and we have 5*3*2 = 30 unique decks with 3 symbols on each card, given 7 unique symbols, so we move along to the case of N=4.

With 13 symbols, we see that there will be C(11,2) = 55 possible cards, ABxy, with the 11 remaining symbols taken in combination 2 at a time. Then in each case, using ABCD as our exemplar, we will have C(8,2) = 28 possible cards, AExy, and then C(5,2) = 10 AHxy cards, leaving the AKLM card, making 15400 unique sets of 4 Axyz cards. For each these sets, we can form the same number of Bxyz cards ( x,y,z != A ) so we take the case of  { ABCD, AEFG, AHIJ, AKLM } and note that each Bxyz must have one symbol from each of the last 3 in this “A set” . There must be a BEyz, BFyz, and BGyz card, and there are 3!*3! ways to assign {H,I,J} and {K,L,M} to y and z. So there are 36 “B sets”.

Now we come to the point of the matrix solution which completes a deck given canonically chosen “A & B sets”, as described above for the case of N=8, the true SPOT IT! deck. One last factor to account for is the interchange of the remaining symbols after A and B. The matrix solution assumes a canonical order for these, so that it won’t redundantly find solutions obtained by shuffling the matrices around. For N=4 this just means a factor of 2 to allow for the swapping of C and D.

Then, in the case of N=4, we get the unique matrix solution:

1 2 3
2 3 1
3 1 2

1 3 2
2 1 3
3 2 1

Which just means that given

ABCD AEFG AHIJ AKLM BEHK BFIL BGJM CE.. CF.. CG.. DE.. DF.. DG..
there is a unique solution, “up to” interchange of C and D. Note that CE, CF, CG, DE, DF, DG must each be present, and this is accounted for in the matrix solution by setting the first column always to 1,2,3 as indexes to  E,F,G in the second position of the “B cards” .

This brings us to N=8. The reasoning just adduced gives a general formula for any N, which applied to N=8 becomes, for the number of “A sets” :

C(56,7) * C(49,7) * C(42,7) * C(35,7) * C(28,7) * C(14,7) / 8!  =

56! / ( 7! )^8 / 8! = 42354925592620124113657511548409579520000

… and for the number of “B sets” for each “A set” : (6!)^6 = 139314069504000000

… throwing in the factor of 6! for the permutation of C,D,E,F,G,H and recalling that there are 120 matrix solutions to every “A & B set” specification, we have a grand total of:

509815040933983250324665926101388800612911244378112000000000000

unique 57 card SPOT IT! decks, using the same 57 symbols. And the 57! permutations of the symbols of any one of these will produce 79493377501440 copies of each of them.