Possible "Spot it!"-like decks

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

Possible "Spot it!"-like decks

Postby lightvector » Tue Aug 29, 2017 2:48 am UTC

Just for fun - this is a possibly-hard math puzzle inspired by the following game: https://boardgamegeek.com/boardgame/63268/spot-it

You have a deck of cards. Every card has exactly 8 different symbols on it, and for every pair of cards there is exactly one symbol that they have in common. Additionally, each symbol occurs on exactly the same number of cards in the deck as every other symbol**. What are the possible sizes that the deck can be?
**I think this is not true of the deck in the actual game, but I think the question is more interesting with this restriction.

What if the number of symbols on each card is different than 8? For each possible number of symbols, can you determine all the sizes of decks that are possible?

I don't actually know a full solution for this puzzle, but I do have some partial results:
Spoiler:
For starters, the number of cards in the deck must be 1 mod D where D is the number of symbols on each card (ignoring the trivial solution of an empty deck). I also know some more (somewhat strong) constraints that have to hold, plus I know of some simple classes of constructions that work, but I've found it difficult to make further progress.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Tue Aug 29, 2017 4:04 am UTC

First thoughts from me: It occurs to me that the supervalue number of symbols the (8 or otherwise) card symbols are populated from has a bearing upon matters.

Reducing to two symbols per card, a choice of two symbols (only) allows no more than one card (no further choice of two can be other than the original, thus not unique enough). Whereas with three symbols, the nominal combinations of AB, AC and BC provides a maximum of three unique cards. Four symbols (still choosing two) requires that AB cannot be partnered with CD, of all the unique combinations.

For three symbols per card, however, four total possibilities of symbol reveals a different problem. None of the four combinations (each different "all but one of the symbols" combinations) can have just one uniquely shared symbols. As such, you need to have (I suspect) twice as many available symbols, less one, as you're going to pick, and yet ignore a vast majority of the viable combinations. I.e. ABC precludes any ABx, ACx, BCx choice, you have to attempt only Axy, Bxy and Cxy (which, in turn, need to mesh with each other, and maybe further if that's not the limit already, which I think it should be).

Must the choice-space then top out at CDE, as DEF is too mutually exclusive? Or is CEF (or CQW) a viable combo? I think it must remain compact, so if not just A..E then far more likely the limit is A..F (but avoiding ABC and DEF being chosen) than anything as extensive as A..W (with huger gaps, there surely would be 'missing letters' if you tried to start with ABC and CVW as your 'limits' then work around the necessarily enlarged holes in the choice-space. (I'm now envisaging some variation upon the Sierpinski Gasket might n-dimensionally represent the choice-space's usable points...)

So, maybe that's useful to you in narrowing things down. Or maybe I've got something wrong, along the way.


ETA: Ooooorrrrr.... Now I've changed my mind on how to approach this. You probably need to look at N-Polygons. Think of points and vertices of a triangle in a show-2-from-3 diagramatical analogue. Then consider how a tetrahedron represents what I think must be the four possible 3-from-6 cards you could create. Then raise up the dimensions accordingly!

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Tue Aug 29, 2017 12:53 pm UTC

I'm probably wrong, but I see this as two decks constructed alike.
lightvector wrote: Every card has exactly 8 different symbols on it

The number of unique permutations for one deck would be 8!, 8 things taken 8 at a time. This because the 8 symbols are distinct.

When you say that each pair must share one symbol, what I am seeing is two decks exactly alike.

Here is the analytical. Each card is a set that has 8 members in different positions. Permutations and combinations tell me me that the larger set containing all the possible unique permutations is 40320 cards, each card distinct.

Proportionality tells me that I can simply multiply those sets by two to get the set you want. Here is what that means. For two decks, every card with one member uniquely in both decks represents the two decks that vary in exactly one way. What that says is that there is one card, with 8 symbols, where 7 of symbols all are in different distinct positions while when 1 is in the same position. And that there are precisely two cards like that in two decks.
lightvector wrote:What are the possible sizes that the deck can be?
The total number of cards is 80,640.

As a sanity check, take the 8 of hearts, on two cards in two identical decks. On the eight of hearts, name one heart, h1 one on both decks, that heart should be in the same location on both cards. Now number the remaining cards so that none of the remaining hearts are ordered the same way. What this say is take this sequence and rearrange it, h2,h3,h4,h5,h6,h8 and change it to this, h3,h4,h5,h6,h7,h2, while keeping h1 the same.. This can be done in pairs with every card. Is that a true statement? If this is true, you now know the answer to your second question.
lightvector wrote:What if the number of symbols on each card is different than 8?
I just showed you how to make that true on a deck of 52 unique cards. Or, if you take it where it leads, how to do this with a deck of any size, as long as every member is distinct. Further you can arrange these same decks in other unique ways while maintaining that condition, by realizing that there are other ways to arrange the markings on the deck for these deck pairs since the remaining 7 can be arranged in 7! unique positions. 5020. This represents (8!+7!)

@ Soupspoon
I missed this in the discussion about password security, I miscounted my sets. I should have realized that Randall's set was larger than mine, not smaller.(/facepalm/) :oops:

You're walking on the edge of the B-T Paradox. When you moved to n gons, you moved closer. He took a 6 gon to make his point. With a 6 gon there are an infinite number of sets containing an infinite number of permutations of that 6 gon, different by n. For his condition of i. Each gon is unique. Here is what he says about doubling. The two spheres differ by a ratio. n=set1/set 2. n counts the individual points in that ratio. The sets are precisely congruent, and differ by location of the points. His spheres are concave everywhere and have no volume. They only have surface area.

Image

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Tue Aug 29, 2017 1:28 pm UTC

B-T again? I think I miss the relevance here, though I think I see where you think it is. You speak of comparison of two decks, whereas the problem is actually comparison within a single deck, and then you're doing the "halve the deck, form two equal decks from each half, still as large as the original", I think.

I've basically satisfied myself about how my ETA point fully solves the problem (just solve for oneself the particular N-Polygon problem, or else look it up, or else just use its orthographic projection). Anyway, that's a practical exercise best left until later.

DavidSh
Posts: 67
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Possible "Spot it!"-like decks

Postby DavidSh » Tue Aug 29, 2017 2:13 pm UTC

For the case with D symbols per card, I can see:
Trivial decks with 0 or 1 cards fit the rules.
A general construction with D+1 cards always works, in a symbol space of D(D+1)/2 symbols.
A construction with 1 + D(D-1) cards in a symbol space of 1+D(D-1) symbols works if D-1 is prime.
No more than 1+D(D-1) cards can work.

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Possible "Spot it!"-like decks

Postby Flumble » Tue Aug 29, 2017 2:44 pm UTC

Naturally, this has been asked on stackoverflow before. On one side math behind it and on the other construction of the cards.

The magical concept used is finite projective planes and I won't pretend to really understand it, but it seems to work. Like David said above, for n+1 symbols per card you can have up to n^2+n+1 cards, at least if n is a prime power. No idea about the upper bound of points when n is not a prime power –whether a projective plane exists for such an order is an open problem, but someone may have estimated the maximum number of cards for n+1 number of symbols per card.

The nice thing about it is that you can remove any* number of cards (or points in the plane) and the game still works –for example there are 57 cards possible for Spot It!, but they only used 55.

[edit]
*you'd have to remove all cards containing a certain symbol (i.e. all points on a line) to keep the additional restriction of "all symbols must occur equally often".

Since 6 is the smallest non prime power, can we make a deck with 7 symbols per card, all symbols occuring evenly? It can't be constructed from a projective plane (since no projective plane of order 6 nor 10 exists according to wikipedia), but maybe some other construction is possible.
Last edited by Flumble on Tue Aug 29, 2017 4:31 pm UTC, edited 2 times in total.

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Tue Aug 29, 2017 3:06 pm UTC

There is no single deck where his condition is true. He defined it out by his choices
lightvector wrote:Every card has exactly 8 different symbols on it, and for every pair of cards there is exactly one symbol that they have in common.
There are 40320 possible unique cards in his deck, he said every card forms a unique pair. With the other points arranged in other ways. This is true for one token if the tokens location is unique. If his deck is one card with one token than there is another deck with one card holding his token in a position that satisfies his statement.

What his condition told you is that there is a set of 8 different tokens arranged so that all the tokens are different by one. Since there are only 4 suits we'll use the 4 cards from those suits. Take a 4 of hearts, a 4 of spades, a 4 of diamonds and a 4 of clubs, and satisfy his condition. You can't obviously. Now rearrange the tokens on all four cards to match his first condition by rearranging the location of the suites. This is translation. Each card should now match each other precisely. Use his second condition.

This is no difference between the cards, it still can't meet his second condition. Now rearrange the cards so the hearts don't move and everything on the cards changes by one. This is rotation. The hearts are all the same, everything else has changed. This meets his condition twice. And it represents 4 decks with four suits and how they differ. And If I were so inclined I could write all the positions, on a 52 card deck four ways for all 52 cards. by denoting on all four corners instead of two. Playing cards are symmetric, they are marked at each corner in two ways. So he describes two decks

Feel free not to read what is under this spoiler, I supply it only because I brought it up. The argument per se above is sufficient to prove my point. I don't have the math, to show you in a way that I could make rigorous for you. I understood it through geometry.

Spoiler:
I know you don't see the connection. I wouldn't have supposed you would. Since you come to it in a different fashion. And this is the last time I will bring it up. I just did it, because of the way the OP bounded his problem. When you moved on from that discussion, I didn't, and I still haven't. But to get to the next level, XKCD can no longer help me since I have to move to tensor calculus to go further. I'm going to buy a book on sets, that is in circulation now, written by Felix Hausdorff. A man of extreme clarity.
Hausdorff's work was the first textbook which presented all of set theory in this broad sense, systematically and with full proofs. Hausdorff was aware of how easily the human mind can err while also seeking for rigor and truth. So he proposed in the preface of the work:

"... Of the human privilege of error to make as economical a use as possible."
I wish I had his clarity. Here is the connection.
In a paper published in 1924,[4] Stefan Banach and Alfred Tarski gave a construction of such a paradoxical decomposition, based on earlier work by Giuseppe Vitali concerning the unit interval and on the paradoxical decompositions of the sphere by Felix Hausdorff, and discussed a number of related questions concerning decompositions of subsets of Euclidean spaces in various dimensions. They proved the following more general statement, the strong form of the Banach–Tarski paradox:
If you look closely what you will see is that the proof is a deleted neighborhood proof.

Sorry to be a pain in the ass.
Morris Walters

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Tue Aug 29, 2017 4:33 pm UTC

morriswalters wrote:There is no single deck where his condition is true.

I don't think that was ever an issue. We're only asked for the size of the deck, not the composition.

Frexample: ABC, ADE, BEF, CDF are the maximal four combos in a 3-symbols-from-6, it seems. But it could equally be ABE, ACD, BCF, DEF. In fact, there are up to 6! variations (just combinatorially choosing A-F in different orders) and actually less (due to certain combinatorial congruencies).

(I worked out the above, in my head, envisaging a tetrahedron. Moving up to a pentahedroid, 4-from-10 combos seem to be ABCD, AEFG, BEHI, CFHJ and DGIJ, unless I've missed a dimension. It also looks like ABCDEF, ABDGHI, ACEGHJ, BCFGIJ, DEFHIJ can be derived from my model as representing the maximal solution for showing six of ten and always matching exactly three, if you want to get complicated... :) )

DavidSh
Posts: 67
Joined: Thu Feb 25, 2016 6:09 pm UTC

Re: Possible "Spot it!"-like decks

Postby DavidSh » Tue Aug 29, 2017 6:32 pm UTC

I think part of the difference here is that most of us are treating each card in the original problem as an unordered set of 8 symbols, with the requirements being that the intersections of these sets for two different cards having exactly one element, and the numbers of cards for which the set contains any particular symbol being some constant K.

I would guess that morriswalters is treating the cards as ordered 8-tuples of symbols, I suspect as permutations of the same set of 8 symbols.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Tue Aug 29, 2017 10:38 pm UTC

Having juggled it around, I thought I'd go through my N-Polygon attempt to break down the problem. It aint necessarily pretty, the way I describe it, but the pictures it implies are rather elegant if I haven't made my word-soup into a word-stew!


In one version, consider a point/vertex to represent each card. A direct connection between points represents two cards sharing a symbol. The one and only symbol linking the two cards, and the symbol only links those two particular cards.

Imagine three cards. Three vertices, each of the three linked to the other two uniquely. It's a triangle. Two edges to each vertex indicate two symbols per card, each the unique 'key' to one of the others. A triangle.

Or imagine four cards. As a tetrahedron. Each vertex has a symbol (edge) connected to one of the other three. Three uniquely linking symbols(/connections) per card(/vertex). Out of six symbols throughout the shape.

Then extend further to the pentahedroid (or whatever you want to call it, like "tetrahedron-based pyramid" as you extend each vertex of the tetrahedron towards a new point, or 5-cell as it has four (either distorted or extradimensional) new converging tetrahedra added to the original one as you do that) and there's a fourth edge leading out from each of the four prior vertex-of-three examples towards the new ('out there'/'in there') fifth point. Continue to add more points, one at a time, and connect it uniquely to each and every prior accumulated one in an N-triangular geometrical net, until you get eight connectors leading off from each of the (by now) nine points to each of the other eight. That models your archetypal "Spot It!" deck.


One model, because a triangle is its own anti-shape. Consider the three edges being the cards, and where two edges join (the vertices) could be the symbol unique to to that pair of cards. And a tetrahedron has an interesting transformation to itself, too. Each of the four faces meets one or other of the other three, uniquely, at one or other of its three edges.

Or, outside the scope of the original problem, it has three corners which it shares with exactly two other cards. But if you want to, you can make those corners the symbol-points and identify a unique face-to-face connection by the two symbols that define the unique edge between them.

But so long as you stick with the simpler N-Triangle geometric progression (i.e. not the more open-caged octahedron or icosahedron, and their successors), you can choose your method of every-card-links-to-every-card. When extrapolating to the pentahedroid, I was able to derive how exactly three (out of six) edges of every unit tetrahedron were unique to the connection that 'solid face' had with any other of the solid faces, with ten edges in total throughout the full geometric form, any single edge being upon one of exactly three of the constituent tetrahedra. (An edge 'inherited' from the original tetrahedra, prior to adding the fifth point, is a member of that original tetrahedron, plus the two fifth-pointing tetrahedra that base themselves upon the two triangular faces that were used as bases in that fifth-pointing.)


Anyway, if you do the math(s), this explains much.

Starting at zero dimensions of extent, one lone vertex has zero edges (or anything else), with nothing to connect to. If you had one card, it wouldn't match with anything, it could be blank!

One dimension of extent has two vertices and one line between them. Add the point, add as many lines as you already had points (1) to lead from 'all' the existing one to the new one. (No faces, or further higher shapes.) Two cards (vertices), each of one symbol (connector out from the vertex), leading to the other. Only one symbol required. Symbol appears only upon two cards. But you only have two cards.

Two dimensions of extent takes the two prior vertices and extends (from each) a new connection to the new third vertex. Two lines (prior points) added to the prior one line is three. Three cards each with two connectors/symbols, three symbols total. Symbols appear upon two cards each. And you have also formed your first 'face'.

Three dimensions lets us add a fourth point. Three new edges (from three prior points) plus the three old edges (two nearly-new edges, one older edge, no edges previous to that) and also three new faces (based upon the prior edges) to add to the prior face, and one new tetrahedral solid now exists. (Each symbol still upon just two of the four cards, by this scheme.)

Four dimensions allows us the fifth point. Four edges (to add to the three, two and one priors). Pretty obvious now that edges is a triangular number n(n+1)/2. Plus six new faces (prior edges basing the new faces) and four new solids (prior faces basing the new solids) created to connect to the new point, for now ten triangles and five tetrahedrons. And this single 5-cell that we created.

N dimensions will allow N+1 cards, N symbols per card, N(N+1)/2 symbols needed, no more than two cards show each symbol, etc, for the original problem. But then you can look at using uniquely matching symbol pairs, triplets, etc.


However, from the description of the game (and by belatedly reading Flumble's post that mentions the finite projective planes, which is something I know of but had forgotten about until now - and I've yet to follow your links, too!), it seems that my optimal N-simplest-triangular setup is actually not used, but goes into more complex N-platonic or even N-stellated bodies (with different 'densities' of symbols per card and even cards-per-match, dependant on how you map the geometries to the playing materials.


That does, though, lead to considering higher-order symbolic matches applicable to K>2 cards at a time or other fudges. If you want cards that allow a three-player-Spot-It/Snap-type-thing, then why not? Lay down a card, lay down a second (optionally limit the time to, study these two), then lay down a third and the player who first identifies the uniquely maximal number of symbols only upon all three cards wins the first card. Fourth card added, and can you spot which shared symbols from #2 and #3 (that weren't all on 1, and maybe none were) are also seen to be on #4? You get to pick up #2, to score, if you do before the others. And, you now know how to work out how many cards you can have and how many symbols you'll need, and how to build up your pack artwork... I'm sure…

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Wed Aug 30, 2017 2:25 am UTC

morriswalters told you exactly what he was doing. I drew cards. But yes.

Draw it for me. Is it this?

[1,8] [8,7][7,6][6,5][5,4][4,3][3,2][2,1]

Is this is what he is describing? There is only one match per symbol and it takes 16 cards for the base. Every number happens twice and they are evenly distributed. I get 112 cards. Just move the pairs everywhere they can go. 7*8 pairs 56*2=112 cards in a deck. The original game used 55. Seems trivial. Mine captures his and adds some few sets. :?

lightvector wrote:For each possible number of symbols, can you determine all the sizes of decks that are possible?
Well?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25788
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Possible "Spot it!"-like decks

Postby gmalivuk » Wed Aug 30, 2017 3:51 am UTC

It's not one match per symbol, it's one symbol per match. As in, pick a random pair of cards. They have to have exactly one symbol in common.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Wed Aug 30, 2017 10:17 am UTC

gmalivuk wrote:It's not one match per symbol, it's one symbol per match. As in, pick a random pair of cards. They have to have exactly one symbol in common.
So shoot me it was late. 56 ordered pairs.

Check the pictures. These are just ordered pairs on round cards. I just handed the same game back to him. They have a version with three tokens to a card. Ordered triples. I put a picture up. I thought he wanted something harder than what he had. I guess this involves some arcane jewel math, and as such I shouldn't be here since I don't know it. So up on my broom, woosh, woosh, and away.
spoilered for large image.
Spoiler:
Image
Image

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25788
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Possible "Spot it!"-like decks

Postby gmalivuk » Wed Aug 30, 2017 11:50 am UTC

They're also not ordered pairs. Order doesn't matter.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Possible "Spot it!"-like decks

Postby Flumble » Wed Aug 30, 2017 1:30 pm UTC

Soupspoon, is your construction akin to making a complete graph? If you take the edges in a complete graph as symbols and the vertices as cards, you use all symbols exactly twice, all cards have exactly one symbol in common and it works for any number of symbols per card.
Reading through, this is probably what lightvector and davidsh had in mind as a lower bound all along.

morriswalters wrote:I guess this involves some arcane jewel math, and as such I shouldn't be here since I don't know it.

I'm amazed it takes you so long to understand the Mathematics subforum deals with actual mathematics.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Wed Aug 30, 2017 2:52 pm UTC

Flumble wrote:Soupspoon, is your construction akin to making a complete graph?
In effect, it is. Though you can see from my outline how I came at it through a different route. That was just what came out of my…
Soupspoon wrote:ETA: Ooooorrrrr.... Now I've changed my mind on how to approach this.
…Damascene moment, the rest was just mental juggling on an otherwise boring car journey, trying to keep straight what aspects of the pack I was assigning to points/connectors

(And, keeping the net in 3d/4d/etc, rather than flattening it, made it easier to track the faces/solid-edges/upwards, too. The alternative being a rather busy 'flattened' map, that I would probably have needed to put pen to paper for, and doubtless much scribbling out.)

Then you got the benefit of my trying to explain my mental images, which never quite comes out right, and definitely never unverbose. ;)


(BTW: What does the notation "[1,8] [8,7][7,6][6,5][5,4][4,3][3,2][2,1]" even mean, in context of this problem? Even if it was in error, I don't understand the intended meaning.)

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Wed Aug 30, 2017 5:48 pm UTC

@Soupspoon
Pairs of cards. I write down what I try to understand. Flumble is slow, I've been telling you the same thing since my first post. I also follow links so I can understand the point of view of the OP, what kind of sets is he looking at?

For you, I think the gons you are looking for are octagons mapped to the surface of a sphere face by face. Pair each face with one that looks like it. Start with one in the center. You'll need tape because it maps to a curved surface. Use 56 octagons cut in paper and you might get a piece wise closed surface./?/

Or you could just divide a circle equally by n and draw all the lines for each n at the center. I do it in my head. Then rotate until you get something you like. Just consider than as lying on a very weird sphere. Catch up. I'd explain the rest, but I already have. :cry:

Morris Walters

Flumble I can accept ridicule. I have to because I don't know everything, and odds are I make myself look ridiculous all the time. You appear to be one step beyond that. How am I supposed to take that? I suggest you ignore me.

Where did the OP remove to, one would think he would be in the melee? :?

lightvector
Posts: 222
Joined: Tue Jun 17, 2008 11:04 pm UTC

Re: Possible "Spot it!"-like decks

Postby lightvector » Thu Aug 31, 2017 1:49 am UTC

morriswalters - Yeah, I think you misinterpreted things originally but hopefully that's cleared up now. There is some finite set of symbols. Each card in the deck is an unordered set of D of those symbols. Every symbol is a member of an equal number of cards as every other symbol. Every pair of cards shares *exactly* one symbol (e.g. they also share at least one symbol). What are the possible sizes of deck that can be constructed?

Flumble wrote:Naturally, this has been asked on stackoverflow before. On one side math behind it and on the other construction of the cards.

The magical concept used is finite projective planes and I won't pretend to really understand it, but it seems to work. Like David said above, for n+1 symbols per card you can have up to n^2+n+1 cards, at least if n is a prime power. No idea about the upper bound of points when n is not a prime power –whether a projective plane exists for such an order is an open problem, but someone may have estimated the maximum number of cards for n+1 number of symbols per card.

The nice thing about it is that you can remove any* number of cards (or points in the plane) and the game still works –for example there are 57 cards possible for Spot It!, but they only used 55.

[edit]
*you'd have to remove all cards containing a certain symbol (i.e. all points on a line) to keep the additional restriction of "all symbols must occur equally often".

Since 6 is the smallest non prime power, can we make a deck with 7 symbols per card, all symbols occuring evenly? It can't be constructed from a projective plane (since no projective plane of order 6 nor 10 exists according to wikipedia), but maybe some other construction is possible.


Nice, thanks for the links! Yeah, once I started drawing graphs and trying to come up with explicit constructions, the kinds of graphs I was getting started to look like projectivey things. It looks like projective planes are great for generating classes of solutions, but I'm not sure that this gets you all the solutions. I'll need to take a closer look at those links, but a cursory skimming of them doesn't immediately reveal an easy way to proceed on that particular front.

So, here's what I can work out:

Let D be the number of symbols per card, let C be the number of cards, let R be the number of repeats of each symbol(how many cards each symbol appears on), let S be the number of distinct symbols. We get some obvious and trivial solution classes when some of these are zero, so ignore those cases and assume all of these values are strictly positive.

  • There are two ways of counting total instances of symbols, either cards * symbols per card = CD, or symbols * repeats of each symbol = SR. Therefore, CD = SR.
  • Considering a single card in the deck. It has D unique symbols, and each of them occurs R times, so R-1 times on other cards. All such D(R-1) of these occurrences of these symbols on other cards must be disjoint, else we would have a pair of cards sharing more than one symbol. And this must be all other cards in the deck, else we would have a pair of cards having no common symbols. Therefore, C = 1 + D(R-1).
  • Substituting in to CD = SR, and doing some basic algebra, we can get to R(D^2-S) = D(D-1). Since everything is an integer, R must be a factor of D(D-1).
  • Consider all S(S-1)/2 pairs of distinct symbols. Any such pair can occur on at most one card, because if a pair occurred on more than one card, those two cards would share both of those symbols in common. Since every card has D(D-1)/2 distinct pairs of symbols,
    we have the constraint that CD(D-1)/2 <= S(S-1)/2. With some basic algebra I believe this simplifies to (D-1)(R-D)(R-1) <= 0. This implies that R <= D, unless D = 1. And in the latter case, any size deck is possible (all cards have just the same single symbol), so that case is trivial and so setting those aside we get further that D >= 2 and R <= D.

So to summarize, excluding trivial and vacuous solutions, it seems that for any D >= 2 the potentially-possible deck sizes are of the form:
C = 1 + D(R-1)
where R is a factor of D(D-1) within the range [1,D].

So then we can build a little table of potentially-possible deck sizes:
For D = 2: 1(R=1), 3(R=2)
For D = 3: 1(R=1), 4(R=2), 7(R=3)
For D = 4: 1(R=1), 5(R=2), 9(R=3), 13(R=4)
For D = 5: 1(R=1), 6(R=2), 16(R=4), 21(R=5)
For D = 6: 1(R=1), 7(R=2), 13(R=3), 25(R=5), 31(R=6)
For D = 7: 1(R=1), 8(R=2), 15(R=3), 36(R=6), 43(R=7)
For D = 8: 1(R=1), 9(R=2), 25(R=4), 49(R=7), 57(R=8)
...

However, while all of these are potentially-possible given the conditions above, I don't know whether they are actually possible, or whether it turns out that there are other problems that can arise when attempting to actually construct a deck of that size.

Clearly all the cases where R=1 are possible - single card deck where the single card has D symbols. And R=2 is always possible - just use the "complete graph" construction that multiple people in this thread have mentioned.

I think that the projective plane constructions from Flumble's links shows that all the cases in the above table where R=D are possible whenever D is a prime power plus one. By excluding all points on a single projective line, I think we can also get that all the cases where R=D-1 are possible when D is a prime power plus one, although I haven't thought through that carefully to make sure.

But there are a lot of cases remaining. Is it possible to construct decks for the R=D and R=D-1 cases in the above table when D is one more than a number that isn't a prime power? Such as (D=7, R=6, 36 cards) or (D=7, R=7, 43 cards). And how about the intermediate cases, like (D=6, R=3, 13 cards), or (D=7, R=3, 15 cards)? I haven't tried yet to manually construct decks for these cases.

Curious to see if anyone else can come up with constructions for some of these cases, or if anyone sees any additional general solution classes or any additional constraints that can be used to rule out some more of the possibilities in that table.

That's about where I'm at now! :mrgreen:

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Thu Aug 31, 2017 12:56 pm UTC

lightvector wrote:morriswalters - Yeah, I think you misinterpreted things originally but hopefully that's cleared up now.
No. I gave you the case at 8. Permutations weed out the excess. This is an infinite set. Your set members are distinct. n things taken 2 at a time n>=1. The pairs connect the cards. My sets meet this condition.

Make a card that is an octagon, call each edge one distinct token. This is Flumble's graph with the points on faces. Your condition. Lay two cards down so the faces match. Make all the matches. There are eight possible pairs on the 9 displayed cards. The tokens aren't important, your conditions are. The set of all tokens is an infinite set, the game you cited could be created in an infinite number decks just by changing the tokens on each deck. Your deck size is n things taken 2 at a time.

Flumble's graph represents distinctness. Or permutations. Count edges at each point. for k=8 each point has 7 edges. 8*7=56. I told Soupspoon this. This is 7 copies of the first 8 rearranged in every unique way. Draw Flumble's graph with these conditions. Start at any point. Go up the axis in a helical spiral and keep track of where you start. Here is how to move. Rotate through the set. When you cross your starting point move up instead of closing the first circle. Do this 9 times and stop. Collapse the spiral.This will close the spiral. Here's how to do that on his graph. Draw the chords first on the next move go to the next chord not connected to you, while not reversing your direction. Keep doing this until the 8th time you cross your starting point and stop. You've done it.

Here's how to increment your deck, if your tokens are always larger than the tokens on your card. Add 2 cards to your current deck from a larger deck which has your deck as a subset maintaining that condition.

This isn't a condition of building a larger deck. This is a condition of choosing whatever deck you want out of a subset of a larger deck with the same conditions. The upper bound of your sets is infinity. What you're doing is picking a set from the infinite set. So your deck can be whatever size you want. This condition is about choice.

UNO decks do this with color. I'm not going to link, it doesn't appear that people are reading them. Just look for the images. Right or wrong this is the way I see it. Now that you replied I'm done, I feel better about the time I've spent with this. Thanks for posting.

Spoiler:
Your chart has errors, it appears to be miscounting by one. Your r= 1 appears to be over counted. What you have yet to realize is the any game of this type will work this way. All your doing is picking subsets of infinite sets. I picked one at 8 and told you every possible permutation. and then showed you how it works. Whatever you thought you did, this condition is ruled by the condition of pairs.

Morris Walters

n!/(n-r)!=P(n,r)

What I did with 1 deck was list every permutation, 8 arranged every way. I made the order unique and duplicated it. Every pair between those two decks fits your conditions arranged in multiple decks. 720 of them if my arithmetic is good. All with 56 cards. However arithmetic is my bane. Had I been paying more attention in the 9th grade I wouldn't have had to do two years of Algebra at one time, and I would have gotten permutations earlier. I think all those decks are unique. I wouldn't take odds.

What makes the card game you are looking at, a game, is that there are more tokens than there are positions for tokens on one card. It makes the game easier if you use images that aren't complex. Make your game out of n gons starting at 20 running to 76 and it will get hard.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 2475
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Possible "Spot it!"-like decks

Postby Soupspoon » Thu Aug 31, 2017 1:50 pm UTC

morriswalters wrote:Make a card that is an octagon, call each edge one distinct token. This is Flumble's graph with the points on faces. Your condition. Lay two cards down so the faces match. Make all the matches.

This makes it sound like you're using them like dominos. (There are trionimos, so why not octonimos? Well, apart from the need to play across a hyperbolic playing surface. ;))

So long as you don't think that's the game in this case..!

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Possible "Spot it!"-like decks

Postby Flumble » Thu Aug 31, 2017 5:47 pm UTC

morriswalters wrote:Flumble I can accept ridicule. I have to because I don't know everything, and odds are I make myself look ridiculous all the time. You appear to be one step beyond that. How am I supposed to take that? I suggest you ignore me.

I think the word is 'snark' –at least the word sounds like it is.
The reason I'm attacking instead of ignoring you is because, to me (and, judging by their responses, others too), you're mostly writing nonsense in the most formal* part of the forum and in general don't seem to discuss but rather posit things. The latter may just seem that way because of the former, but I really can't tell because of the lack of clarity and coherence in your messages. I hope this helps you.

morriswalters wrote:I'm not going to link, it doesn't appear that people are reading them.

Every link in this topic so far has been read by at least two people. (and I hope by everyone)


Soupspoon wrote:In effect, it is. Though you can see from my outline how I came at it through a different route. That was just what came out of my…

Thanks, I had a hard time understanding your description, but since you ended up with D+1 vertices, it would seem to be the same construction.


lightvector wrote: By excluding all points on a single projective line, I think we can also get that all the cases where R=D-1 are possible when D is a prime power plus one, although I haven't thought through that carefully to make sure.

This is true because any line (symbol) intersects once with all other lines (distinct symbols) at the vertices, so removing all cards on a line removes all occurences of one symbol and one occurence of every other symbol.
Or, algebraically, we have S=CD/R=(1+D*(R-1))*D/R=1+R*(R-1) distinct symbols, given D=R. All R cards containing one specific symbol have R*(R-1) other, necessarily distinct symbols, which is exactly the number of distinct symbols minus one.

My gut feeling says you can't have a deck of R=D for D=7 or D=11 because there is no projective space of the matching order. No, that's not really rigorous.


*in the mathematical sense

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Fri Sep 01, 2017 11:02 am UTC

@Soupspoon
I have no idea what you are talking about. However I'm using them as what the OP seems to want. Playing cards. I came back to correct an error in something I said to the OP.

The movement through the graph is more difficult then I initially thought. However just always start the next circle on 1 and move to the next number.

1234567n1257643n1376524n1472635n1563472n1745632n1234567n I took pictures of the graph for each loop but this morning I feel no need to link to them after looking around. The extra loop occurs because you loop up through through n and never close the first circle. It's possible that there is an error in that list, I got cross eyed drawing the 7 gons. And I'm losing interest.

Toodles

Flumble wrote:My gut feeling says you can't have a deck of R=D for D=7 or D=11 because there is no projective space of the matching order. No, that's not really rigorous.
I have no idea. I've constructed every deck I've talked about, without of course constructing every deck possible. I have no idea what a projective space is, or why I should burn time thinking about it. I have enough going on for my limited skills. All I've done is geometry and simple algebra. This isn't rocket science.

Gmaivuk can lock the thread or ban me, he has done so. No one forces you to post. I can't make you participate. And I don't care if you think I'm the village idiot. Foe me. I'm almost certain others have. I participate in a relatively small number of topics in the math forum because I don't understand them well enough to say anything meaningful.

The OP's question isn't all that interesting. The only relevant questions are, how many symbols are available, and what are the rules for using them. With a third question of how many matches per card. In permutations and combinations, R=D makes the relevant expressions undefined, the denominator goes to 0. Use n!. The deck size is a manufacturing limitation, it has nothing to do with the game. Only the tokens and the conditions of match matter.

You have things to say that I might need to hear, so you foe me, you'll feel better for it. I'll still get to read what you post. We're all good. Ok?

Morris Walters

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25788
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Possible "Spot it!"-like decks

Postby gmalivuk » Fri Sep 01, 2017 11:45 am UTC

You can't really judge the interest of the OP's question when you didn't understand it.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Fri Sep 01, 2017 1:44 pm UTC

gmalivuk wrote:You can't really judge the interest of the OP's question when you didn't understand it.
So I gather. My pardon to the poster, I seem to be missing something. It seems to be fairly straightforward though. Had I realized I didn't understand it I wouldn't have posted.
lightvector wrote:You have a deck of cards.

Every card has exactly 8 different symbols on it,

and for every pair of cards there is exactly one symbol that they have in common.

Additionally, each symbol occurs on exactly the same number of cards in the deck as every other symbol**.

What are the possible sizes that the deck can be?

See I thought that when you made cards like these it was what he was asking about. I thought these worked, Meets all his conditions.
1376524
1745632

1234567
1472635

1563472
1625743

Do this seven times and get 42, right. Of course this is seven symbols, not eight. It's the damnedest thing but I thought this could work with any number of symbols. Obviously I'm wrong, and I'll stop responding, okay?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25788
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Possible "Spot it!"-like decks

Postby gmalivuk » Fri Sep 01, 2017 2:23 pm UTC

I don't know how you misunderstand the conditions when you quote them right there, but once again order doesn't matter, so 1376524 and 1745632 aren't both allowed because they match on all seven symbols and the requirement is that they match on exactly one. So if one card has 1234567 and another has a 1 anywhere, then it cannot have any of 2, 3, 4, 5, 6, or 7, regardless of the order.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
jaap
Posts: 2071
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Possible "Spot it!"-like decks

Postby jaap » Fri Sep 01, 2017 2:27 pm UTC

morriswalters wrote:See I thought that when you made cards like these it was what he was asking about. I thought these worked, Meets all his conditions.
1376524
1745632

1234567
1472635

1563472
1625743


All your cards have the same symbols. We don't care about their order on each card, so every pair of cards in your set has 7 symbols in common. We want a set of cards such that any one card has only one symbol in common with another (and 7 other symbols that don't occur on the other card).

User avatar
ivnja
The spirit of things can bugger right off.
Posts: 785
Joined: Mon Dec 04, 2006 5:30 am UTC
Location: 19T402550 4830720 (NAD 83)

Re: Possible "Spot it!"-like decks

Postby ivnja » Mon Sep 04, 2017 1:51 am UTC

This is a picture of the game cards in questions, which could be found by following the link in the opening post:
Spoiler:
Image
Hi you.
She(?!)

arbiteroftruth
Posts: 367
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Possible "Spot it!"-like decks

Postby arbiteroftruth » Mon Sep 04, 2017 6:15 am UTC

For 7 symbols per card, I think the biggest deck you can make is 15 cards, with 35 distinct symbols and 3 instances of each symbol.

Spoiler:
1234567
189ABCD
1EFGHIJ

28EKLMN
29FOPQR

38FSTUV
39EWXYZ

4AGKOSW
4BHLPTX

5AHMQUY
5BGNRVZ

6CIKPUZ
6DJLOVY

7CJMRSX
7DINQTW


7 instances of each symbol is impossible. After you form the first card with the first 7 symbols, the act of trying to generate the other 6 instances of each of those symbols is necessarily equivalent to trying to draw lines through a 6 x 6 grid of the other 36 symbols, and the non-existence of a finite projective plane of order 6 makes it impossible to form a set of lines with the necessary properties.

Decks with 7 symbols per card and 4 or 5 instances of each symbol are also impossible, because the total number of symbols occurrences in the deck is not divisible by the number of occurrences per symbol. With 4 of each symbol, each symbol on a card matches it to 3 other cards, for a total of 21 matches, so a deck of 22 cards. That makes 2 x 7 x 11 total occurrences, which is not divisible by the 4 occurrences per symbol. Likewise, 5 doesn't work either.

6 occurrences per symbol doesn't run into this issue. But every attempt I've made looks a lot like attempting the case of 7 occurrences per symbol, so I'm pretty sure that one is impossible too.

Edit:
Fun fact. The 4-symbols-per-card version of this problem makes for a nice puzzle with a standard 52-card deck of playing cards. The puzzle being to divide the deck into 13 hands of 4 cards each, such that any pair of hands have exactly one value in common.

arbiteroftruth
Posts: 367
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Possible "Spot it!"-like decks

Postby arbiteroftruth » Fri Sep 08, 2017 7:40 pm UTC

Additional results:

I'll use lightvector's notation, where C is the number of cards in the deck, D is the number of symbols per card, R is the number of occurrences per symbol, and S is the number of distinct symbols used. As lightvector observed, there exists the constraint that CD=SR, because both products give you the total number of symbol occurrences throughout the deck.

When R=D, then S=C, and just as any two cards must share exactly one symbol, likewise any two symbols must appear together on exactly one card. This is exactly isomorphic to the main axioms of a projective plane (any two points lie on a unique line, any two lines intersect at a unique point), so any deck with R=D is isomorphic to a finite projective plane of order D-1, and is subject to exactly the same constraints.

A deck with R=D-1 is likewise always isomorphic to a finite affine plane of order D-1, and implies the existence of the R=D case. So it is likewise subject to the same constraints.

Proof sketch of the above claim:
C=1+D(R-1), and S=CD/R. So when R=D-1, S=D(1+D(D-2))/(D-1)=D^2-D
Pick an arbitrary symbol and consider all the cards containing that symbol. There will be R(D-1)=(D-1)^2=D^2-2D+1 other symbols present on those cards. If you include the original symbol you picked, that accounts for D^2-2D+2 symbols. That leaves (D^2-D)-(D^2-2D+2)=D-2 symbols unaccounted for.
All cards that don't include your original symbol will have to use all but 1 of their available symbol positions to create matches with the cards that do contain your original symbol, leaving only one position for one of the unaccounted-for symbols. Therefore the D-2 unaccounted-for symbols, together with your original symbol, form a set of D-1 symbols that never appear together on any card. Since the original choice of symbol is arbitrary, the entire space of symbols can be divided into D sets of D-1 symbols that never appear together, and every card will contain one symbol from each of these sets.
This means that if you increase R from D-1 to D, you can keep the deck where R=D-1, and add D new cards each spanning a complete set of D-1 symbols that aren't shared anywhere, together with 1 new symbol creating matches between all the new cards.

So a deck with R=D can be constructed from any deck with R=D-1, and the constraint of being able to create a projective plane of order D-1 still applies.

I've also found that if you pick any prime power p, you can construct a deck with R=p+1 and D=p(p+1)+1. This accounts for the R=3, D=7 case I looked at before, and means that you can make a deck with R=4, D=13, or R=5, D=21. I suspect this can be generalized to say that for any viable pair {R,D}, you can construct a deck with {R,D(D-1)+1}.

It's already been observed that there are simple constructions of R=1 and R=2 cases for all values of D. So the only 'small' combination that doesn't fit into one of the classifications already described is R=3, D=6. I've confirmed that such a deck is possible, but it was a very trial-and-error process, so I don't yet see any connection to other constructions.

R=3,D=6:
Spoiler:
012345

06789A
0BCDEF

16BGHI
17CJKL

28DGJM
26FLNO

39FIKM
3ABJNP

47EHMN
48CIOP

59DHLP
5AEGKO

morriswalters
Posts: 6900
Joined: Thu Jun 03, 2010 12:21 am UTC

Re: Possible "Spot it!"-like decks

Postby morriswalters » Fri Sep 15, 2017 12:19 pm UTC

gmalivuk wrote:I don't know how you misunderstand the conditions when you quote them right there, but once again order doesn't matter, so 1376524 and 1745632 aren't both allowed because they match on all seven symbols and the requirement is that they match on exactly one. So if one card has 1234567 and another has a 1 anywhere, then it cannot have any of 2, 3, 4, 5, 6, or 7, regardless of the order.
You are right, of course, but sometimes it takes me time. After much research it turns out that the whole business was done on the Stack Exchange in 2011. Including the cards and a python program to generate them. Evidently some software called Sage can do it out of the box. My apologies for being thick.

User avatar
PM 2Ring
Posts: 3619
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Possible "Spot it!"-like decks

Postby PM 2Ring » Wed Sep 27, 2017 12:39 pm UTC

I've been following this thread since it started but I apologize that I'm a bit late in posting to it; I got caught up learning about finite projective geometry. ;)

As Soupspoon noted, it's easy enough to solve the cases with R=2. And as mentioned on Stack Exchange, we can use finite fields to quickly solve cases where D-1 is a prime number or a prime power and R=D or R=D-1. I suspect that there may be some clever way to use finite fields to solve cases with 2 < R < D-1, but if there is a known way to do that (eg as a subset of some larger field), it's not easy to find via Google, or it's behind a paywall.

However, I have created a bunch of Python 3 programs that generate SpotIt-like decks, using various strategies, which I've just put on GitHub in the form of a Gist. You can grab individual files, or just download the whole collection as a .zip file. You can read about the programs in spotit_readme.txt, but I'll give a brief summary here.

These programs use integers to represent the cards' symbols. The programs print lists of the symbols on each card; an incidence matrix, that shows which symbols are used on which cards; and a pair matrix, that shows which symbol is shared by each pair of cards.

Three of these programs are special purpose: simple_spotit.py handles the simple R=2 case, prime_spotit.py uses a prime finite field to generate decks where D-1 is a prime number and R=D, galois_spotit.py uses finite field arithmetic to generate decks where D-1 is a prime power and R=D.

The rest of the programs are general purpose solvers that take D and R as command line arguments. Of these, the best all-round performer is algorithmx_spotit.py, which uses Knuth's well-known algorithm for the exact cover problem, Algorithm X. This algorithm will eventually find all solutions (if any solutions exist), however, it can consume vast amounts of RAM unless the input parameters are fairly small. The remaining programs are relatively conservative in their use of RAM, but they may run for a very long time.

All of the deck generation programs import the spotit_tools.py module, which mostly contains functions that are used to check that a deck is valid, it also contains the functions that print the incidence matrix and pairs matrix. galois_spotit.py also needs galois.py to handle the finite field arithmetic. The simple way to run this software is to put all the files into a folder and open a terminal with that folder as the current directory. That way the deck generation programs will be able to find the file(s) they need to import.

Here are some results, for those who can't (or don't want to) run my scripts. Firstly, here's a table of SpotIt parameters, which can be generated by running spotit_tools.py in the terminal.

