3
$\begingroup$

Motivation

There are several rules about what makes a rack legal for a game of eight-ball: the top ball has to be a solid, the eight-ball is in the middle, the two bottom vertices have to be one solid and one stripe, etc. But a rule I learned when I first learned to play pool was that there should be no three balls which are pairwise touching each other that are all stripes or all solids. Apparently this is not an actual rule for professional eight-ball. Nevertheless, it is an interesting restriction.

Problem

Suppose we color the points in a triangular grid with base length $n$ with two colors, $A$ or $B$. How many such colorings have the property that no three points in a touching triangle are all the same color?

For instance, with $n=4$, a legal coloring is,

     A
    B A
   A B B
  B B A B

but an illegal coloring is,

     A
    B A
   A A B
  B A B A

because it contains a triangle with three $A$s.

If $\kappa(n)$ denotes the number of legal colorings for a grid with base $n$, what is $\kappa(n)$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You might try setting up a recursion. Forgive the signatory pun. Gerhard "It May Involve Pascal's Triangle" Paseman, 2012.08.30 $\endgroup$
    – Gerhard Paseman
    Commented Aug 31, 2012 at 4:25
  • $\begingroup$ Also, when I in my not so misspent youth was racking up for 8 ball, I was supposed to alternate patterns on the border, with the 1 at an apex and the 8 close to it in the interior. This always left one striped triangle, usually to the lower right of the 8 ball when I lifted the rack. Gerhard "Wore Platforms To See Felt" Paseman, 2012.08.31 $\endgroup$
    – Gerhard Paseman
    Commented Aug 31, 2012 at 16:16

1 Answer 1

Reset to default
3
$\begingroup$

I calculated the first few terms recursively.

$1, 2, 6, 24, 130, 960, 9702, 134512, 2562516, 67152240, 2422643366, 120395521752, \\\ 8245524190254, 778511553019200, 101361018574446630$

They weren't in the OEIS, but taking off the initial $1$ and dividing the other terms by $2$ produced A007017, which referred to "L. Vuillon, 'Contribution a l'etude des pavages et des surfaces dicretisees,' Dissertation, Universite de la mediterranee, Marseille, France 1996."

Some problems like this have a closed form solution or asymptotics, but typically there is some entropy per area which people can bound but can't compute exactly, such as the hard square entropy constant.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Out of morbid curiosity, what made you consider "taking off the initial $1$ and dividing the other terms by $2$"?? $\endgroup$
    – Vidit Nanda
    Commented Aug 31, 2012 at 5:43
  • 1
    $\begingroup$ Well, the $1$ is trivial, the number of patterns for the empty triangle. The recursion I used enumerated triangles by the patterns of their bottom rows. Among the possible symmetries which might reduce the recursion, I considered forcing the first entry of the row to be an A. This optimization wasn't worth the trouble to compute the first few terms, but I figured someone else might mod out by the global $A \leftrightarrow B$ symmetry. $\endgroup$
    – Douglas Zare
    Commented Aug 31, 2012 at 6:02
  • $\begingroup$ One thing I noticed was a connection to domino tilings. If you place an AB tile next to another, one of the letters placement will be determined by the trianglee condition, and one should then place the domino to fill that condition. That doesn't mean every coloring is a domino tiling of the triangle, but a lot of it is. Gerhard "Ask Me About System Design" Paseman, 2012.08:30 $\endgroup$
    – Gerhard Paseman
    Commented Aug 31, 2012 at 6:13
  • 1
    $\begingroup$ In fact in the comments section of the OEIS they mention this exact problem: "Also, half the number of (n+1)X(n+1)X(n+1) triangular binary arrays with no upright or inverted 2X2X2 subtriangle that is all 0's or all 1's. - R. H. Hardin, Oct 22, 2010." Thanks for this find! $\endgroup$
    – Sam Hopkins
    Commented Aug 31, 2012 at 15:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .