8
$\begingroup$

Consider a flexible form of bingo, where each square contains a condition and you mark off whether or not the condition applies to you. The number of bingos you obtain ostensibly measures the extent to which you satisfy the theme of the bingo card. I, a soulless automaton, have inferred that these are commonly shared as images on social media as ways to bond over shared preferences.

Suppose, in my purely hypothetical robotic misanthropy, I wished to construct a standard bingo card (5x5 with a free space in the center) on which no bingos (vertical, horizontal, or diagonal) were possible. To do this, on each possible bingo line, place a pair of squares which cannot be simultaneously satisfied, such as "tall" and "short". Twelve possible bingos mandates twelve such pairs of squares, and luckily enough there are 24 usable squares in a standard bingo card.

Here is an example of one such malicious bingo card, using the letters A through L to denote the pairs:

AABCD
EEBCD
FG_HH
FIJKJ
IGLLK

How many malicious bingo cards are there? Is there a human-understandable way to count them, or should this enumeration be left to a computer like myself?

On a secondary note, are there well-known combinatorial objects they are in a natural bijection with? Searching the vast indices in my hard disks, I can only come up with "maximum matchings in a particular 24-vertex graph such that each maximal clique contains exactly one matched edge"—I do not expect to find something this convoluted in any of your human mathematical literature.

$\endgroup$
  • $\begingroup$ On an unrelated note, can someone help me fix the tags? The mobile app refuses to allow me to tag this with "enumeration". $\endgroup$ – algorithmshark Sep 9 '18 at 21:08
  • $\begingroup$ Enumeration doesn't seem to be a tag, but "combinatorics" is, and I've added it. $\endgroup$ – John Hughes Sep 9 '18 at 22:03
  • $\begingroup$ Well, there's something I want to add on to this. There are malicious cards that might have $3$ conditions like you are < 5 ft, you are > 6 ft, or you are in between $5$ to $6$ feet. This makes the counting so much nonhumanlike. $\endgroup$ – Jason Kim Sep 11 '18 at 1:37
1
$\begingroup$

Edited, new from the scratch, since there seems to be only one question, extracted from the comments, that i completely misunderstood, for short:

Consider the $24$--vertex graph whose vertex set is $\{a,\dots,x\}$ and whose edge-set is the union of the $12$ cliques $$abcde,\ fghij,\ kl\; mn,\ opqrs,\ tuvwx;\ afkot,\ bglpu,\ ch\;qv,\ dimrw,\ ejnsx;\ agrx,\ eipt\ . $$ How many matchings that have one edge in each maximal clique?


The following simple sage program computes $$6156$$ matchings:

a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x = \
    'abcdefghijklmnopqrstuvwx'
S = {a,b,c,d,e, f,g,h,i,j, k,l,m,n, o,p,q,r,s, t,u,v,w,x}
K = [ {a,b,c,d,e}, {f,g,h,i,j}, {k,l,m,n}, {o,p,q,r,s}, {t,u,v,w,x}
      , {a,f,k,o,t}, {b,g,l,p,u}, {c,h,q,v}, {d,i,m,r,w}, {e,j,n,s,x}
      , {a,g,r,x}, {e,i,p,t} ]

count = 0
for edges in cartesian_product( [ [ tuple(comb)
                                    for comb in Combinations(cl, 2) ]
                                  for cl in K if len(cl) == 4 ] ):
    U = { element for edge in edges for element in edge }

    Khorz = [ cl.difference(U) for cl in K[0: 5] if len(cl) == 5 ]
    Kvert = [ cl.difference(U) for cl in K[5:10] if len(cl) == 5 ]

    for horzedges in cartesian_product( [ [ tuple(comb)
                                            for comb in Combinations(cl, 2) ]
                                          for cl in Khorz ] ):
        Uhorz = { element for edge in horzedges for element in edge }
        ok = True    # so far, we check there are exactly 2 pieces left "vertically"
        for kk in range(4):
            if len( Kvert[kk].difference(Uhorz) ) != 2:
                ok = False
                break
        if ok:
            count += 1
            # print count, edges, horzedges, [ tuple(Kvert[kk].difference(Uhorz)) for kk in range(4) ]

print count

Note: Previously i computed a much bigger number not taking the "diagonal cliquets" as a further restriction. (This was a much harder combinatorial problem.)

Note: The original post also uses a label for each edge of the matching, in this case the counter is $6156\cdot 12!$. There is no other combinatorial structure that i can connect with this problem, the diagonal constraints make the picture very "rigid", so graph theory is the right frame.


Note: In such cases, please always give also the mathematical description, this spares effort and tension on both sides. I never played bingo, i still have no idea if a "bingo" is the whole 5x5 picture with a hole, if it is a cell, or a (malicious non-)matching pair, or a row, or a column in it. If there is an obvious bound, please mention it.

$\endgroup$
  • $\begingroup$ There is no mention of diagonals, and it is not evident to me how your stabilizer subgroup tracks or preserves that information. Also, the bottom row or rightmost column are not in the orbit of the subgroup as described. $\endgroup$ – algorithmshark Sep 10 '18 at 0:59
  • $\begingroup$ I used "diagonal" as an optional hint, there is an obvious symmetry of the Ferrers diagram of the shape $(5,5,5,5,4)$ which exchanges the "cells" $(j,k)\leftrightarrow (k,j)$, this fixes the diagonal and reflects w.r.t. it. The action of the group is used only to make the counting job simpler (for the human). I am using the permutation of the first $\color{red}{4}$ columns to bring the last row in the form **AA. What is unclear here? After this step, a smaller group acts. The downvote is not really in the humoristic spirit of the OP. $\endgroup$ – dan_fulea Sep 10 '18 at 2:36
  • $\begingroup$ There are two diagonals on a bingo card, and for a malicious bingo card to prevent those bingos there must be a pair situated along each of them. What is unclear is how your analysis accounts for this restriction when you pass from malicious bingo cards to 55554-fillings. Also, my mistake on the rows and columns comment—I got confused because two pairs on the same row like CCAA is an impossible configuration, since 12 bingos times 2 squares per bingo is precisely equal to the 24 available squares. $\endgroup$ – algorithmshark Sep 10 '18 at 17:51
  • $\begingroup$ From the start i was using and explicitly drawing an other diagram with equivalent meaning, because the question wanted - as i understood - rather an existing mathematical structure to embed the problem in it, not the number. Well, it is hard to fit the given problem in some particular structure, the connection with graph theory was in the OP, so i tried an other one, which also has some "industry". (Key word Young diagrams & tableau.) I will add some sentences in the answer to see how to pass from the bingo 5x5 card with one hole in the middle to the 5x5 card with a hole in the corner. $\endgroup$ – dan_fulea Sep 10 '18 at 18:43
  • $\begingroup$ I don't trust the number 3245346, because I think you are forgetting about the two diagonal bingos that need to be blocked (II and KK in the OP). Each malicious bingo card is determined by the choice of a pair along each of the five rows and the two diagonals: such a choice completes to one malicious bingo card if the columns have two unchosen squares each, and fails to complete otherwise. This gives a simple upper bound of $\binom52^4\cdot\binom42^3 = 2160000 < 3245346$, and if you take more care for the row choices to be disjoint from the diagonal choices, you get as low as 234576. $\endgroup$ – algorithmshark Sep 13 '18 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.