Code: Select all

Potential Spot-It deck parameters

Any valid (non-trivial) deck corresponds to a parameter set
of this form, but some of these sets have no solutions.

Table format
------------

d: Number of symbols per card
r: Number of times each symbol is repeated through the deck
c: Number of cards in the deck
s: Number of distinct symbols

The core formula is c = 1 + d * (r - 1)
Note that c * d == r * s; also, c * (c - 1) = s * r * (r -1).
It can be shown that r divides d * (d - 1)
For non-trivial decks, 2 <= r <= d

Each row corresponds to a d, each column corresponds to an r.
Each table entry is c,s with --- for invalid d,r combinations.

rows=d, cols=r, table item=c,s

d/r     2     3     4     5     6     7     8     9    10
 2:  3, 3
 3:  4, 6  7, 7
 4:  5,10  9,12 13,13
 5:  6,15  ---  16,20 21,21
 6:  7,21 13,26  ---  25,30 31,31
 7:  8,28 15,35  ---   ---  36,42 43,43
 8:  9,36  ---  25,50  ---   ---  49,56 57,57
 9: 10,45 19,57 28,63  ---  46,69  ---  64,72 73,73
10: 11,55 21,70  ---  41,82 51,85  ---   ---  81,90 91,91


Here are card lists for some small D, R pairs.

