Ile tych kart bez seta

Pod artykułem o grze SET rozie postawił problem wśród ilu kart SET na pewno jest.

Pierwotnie spodziewałem się, że we dwa-trzy wieczory znajdę jakieś mocne ograniczenie na ilość kart bez seta i będę mógł się pochwalić autorskim rozwiązaniem. No i intuicyjnie oczekiwałem odpowiedzi rzędu 13, może 15.

Jeśli ktoś jeszcze próbuje samodzielnie problem rozwiązać, proszę dalej nie czytać, ciąg dalszy zawiera informacje psujące zabawę.

Pierwszy moment niepokoju nastąpił, gdy mimo rozlicznych prób nie udawało mi się wymyślić żadnego sposobu na poszufladkowanie dającego ograniczenie jakkolwiek zbliżone do spodziewanego.

Dość szybko narzuciła mi się notacja, w której zamiast własnościami kart posługiwałem się czwórkami cyfr z zakresu 0-2 (np. pierwszą kodując oznacza kolor, druga kształt itd). Trzy takie wektory są setem jeśli ich suma na każdej współrzędnej dzieli się przez trzy (albo, jak kto woli, jest zerem przy obliczaniu w Z₃).

Próbowałem na różne sposoby te układy porządkować ale nie udało mi się dojść do niczego ciekawego.

Potem w jednej z partii nie potrafiliśmy znaleźć seta wśród dwunastu kart, dołożyliśmy trzy i ... dalej nie potrafiliśmy.

Absolutnej pewności czy tu nie ma odpowiedniej trójki - nie mam (skryptu szukającego seta w zadanej kombinacji kart na razie nie chciało mi się pisać). Jeśli ktoś takową tu znajdzie, proszę o wzmiankę w komentarzu.

Wreszcie, programista zwyciężył we mnie matematyka i napisałem parędziesiąt wierszy kodu w C++ próbującego budować jak największy zbiór kart bez seta. Kod jest dość brzydki i chwalić się nim nie mam powodu (proste wyszukiwanie w głąb w którym dla zbioru kart utrzymuję oprócz listy kart doń należących także listę kart, które jeszcze można dołożyć, tj. które nie tworzą seta z żadną parą już należącą do zbioru) ale szybko znalazł mi następujący zbiorek:

Jak widać, nawet dwadzieścia kart może nie wystarczyć.

