Lösungsvorschläge A16 Schafhotel

[Pierrot]

Eine von drei sehr schönen Aufgaben von Matthew Maat, freue mich schon auf weitere aus seiner Feder die nächsten Jahre…


Schöne Anwendung der Potenzmenge (hier einer dreielementigen Menge), sprich die Menge aller Teilmengen bis auf die leere Menge. 
Also 2^3-1=7 Teilmengen. Jede Teilmenge entspricht einer Schafsart-Zimmeraufteilung (mögliche Elemente 1,2,3 sind die Zimmernummern).
Dann sieht man direkt, dass für je  zwei Teilmengen x und y die Menge z gerade die Vereinigungsmenge von x und y ist. 

Man beginnt günstiger Weise bei David: für 7 verschiedene Schafsarten braucht er gerade alle 7 möglichen Teilmengen (leere Menge ist ja ausgeschlossen) und man sieht beim Aufschreiben in eine Tabelle direkt wie oft jedes Zimmer belegt ist. Erst bei Ananias kommt man von 4 auf 3 Goldstücke.

Hier ausführlicher mit der Tabelle der Teilmengen: 
https://www.dropbox.com/scl/fi/c7j8ol6v4...pf0rl&dl=0Ω

[Georg J. aus D.]

Du behauptest: "Für C, B, A darf man nur einelementige S_i streichen."

Für A darf man auch S_3, S_5 und S_6 streichen. Übrig bleibt die Zimmerbelegung. Und diese muss unter der Vereinigungsoperation abgeschlossen sein.

Die Kosten für n Schafe: https://oeis.org/A004001

2^(n-1) bis 2^n-1 Schafarten in n Zimmern kosten insgesamt: https://oeis.org/A095930

[Pierrot]

Das ist korrekt! Ändert aber nichts an der Lösung, dass Ananias 3 Goldstücke zahlen muss, anstatt alle 3 Zimmer dreifach zu belegen, braucht er also nur zwei Zimmer dreifach und eines einfach zu belegen.

Dieser Beitrag wurde zuletzt bearbeitet: 01-01-2024, 08:17 PM von Pierrot.

[Mathe Juergen]

Das mit der Regel 3 ist lästig (und erforderte, zumindest für mich, "Fleißarbeit"). Ohne Regel 3 müssten sie genau 12 Goldtaler bezahlen, aber diese Antwort gibt es zum Glück nicht.

Bei David muss man sich zum Glück nicht um die Regel 3 kümmern (das wären 7 über 2 = 21 Funktionswerte zum überprüfen), denn es gibt mit 3 Zimmer nur genau eine Verteilung von 7 Schafsorten, nach den übrigen Regeln nämlich:

Zimmer 1: 1 ; 2 ; 3 ; 5

Zimmer 2: 1 ; 2 ; 4 ; 6

Zimmer 3: 1 ; 3 ; 4 ; 7

Somit sind dies genau 4 Goldtaler. Da A max. 4 , B max. 5 , C max. 6 sein kann, folgt sofort: Summe <= 4 + 4 +5 + 6 = 19 ==> Antwort 8, 9 und 10 sind raus.

Kommen wir zu Ananias: Beispiel

Zimmer 1: 1 ; 3 ; 4

Zimmer 2: 2 ; 3 ; 4

Zimmer 3: 3

Funktionswerte nach Regel 3:  x ; y  1;2  1;3  1;4  2;3  2;4  3;4
           
                                                z    4     3     4     3     4    3

Somit ist A = 3 womit die Summe auch nicht mehr 19 sein kann ==> Antwort 7 ist raus

Kommen wir zu Benjamin: Beispiel

Zimmer 1: 1 ; 2 ; 3

Zimmer 2: 1 ; 2 ; 4

Zimmer 3: 1 ; 3 ; 4 ; 5


Funktionswerte nach Regel 3:  x ; y  1;2  1;3  1;4  1;5  2;3  2;4  2;5  3;4  3;5  4;5
           
                                                z    1     1     1     1     1     1     1     1    3     4

Somit ist B = 4 womit die Summe auch nicht mehr 18 sein kann ==> Antwort 6 ist raus.

Kommen wir zu Caius: Beispiel

Zimmer 1: 1 ; 2 ; 4

Zimmer 2: 1 ; 2 ; 3 ; 6

Zimmer 3: 1 ; 3 ; 4 ; 5


Funktionswerte nach Regel 3:  x ; y  1;2  1;3  1;4  1;5  1;6  2;3  2;4  2;5  2;6  3;4  3;5  3;6  4;5  4;6  5;6
           
                                                z    1     1     1     1     1     1     1    1     2     1     3     3     4     1     3
    
Somit ist C = 4 ==> Summe ist 3 + 4 + 4 + 4 = 15 ==> Antwort 3.

[Fanbusfahrer]

So bin ich auch vorgegangen. Irgendwie fand ich mein Vorgehen nicht so schön. Freue mich da auf die Musterlösung.
Die Aufgabe hat mir alles abverlangt ;-)

[st1974]

So bin ich auch vorgegangen. Irgendwie fand ich mein Vorgehen nicht so schön. Freue mich da auf die Musterlösung.
Die Aufgabe hat mir alles abverlangt ;-)

Vielleicht gefällt dir meine Lösung:

https://www.dropbox.com/scl/fi/qof23dpfp...wt0si&dl=0