Code: Select all

Cards=3, Spots=2, Symbols=3, Repeats=2
 0: [0, 1]
 1: [0, 2]
 2: [1, 2]

Cards=4, Spots=3, Symbols=6, Repeats=2
 0: [0, 1, 2]
 1: [0, 3, 4]
 2: [1, 3, 5]
 3: [2, 4, 5]

Cards=7, Spots=3, Symbols=7, Repeats=3
 0: [0, 1, 2]
 1: [0, 3, 4]
 2: [0, 5, 6]
 3: [1, 3, 5]
 4: [1, 4, 6]
 5: [2, 3, 6]
 6: [2, 4, 5]

Cards=5, Spots=4, Symbols=10, Repeats=2
 0: [0, 1, 2, 3]
 1: [0, 4, 5, 6]
 2: [1, 4, 7, 8]
 3: [2, 5, 7, 9]
 4: [3, 6, 8, 9]

Cards=9, Spots=4, Symbols=12, Repeats=3
 0: [0, 1, 2, 3]
 1: [0, 4, 5, 6]
 2: [0, 7, 9, 10]
 3: [1, 4, 7, 8]
 4: [1, 6, 10, 11]
 5: [2, 5, 7, 11]
 6: [2, 6, 8, 9]
 7: [3, 4, 9, 11]
 8: [3, 5, 8, 10]