Wykluczenie 21 jest programistycznie trudniejsze (siłowa analiza 13636219405675529520 wariantów odpada z miejsca, proste pogłębianie jakie napisałem też w realnym czasie się nie kończy.

W kolejce mam pomysł by znaleźć wszystkie bezsetowe grupy cztero-, pięcio- czy może sześciokartowe i później próbować kombinować je ze sobą, dodatkowo starając się wyzyskać różne symetrie układu. Gdyby w ten sposób uzyskać wszystkie grupy - powiedzmy - 15 czy 16 elementowe, dalej można je pogłębiać siłowo, nie powinno być ich wiele.

Ostatecznie, dzięki Arturowi Popławskiemu (warto było wpaść na Buzzie w towarzystwo matematyków) dowiedziałem się, że problem zyskał status całkiem poważnego problemu matematycznego a jednym z rozwiązań jest ta oto publikacja matematyków z Wenezueli dowodząca min. że faktycznie, 21-elementowych zbiorów kart bez seta nie ma (a wszystkie 20-elementowe rozwiązania są modulo symetrie identyczne). Aha, dla większej niż 4 liczby wymiarów (cech kart) zagadnienie jest otwarte.

Uczciwie mówiąc, trochę ciężki i żmudny wydaje mi się ten dowód i ciągle wierzę, że może istnieć jakiś cwany, zgrabniejszy sposób.

Dalsza zabawa

Poza próbami znalezienia krótszego, ładniejszego dowodu czy napisania kodu wydajnie wykluczającego 21-elementowe sety interesująca wydaje mi się próba poszacowania ilości dużych zbiorów bez setów - np. ustalenia, ile jest takich zbiorów 18-o czy 15-o kartowych albo przynajmniej oszacowania tej wartości. Końcem takich prac mogłoby być formalne wyprowadzenie prawdopodobieństwa wylosowania 18, 15 i 12 kart bez seta.

Bonus

Jako bonus załączam kawałek kodu w Pythonie, przy pomocy którego namalowałem powyższy obrazek (zamieniający kodowe oznaczenia setów na malunek z kartami).

# -*- coding: utf-8 -*-
#
# SET-painter. Paints image with given SET cards

######################################################################
# Painting B-spline, according to 
# http://stackoverflow.com/questions/2534786/drawing-a-clamped-uniform-cubic-b-spline-using-cairo
# with slight modifications (to make it possible to paint
# filled shape made of splines)
######################################################################

from collections import namedtuple

class Point(namedtuple("Point", "x y")):
    __slots__ = ()

    def interpolate(self, other, ratio = 0.5):
        return Point(x = self.x * (1.0-ratio) + other.x * float(ratio), \
                     y = self.y * (1.0-ratio) + other.y * float(ratio))

class CubicBSpline(object):
    __slots__ = ("points", )

    def __init__(self, points):
        self.points = [Point(*coords) for coords in points]

    def clamped(self):
        new_points = [self.points[0]] * 3 + self.points + [self.points[-1]] * 3
        return CubicBSpline(new_points)


class BSplineDrawer(object):
    def __init__(self, context):
        self.context = context

    def draw(self, bspline):
        pairs = zip(bspline.points[:-1], bspline.points[1:])
        one_thirds = [p1.interpolate(p2, 1/3.) for p1, p2 in pairs]
        two_thirds = [p2.interpolate(p1, 1/3.) for p1, p2 in pairs]

        poly_points = []

        coords = [None] * 6
        for i in xrange(len(bspline.points) - 3):
            start = two_thirds[i].interpolate(one_thirds[i+1])
            coords[0:2] = one_thirds[i+1]
            coords[2:4] = two_thirds[i+1]
            coords[4:6] = two_thirds[i+1].interpolate(one_thirds[i+2])

            self.context.move_to(*start)
            self.context.curve_to(*coords)
            #self.context.stroke()

            poly_points.append(start)

        # Painting the border before extending spline with interior
        self.context.stroke_preserve()

        # Adds internal polygon to selection to have fill/clip
        # working properly
        self.context.move_to(* poly_points[0])
        for pp in poly_points[1:]:
            self.context.line_to(*pp)
        self.context.line_to(* poly_points[0])

######################################################################
# Card painting
######################################################################

import cairo, math

def paint_card(card_code, ctx, top_x, top_y, width, height):
    """
    Paints card of given code (code is a string of 4 digits)
    on given Cairo context in the specified place. Card is painted
    with both border and symbols, but without background.
    """

    # Shape routines. All draw given shape border and leave
    # it's interior as selection

    def shape_diamond(min_x, min_y, max_x, max_y):
        half_hsize = (max_x - min_x)/2
        half_vsize = (max_y - min_y)/2
        ctx.move_to(min_x, min_y + half_vsize)
        ctx.rel_line_to(half_hsize, -half_vsize)
        ctx.rel_line_to(half_hsize, half_vsize)
        ctx.rel_line_to(-half_hsize, half_vsize)
        ctx.close_path()
        ctx.stroke_preserve()

    def shape_oval(min_x, min_y, max_x, max_y):
        #ctx.new_sub_path()
        med_y = (min_y + max_y) / 2
        radius = med_y - min_y
        ctx.arc(min_x + radius, med_y, radius,
                math.pi/2, 3*math.pi/2 )
        ctx.rel_line_to(max_x - min_x - 2 * radius, 0)
        ctx.arc(max_x - radius, med_y, radius,
                3*math.pi/2, math.pi/2 )
        ctx.close_path()
        ctx.stroke_preserve()

    def shape_tilde(min_x, min_y, max_x, max_y):
        hsize = max_x - min_x
        vsize = max_y - min_y
        # Experimentally picked control points for b-spline
        points = [
            (min_x + 0.1 * hsize, max_y),
            (min_x, max_y - 0.24 * vsize),
            (min_x + 0.3 * hsize, min_y),
            (min_x + 0.58 * hsize, min_y + 0.14*vsize),
            (min_x + 0.68 * hsize, min_y + 0.19*vsize),
            (max_x - 0.07 * hsize, min_y)
            ]
        # Bottom points mirror top
        points += [ 
            (max_x + min_x + 0.1*hsize - x, min_y + max_y -y) 
            for (x,y) in points ]
        # Wrapping shape up
        points.append(points[0])
        # Fix for small dilatation observed
        points = [ (x-0.05 * hsize, y) for (x,y) in points ]
        spline = CubicBSpline(points).clamped()
        BSplineDrawer(ctx).draw(spline)
        ctx.close_path()

    # Fill routines. All assume selection to fill

    def fill_empty(min_x, min_y, max_x, max_y):
        pass

    def fill_filled(min_x, min_y, max_x, max_y):
        ctx.fill()

    def fill_hashed(min_x, min_y, max_x, max_y):
        hsize = max_x - min_x
        vsize = max_y - min_y
        line_step = hsize/8  # space between lines
        line_angl = hsize/10 # space between end and start of single line
        ctx.save()
        ctx.clip()
        x = min_x + 2
        while x <= max_x + line_angl:
            ctx.move_to(x, min_y)
            ctx.rel_line_to(- line_angl, vsize)
            x += line_step
        ctx.stroke()
        ctx.restore()

    # Main work

    CARD_COLORS = [ (1.0,0,0), (0,1.0,0), (0.5,0.1,0.7) ]
    SHAPE_ROUTINES = [ shape_diamond, shape_oval, shape_tilde ]
    FILL_ROUTINES = [ fill_empty, fill_filled, fill_hashed ]
    START_RATIOS = [ (0.5,), (0.3,0.7), (0.18,0.5,0.82) ]

    color_code, shape_code, fill_code, count = [int(x) for x in card_code]

    color = CARD_COLORS[color_code]
    shape_rtn = SHAPE_ROUTINES[shape_code]
    fill_rtn = FILL_ROUTINES[fill_code]
    start_locations = START_RATIOS[count]

    # Border
    ctx.new_path()
    ctx.set_source_rgb (0, 0, 0)
    ctx.set_line_width(3.0)
    ctx.rectangle(top_x + 5, top_y + 5, width-10, height-10)
    ctx.stroke()

    vsize = 0.25 * height
    hsize = 0.75 * width

    ctx.set_line_width(5.0)
    ctx.set_source_rgb(*color)

    spacer = (width-hsize)/2
    min_x = top_x + spacer
    max_x = top_x + width - spacer

    for start in start_locations:
        med_y = top_y + start*height
        min_y = med_y - 0.5 * vsize
        max_y = med_y + 0.5 * vsize

        ctx.new_path()  # To avoid lines to first arc etc

        shape_rtn(min_x, min_y, max_x, max_y)
        fill_rtn(min_x, min_y, max_x, max_y)

def create_cards_image(cards, card_width, card_height, output_file):
    """
    Paints image of given cards and saves it inside given file (as .png)
    """
    cards_count = len(cards)
    cards_per_row = max(1, int(math.sqrt(cards_count)))
    rows = (cards_count + cards_per_row - 1) // cards_per_row

    surface = cairo.ImageSurface(cairo.FORMAT_ARGB32,
                                 card_width * cards_per_row, card_height * rows)
    ctx = cairo.Context(surface)

    # White background
    ctx.set_source_rgb (1, 1, 1)
    ctx.set_operator (cairo.OPERATOR_SOURCE)
    ctx.paint()

    for card_no, card in enumerate(cards):
        row = card_no // cards_per_row
        pos = card_no % cards_per_row
        xloc = pos * card_width
        yloc = row * card_height
        paint_card(card, ctx, xloc, yloc, card_width, card_height)

    surface.write_to_png(output_file)

######################################################################
# Main
######################################################################

if __name__ == "__main__":
    best = ["0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1012", "1022", "1102", "1202", "2012", "2102", "2110", "2111", "2122", "2212"]
    create_cards_image(best, 300, 300, "OUT/best.png")

    all = list( "%d%d%d%d" % (a,b,c,d)
                for a in [0,1,2]
                for b in [0,1,2]
                for c in [0,1,2]
                for d in [0,1,2] )
    create_cards_image(all, 300, 300, "OUT/all.png")