Välja böcker
Hej jag förstår inte vad jag gör för fel, svaret ska vara 18891
frågan :
Tre personer ska välja ut 2 böcker var i en samling av 10 unika böcker.
En av personerna har läst en av böckerna och vill därför inte ha den. Hur manga kombinationer kan man nu skapa?
Den första kan välja 9 över 2. Det är 8 kvar
Den andra kan välja 8 över 2.
Men nu är det 6 kvar.
Hoppsan! Det blev 15120??
Får tänka litet till. Återkommer.
Hmm 18891 = 9*2099 och 2099 är ett primtal.
Man ska vara försiktig med att larma om fel i facit när det gäller kombinatorikuppgifter, men här blir jag misstänksam.
Jag kan inte få det till annat än 9*8*8*7*6*5 / (2*2*2) = 9*8*7*6*5 = 15120
Marilyn skrev:Hmm 18891 = 9*2099 och 2099 är ett primtal.
Man ska vara försiktig med att larma om fel i facit när det gäller kombinatorikuppgifter, men här blir jag misstänksam.
Jag kan inte få det till annat än 9*8*8*7*6*5 / (2*2*2) = 9*8*7*6*5 = 15120
Ja, något verkar "lurt". Jag anar att det är en addition som spelar in.
Om person 1 är den som redan har läst boken blir det 9 * 8 * 6
Om person 2 är den som redan har läst boken blir det 10*8*6 eller 10*7*6 beroende på om person 1 valde den bok som person 2 redan läst.
Och så blir det mera komplicerat ju längre ner i kedjan vi kommer och allt skall vara disjunkt för att addition skall gälla etc. Ma5 rör sig med additionsprincipen och multiplikationsprincipen så det borde vara allt man behöver.
Det kommer säkert en smart 1-radslösning här snart. Vi får avvakta med stort intresse.
Ligger i en drängbod (drängen levde på 1700-talet och hette Lars) utan dator just nu men en observation är att:
C(10,2)C(8,2)C(6,2) = 18900 = 18891 + 9
Så på något sätt ska begränsningen innebära att nio fall tas bort från svaret om begränsningen inte fanns.
Jag får dock samma svar som Marilyn hur jag än angriper problemet…
Tillägg: 4 maj 2025 01:52
Om ingen har löst detta tills imorgon så kan jag göra en enkel simulering i Python eller liknande så kan vi få reda på svaret empiriskt.
Jag tror naytte har torpederat facit.
Det känns som en förskolelösning att dra bort 9 från antalet det skulle blivit ifall ingen hade läst någon av böckerna. Inget ont om förskolan men jag är säker på att drängen Lars hade gjort det bättre. Varifrån kommer uppgiften???
Trinity2 skrev:
Om person 1 är den som redan har läst boken blir det 9 * 8 * 6
Om person 2 är den som redan har läst boken blir det 10*8*6 eller 10*7*6 beroende på om person 1 valde den bok som person 2 redan läst.
Vi kan alltid låta den som hade läst en bok välja först. Jag ser inte att det påverkar antalet kombinationer. Fast osvuret är bäst i kombinatorikens värld,
Jag avvaktar med intresse det Pythonianska svaret.
Trinity2 skrev:Om person 1 är den som redan har läst boken blir det 9 * 8 * 6
Om person 2 är den som redan har läst boken blir det 10*8*6 eller 10*7*6 beroende på om person 1 valde den bok som person 2 redan läst.
Detta var mycket krångligare än vad jag trodde att det skulle vara...
class Book:
def __init__(self, name):
self.name = name
def __repr__(self):
return f"Book({self.name})"
class Person:
def __init__(self, name, forbidden_book=None):
self.name = name
self.forbidden_book = forbidden_book
def __repr__(self):
return f"Person({self.name})"
books = [Book(str(i)) for i in range(1, 11)]
people = [
Person("A", forbidden_book="1"),
Person("B"),
Person("C")
]
valid_combinations = set()
for i in range(len(books)):
for j in range(i + 1, len(books)):
books_copy = books[:]
book_a1 = books_copy.pop(j)
book_a2 = books_copy.pop(i)
a_books = [book_a1, book_a2]
if any(book.name == people[0].forbidden_book for book in a_books):
books_copy.insert(i, book_a2)
books_copy.insert(j - 1, book_a1)
continue
for k in range(len(books_copy)):
for l in range(k + 1, len(books_copy)):
books_copy2 = books_copy[:]
book_b1 = books_copy2.pop(l)
book_b2 = books_copy2.pop(k)
b_books = [book_b1, book_b2]
for m in range(len(books_copy2)):
for n in range(m + 1, len(books_copy2)):
book_c1 = books_copy2[m]
book_c2 = books_copy2[n]
c_books = [book_c1, book_c2]
combo = [
(people[0].name, tuple(sorted(b.name for b in a_books))),
(people[1].name, tuple(sorted(b.name for b in b_books))),
(people[2].name, tuple(sorted(b.name for b in c_books))),
]
valid_combinations.add(tuple(sorted(combo)))
print(len(valid_combinations))
Scriptet bekräftar i alla fall att svaret är 15120.
Kan det var så att tre personer väljer varsina två böcker
Men för en person är det 9 gånger som den oönskade boken dyker upp.
hansa skrev:Kan det var så att tre personer väljer varsina två böcker
Men för en person är det 9 gånger som den oönskade boken dyker upp.
Nej, så kan det inte vara.
Tänk dig att böckerna har titlarna 0, 1, 2, 3, …, 8, 9.
Dessa kan fördelas på personerna A, B och C på 18900 sätt.
Men A har läst bok 0.
Nu noterar jag några av de förbjudna kombinationerna. De två första siffrorna är A:s böcker, de två nästa är B:s och de två sista är C:s
01 23 45
01 23 46
01 23 47
01 23 48
01 23 49
01 34 56
01 34 57
01 34 58
01 34 59
01 45 67
Det var tio förbjudna kombinationer. Det återstår fortfarande en massa förbjudna kombinationer där A får 01. Sedan finns det lika många där A får 02, lika många där hen får 03 osv.
Det är faktiskt ett sätt att lösa uppgiften. Räkna inte ut hur många kombinationer som är godkända, utan räkna ut hur många som är underkända. Min gissning är 3780.
I scriptet ovan så går datorn systematiskt igenom varenda kombination som finns och svaret blir även där 15120. Facit har helt enkelt fel (förutsatt att mina mitt-i-natten-python-skills inte svek oss)
Detta var ju mycket lättare.
Totalt antal kombinationer C(10, 2) * C(8, 2) * C(6, 2) = 18900 (inklusive förbjudna).
Bok 0 förbjuden.
Förbjudna kombinationer där A har böckerna 0 och 1 (för beteckn se #12)
C(8, 2) * C(6, 2) = 420
Antal förbjudna komb där A har 0 och j (j = 1, 2, …, 9)
9* 420 = 3780
Antal godkända komb
18900 – 3780
Inte är det väl lättare än C(9,2)C(8,2)C(6,2)?
naytte skrev:Inte är det väl lättare än C(9,2)C(8,2)C(6,2)?
Jo, Mycket lättare
Iallafall snyggare. Eller, ok, lika snyggt.
Marilyn skrev:Detta var ju mycket lättare.
Totalt antal kombinationer C(10, 2) * C(8, 2) * C(6, 2) = 18900 (inklusive förbjudna).
Bok 0 förbjuden.
Förbjudna kombinationer där A har böckerna 0 och 1 (för beteckn se #12)C(8, 2) * C(6, 2) = 420
Antal förbjudna komb där A har 0 och j (j = 1, 2, …, 9)
9* 420 = 3780
Antal godkända komb
18900 – 3780
Hej jag förstår början men inte det som kommer efter för att beräkna de förbjudna kombinationerna och varför är det 0 och 1 som är förbjudna är det inte alla kombinationer där 0 ingår ?
Vi har tio böcker. Deras titlar är 0, 1, 2, …, 8, 9.
Vi har tre personer, A, B och C. De ska ha två böcker var.
Jag arrangerar i par. Första paret är A:s böcker, andra paret B:s, och tredje C:s.
Det kan bli så här: 51 37 84
Men eftersom det inte spelar roll om du får 51 eller 15 så ordnar jag varje par i stigande nummerordning: 15 37 48.
A har läst bok 0, så första paret får inte innehålla en nolla. Däremot är det ok ifall B får bok 0, för hen har inte läst någon av de tio böckerna.
Eftersom vi ordnar varje par stigande blir alltså villkoret att första siffran inte får vara 0, den andra siffran kan ändå inte vara det.
OK, du var med på att totala antalet kombinationer var (inklusive otillåtna) var
(10 över 2) * (8 över 2) * (6 över 2) = 18900
Nu vill jag räkna hur många av dem som är otillåtna, dvs hur många kombinationer som har följande utseende:
0a bc de
Jag gjorde så här:
Låt a vara 1, dvs A får 01, en otillåten kombination, oavsett vad de andra får.
Då finns det åtta titlar kvar till B och C: 2, 3, 4, …, 8, 9
B kan välja (8 över 2), C kan välja (6 över 2).
Så om A har 01 så blir det 8*7*6*5 / (2*2) = 420 möjligheter.
MEN om A har 02, så är det samma situation; ytterligare 420 möjligheter.
och samma om A har 03, 04, …, 08, 09 – dvs totalt 9 gånger 420 = 3780 förbjudna möjligheter.
Och 18900–3780 = 15120 godkända möjligheter.
Klart.
MEN
naytte har rätt. Det är faktiskt enklare att räkna som jag gjorde först i toppen av hela denna långa diskussion. Så här är en alternativ lösning.
Först får A välja. Hen kan välja 2 av 9 böcker. (9 över 2) kombinationer.
Sedan får B välja. Nu råder inga restriktioner, 8 titlar återstår. (8 över 2) kombinationer.
C har 6 böcker att välja bland. (6 över 2) kombinationer.
Multiplicerar vi får vi 9*8*8*7*6*5 / (2*2*2) = 9*8*7*6*5 kombinationer.
Vill man ha stilpoäng kan man svara 9! / 4! = 15120 möjliga val.
Säg till om något är oklart.
Anmärkning: Du kanske tycker det är onödigt med två lösningar. Men det är det inte. I kombinatorikproblem är man sällan helt säker. Därför är det ofta bra att testa om två olika lösningar ger samma resultat.