Cards=13, Spots=4, Symbols=13, Repeats=4
 0: [0, 1, 2, 3]
 1: [0, 4, 5, 6]
 2: [0, 7, 8, 9]
 3: [0, 10, 11, 12]
 4: [1, 4, 7, 10]
 5: [1, 5, 9, 11]
 6: [1, 6, 8, 12]
 7: [2, 4, 9, 12]
 8: [2, 5, 8, 10]
 9: [2, 6, 7, 11]
10: [3, 4, 8, 11]
11: [3, 5, 7, 12]
12: [3, 6, 9, 10]

Cards=6, Spots=5, Symbols=15, Repeats=2
 0: [0, 1, 2, 3, 4]
 1: [0, 5, 6, 7, 8]
 2: [1, 5, 9, 10, 11]
 3: [2, 6, 9, 12, 13]
 4: [3, 7, 10, 12, 14]
 5: [4, 8, 11, 13, 14]

Cards=16, Spots=5, Symbols=20, Repeats=4
 0: [0, 1, 2, 3, 4]
 1: [0, 5, 6, 7, 8]
 2: [0, 10, 13, 14, 19]
 3: [0, 11, 15, 16, 17]
 4: [1, 5, 9, 10, 11]
 5: [1, 6, 14, 17, 18]
 6: [1, 7, 12, 16, 19]
 7: [2, 6, 11, 12, 13]
 8: [2, 7, 10, 15, 18]
 9: [2, 8, 9, 14, 16]
