Lösungen Aufgabe 13 2024

[tfry]

Das führt dann ganz schnell zu einem Würfel mit nicht zusammenhängenden Nicht-Rubinen, weil diese zwei Rubine immer in einem Würfel liegen. 

Richtig, das heißt es ist Bedingung 3, die dies verhindert. Ohne wäre auch eine Lösung mit 12 Rubinen möglich (alle Ecken außer A, B, O, P und Drehungen davon).

Die Lösung mit den acht Rubinen hatte ich relativ schnell gefunden, musste aber sehr lange grübeln, um mich davon zu überzeugen, dass es die optimale ist.

[ukleinek]

Mein Python-Programm ist etwas anders. Ich habe die Würfel und Quadrate und Kanten händisch erstellt. (Wobei ich kurz nachgedacht hatte, statt den Buchstaben `itertools.product([0, 1], repeat=4)` zu verwenden. Dann sind die Kanten die Punkte, die an 3 Komponenten übereinstimmen, die Quadrate die, die an 2 übereinstimmen und die Würfel an dreien. Naja.

Dann bin ich die Möglichen Teilmengen aufsteigend durchgegangen und habe alle Bedingungen geprüft.

Code:

#!/usr/bin/env python3

points = set('ABCDEFGHIJKLMNOP')

edges = set(frozenset(ed) for ed in 'AB CD EF GH IJ KL MN OP AC BD EG FH IK JL MO NP AE BF CG DH IM JN KO LP AI BJ CK DL EM FN GO HP'.split())

squares = set(frozenset(sq) for sq in 'ABDC EFGH IJLK MNPO ACGE BDHF IKOM JLPN ABFE CDHG IJNM KLPO ABJI CDLK EFNM GHPO ACKI BDHF EGOM FHPN'.split())

cubes = set(frozenset(cu) for cu in 'ABCDEFGH IJKLMNOP ABIJEFMN CDKLGHOP ABCDIJKL EFGHMNOP BDFHJLNP ACEGIKMO'.split())

def increasing_subsets(st):
    def ssos(st, size):
        if size == 0:
            yield set()
        elif st:
            nst = st.copy()
            elem = nst.pop()
            for ss in ssos(nst, size):
                yield ss
            for ss in ssos(nst, size - 1):
                yield {elem} | ss
    for i in range(len(st) + 1):
        for ss in ssos(st, i):
            yield ss

def isconnected(st):
    if not st:
        return True
    openset = set(st)
    closedset = { openset.pop() }
    changed = True
    while changed:
        changed = False
        for po in openset.copy():
            for pc in closedset:
                if frozenset({po, pc}) in edges:
                    openset -= { po }
                    closedset |= { po }
                    changed = True
                    break;

    if openset:
        return False
    else:
        return True

# Now assume A has a Ruby and B doesn't
pointswithoutAB = points - {'A', 'B'}

for nonrubies in increasing_subsets(pointswithoutAB):
    nonrubies = nonrubies | { 'B' }
    rubies = points - nonrubies

    print(f'check {nonrubies=}')

    if not isconnected(nonrubies):
        continue

    if not isconnected(rubies):
        continue

    if not all(isconnected(nonrubies & sq) for sq in squares):
        continue

    if not all(isconnected(nonrubies & cu) for cu in cubes):
        continue

    if not all(isconnected(rubies & sq) for sq in squares):
        continue

    if not all(isconnected(rubies & cu) for cu in cubes):
        continue

    if not all(any(not isconnected((rubies - {r}) & sq) for sq in squares) for r in rubies):
        continue

    print(f'{nonrubies=}')
    break

[Dave080e]

Ich war da wohl total auf dem Holzweg... War mir nämlich sicher, dass alle Regeln befolgt sind, wenn die Kiste auf allen 16 Ecken Rubine hat. Verstehe immer noch nicht, warum das nicht stimmt...

[Gramar]

Wenn einer fehlt, sind ja immer noch auf allen Quadraten alle Rubine verbunden, so dass Regel 5 verletzt ist.

[Frank Buchholz]

Entscheidend ist hier Regel 5: jeder Rubin muss in einem Quadrat der "mittlere" sein.
Damit ein Rubin der mittlere sein kann, dürfen in diesem Quadrat dann aber auch nur drei Rubine vorhanden sein.
Nachdem es für jeden Rubin ein solches Quadrat geben muss, kann es nicht mehr Rubine als Nicht-Rubine geben, bei 16 Ecken insgesamt kann es also nicht mehr als acht Rubine geben.

Wenn man nun ein gültiges Design findet, das acht Rubine enthält, ist dies gleichzeitig optimal. Und das kann man auf Grundlage der Idee, dass die Rubine eine durchgängige geschlossene Kette bilden müssen, recht leicht bilden (z.B. MOPLDBAE).

--> Antwort 5

Ein Nicht-Rubin kann doch theoretisch auch für mehrere Rubine der Nicht-Rubin sein, oder?

Der Tesserakt ist extrem symetrisch, daher müssen auch alle Beziehungen sehr symetrisch sein, also kann es keine Lösung geben in denen die einen Rubine oder Nicht-Rubine anders angeordnet sein, als andere.

---

Nachdem ich die 8+8-Vermutung hatte, habe ich einen passenden Tesserakt gemalt:
GeoGebra 2024-13

Dieser Beitrag wurde zuletzt bearbeitet: Gestern, 04:41 PM von Frank Buchholz.

[Georg J. aus D.]

Der Tesserakt ist extrem symetrisch, daher müssen auch alle Beziehungen sehr symetrisch sein, also kann es keine Lösung geben in denen die einen Rubine oder Nicht-Rubine anders angeordnet sein, als andere.

Wenn man auf die Verbundenheit der Nicht-Rubine verzichtet, gibt es 88 Lösungen mit 6, 8, 10 oder 12 Rubinen.