10: [3, 5, 12, 14, 15]
11: [3, 7, 9, 13, 17]
12: [3, 8, 11, 18, 19]
13: [4, 5, 13, 16, 18]
14: [4, 6, 9, 15, 19]
15: [4, 8, 10, 12, 17]

Cards=21, Spots=5, Symbols=21, Repeats=5
 0: [0, 1, 2, 3, 4]
 1: [0, 5, 6, 7, 8]
 2: [0, 9, 11, 12, 13]
 3: [0, 10, 14, 15, 16]
 4: [0, 17, 18, 19, 20]
 5: [1, 5, 9, 10, 17]
 6: [1, 6, 12, 15, 18]
 7: [1, 7, 13, 14, 20]
 8: [1, 8, 11, 16, 19]
 9: [2, 5, 13, 16, 18]
10: [2, 6, 11, 14, 17]
11: [2, 7, 9, 15, 19]
12: [2, 8, 10, 12, 20]
13: [3, 5, 12, 14, 19]
14: [3, 6, 9, 16, 20]
15: [3, 7, 10, 11, 18]
16: [3, 8, 13, 15, 17]
17: [4, 5, 11, 15, 20]
18: [4, 6, 10, 13, 19]
19: [4, 7, 12, 16, 17]
20: [4, 8, 9, 14, 18]

Cards=7, Spots=6, Symbols=21, Repeats=2
 0: [0, 1, 2, 3, 4, 5]
 1: [0, 6, 7, 8, 9, 10]
 2: [1, 6, 11, 12, 13, 14]
 3: [2, 7, 11, 15, 16, 17]
 4: [3, 8, 12, 15, 18, 19]
 5: [4, 9, 13, 16, 18, 20]
 6: [5, 10, 14, 17, 19, 20]


Here's a card list, incidence matrix, and pairs matrix for D=6, R=3.

Code: Select all

Cards=13, Spots=6, Symbols=26, Repeats=3
 0: [0, 1, 2, 3, 4, 5]
 1: [0, 6, 7, 8, 9, 10]
 2: [0, 12, 15, 18, 22, 23]
 3: [1, 6, 11, 12, 13, 14]
 4: [1, 10, 19, 21, 23, 24]
 5: [2, 7, 11, 15, 20, 21]
 6: [2, 8, 13, 17, 23, 25]
 7: [3, 8, 12, 16, 19, 20]
 8: [3, 9, 14, 21, 22, 25]
 9: [4, 7, 13, 16, 22, 24]
10: [4, 9, 11, 17, 18, 19]
11: [5, 6, 18, 20, 24, 25]
12: [5, 10, 14, 15, 16, 17]

                       1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
 0 X|X|X|X|X|X| | | | | | | | | | | | | | | | | | | |
 1 X| | | | | |X|X|X|X|X| | | | | | | | | | | | | | |
 2 X| | | | | | | | | | | |X| | |X| | |X| | | |X|X| |
 3  |X| | | | |X| | | | |X|X|X|X| | | | | | | | | | |
 4  |X| | | | | | | | |X| | | | | | | | |X| |X| |X|X|
 5  | |X| | | | |X| | | |X| | | |X| | | | |X|X| | | |
 6  | |X| | | | | |X| | | | |X| | | |X| | | | | |X| |X
 7  | | |X| | | | |X| | | |X| | | |X| | |X|X| | | | |
 8  | | |X| | | | | |X| | | | |X| | | | | | |X|X| | |X
 9  | | | |X| | |X| | | | | |X| | |X| | | | | |X| |X|
10  | | | |X| | | | |X| |X| | | | | |X|X|X| | | | | |
11  | | | | |X|X| | | | | | | | | | | |X| |X| | | |X|X
12  | | | | |X| | | | |X| | | |X|X|X|X| | | | | | | |

     0  1  2  3  4  5  6  7  8  9 10 11 12
    --------------------------------------
 0 | -  0  0  1  1  2  2  3  3  4  4  5  5
 1 | 0  -  0  6 10  7  8  8  9  7  9  6 10
 2 | 0  0  - 12 23 15 23 12 22 22 18 18 15
 3 | 1  6 12  -  1 11 13 12 14 13 11  6 14
 4 | 1 10 23  1  - 21 23 19 21 24 19 24 10
 5 | 2  7 15 11 21  -  2 20 21  7 11 20 15
 6 | 2  8 23 13 23  2  -  8 25 13 17 25 17
 7 | 3  8 12 12 19 20  8  -  3 16 19 20 16
 8 | 3  9 22 14 21 21 25  3  - 22  9 25 14
 9 | 4  7 22 13 24  7 13 16 22  -  4 24 16
10 | 4  9 18 11 19 11 17 19  9  4  - 18 17
11 | 5  6 18  6 24 20 25 20 25 24 18  -  5
12 | 5 10 15 14 10 15 17 16 14 16 17  5  -


And here's a full 57 card deck for the original SpotIt parameters, D=R=8

Code: Select all

Cards=57, Spots=8, Symbols=57, Repeats=8
 0: [0, 1, 2, 3, 4, 5, 6, 49]
 1: [0, 7, 14, 21, 28, 35, 42, 50]
 2: [0, 8, 16, 24, 32, 40, 48, 51]
 3: [0, 9, 18, 27, 29, 38, 47, 52]
 4: [0, 10, 20, 23, 33, 36, 46, 53]
 5: [0, 11, 15, 26, 30, 41, 45, 54]
 6: [0, 12, 17, 22, 34, 39, 44, 55]
 7: [0, 13, 19, 25, 31, 37, 43, 56]
 8: [1, 7, 20, 26, 32, 38, 44, 56]
 9: [1, 8, 15, 22, 29, 36, 43, 50]
10: [1, 9, 17, 25, 33, 41, 42, 51]
11: [1, 10, 19, 21, 30, 39, 48, 52]
12: [1, 11, 14, 24, 34, 37, 47, 53]
13: [1, 12, 16, 27, 31, 35, 46, 54]
14: [1, 13, 18, 23, 28, 40, 45, 55]
15: [2, 7, 19, 24, 29, 41, 46, 55]
16: [2, 8, 14, 27, 33, 39, 45, 56]
17: [2, 9, 16, 23, 30, 37, 44, 50]
18: [2, 10, 18, 26, 34, 35, 43, 51]
19: [2, 11, 20, 22, 31, 40, 42, 52]
20: [2, 12, 15, 25, 28, 38, 48, 53]
21: [2, 13, 17, 21, 32, 36, 47, 54]
22: [3, 7, 18, 22, 33, 37, 48, 54]
23: [3, 8, 20, 25, 30, 35, 47, 55]
24: [3, 9, 15, 21, 34, 40, 46, 56]
25: [3, 10, 17, 24, 31, 38, 45, 50]
26: [3, 11, 19, 27, 28, 36, 44, 51]
27: [3, 12, 14, 23, 32, 41, 43, 52]
28: [3, 13, 16, 26, 29, 39, 42, 53]
29: [4, 7, 17, 27, 30, 40, 43, 53]
30: [4, 8, 19, 23, 34, 38, 42, 54]
31: [4, 9, 14, 26, 31, 36, 48, 55]
32: [4, 10, 16, 22, 28, 41, 47, 56]
33: [4, 11, 18, 25, 32, 39, 46, 50]
34: [4, 12, 20, 21, 29, 37, 45, 51]
35: [4, 13, 15, 24, 33, 35, 44, 52]
36: [5, 7, 16, 25, 34, 36, 45, 52]
37: [5, 8, 18, 21, 31, 41, 44, 53]
38: [5, 9, 20, 24, 28, 39, 43, 54]
39: [5, 10, 15, 27, 32, 37, 42, 55]
40: [5, 11, 17, 23, 29, 35, 48, 56]
41: [5, 12, 19, 26, 33, 40, 47, 50]
42: [5, 13, 14, 22, 30, 38, 46, 51]
43: [6, 7, 15, 23, 31, 39, 47, 51]
44: [6, 8, 17, 26, 28, 37, 46, 52]
45: [6, 9, 19, 22, 32, 35, 45, 53]
46: [6, 10, 14, 25, 29, 40, 44, 54]
47: [6, 11, 16, 21, 33, 38, 43, 55]
48: [6, 12, 18, 24, 30, 36, 42, 56]
49: [6, 13, 20, 27, 34, 41, 48, 50]
50: [7, 8, 9, 10, 11, 12, 13, 49]
51: [14, 15, 16, 17, 18, 19, 20, 49]
52: [21, 22, 23, 24, 25, 26, 27, 49]
53: [28, 29, 30, 31, 32, 33, 34, 49]
54: [35, 36, 37, 38, 39, 40, 41, 49]
55: [42, 43, 44, 45, 46, 47, 48, 49]
56: [49, 50, 51, 52, 53, 54, 55, 56]


-----------

FWIW, in the course of my searches, I encountered a related problem: Kirkman's schoolgirl problem:
Rev T. Kirkman wrote:Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 16 guests