Problem med kortlek - kombinatoriskt under bestämda förutsättningar
Ur en kortlek dras 16 kort, 2 st av äss, ettor, tvåor, ... , sjuor, åttor. Alltså åtta par. Dessa placeras sedan på en rad så att åttorna har åtta kort mellan sig, sjuorna har sju kort mellan sig och så vidare. På vilket/vilka sätt kan detta göras på?
Jag inledde med att försöka lösa problemet algebraiskt, detta genom att teckna en variabel för varje valör med två olika index (en för vardera kort i paret). Variabelns värde motsvarar då positionen (1-16). Vi vet också att inga variabler får vara lika. Detta ekvationssystem gick dock ej så bra då det tillkommer 16 variabler, men bara presenteras 8 stycken ekvationer.
Jag har dessutom grafiskt tecknat vilka kort som kan befinna sig på olika positioner, men det enda resultatet som gavs av detta var att ingen av åttorna kan placeras på position 8.
Självfallet skulle det säkert gå att testa sig fram, genom att exempelvis testa alla möjliga värden åttorna vilket kanske sedan skulle förenkla processen att hitta de enda möjliga värdena, men jag vill gärna lösa det algebraiskt. Om också möjligt vill jag sedan teckna en generalisering för n antal kort ur en kortlek.
En tanke var om problemet kan betraktas kombinatoriskt ur strikta förutsättningar?
Jag föredrar ledningar framför lösningar då jag gärna själv vill komma fram till ett svar.
Tråd flyttad från Kluringar till Allmänna diskussioner. Kluringforumet är endast till för matematiska delikatesser du vill bjuda andra på. /Smutstvätt, moderator
Välkommen till Pluggakuten!
Vilken nivå studerar du matematik på? Det är lättare för oss som svarar om vi vet hur mycket matte du har läst, exempelvis lär man sig att använda kombinationer och permutationer i Ma5 så om du inte läst (eller läser) den kursen bör vi förklara de här utan att använda dessa begrepp. Forumdelen Kluringar är inte till för uppgifter du vill ha hjälp med, utan för kluriga problem där du et svaret och vill ge dina medmänniskor en trevlig uppgift att fundera på. Du kan själv flytta din tråd till rätt nivå genom att redigera ditt förstainlägg. /moderator
Jag går i nian, men har läst gymnasiematematik upp till Ma3 och har också koll på kombinationer samt permutationer så det är helt okej att förklara med dessa begrepp.
Kul problem! Jag ser ingen uppenbar lösning. Något man nog kan göra är att se fall som det INTE går att göra över huvudtaget. Exempelvis så tror jag att det går att visa att 9 eller 10 kortpar inte skulle fungera. Har du något exempel på där det faktiskt går?
Det känns mer som ett kombinatoriskt problem än ett algebraiskt problem till naturen (eller programmering, någon slags villkorsprogrammering borde kunna leta upp eventuella lösningar).
3 fungerar.
4 också.
JohanB skrev:Kul problem! Jag ser ingen uppenbar lösning. Något man nog kan göra är att se fall som det INTE går att göra över huvudtaget. Exempelvis så tror jag att det går att visa att 9 eller 10 kortpar inte skulle fungera. Har du något exempel på där det faktiskt går?
Det känns mer som ett kombinatoriskt problem än ett algebraiskt problem till naturen (eller programmering, någon slags villkorsprogrammering borde kunna leta upp eventuella lösningar).
Låter som ett bra tillvägagångssätt för en generalisering. Men vilken metod kan man använda för att till exempel visa att det finns ett sätt (vilket vi utgår ifrån i uppgiften) för 8 kort samt vilket sätt det är? Hur skulle villkorsprogrammering se ut i detta fall?
Av n < 14 går 3, 4, 7, 8, 11 och 12 men inga andra. Sen går 15 och 16 också. 14 provade jag inte. När det går så producerar mitt program lösningar väldigt fort.
Man kan skönja ett mönster.
Laguna skrev:Av n < 14 går 3, 4, 7, 8, 11 och 12 men inga andra. Sen går 15 och 16 också. 14 provade jag inte. När det går så producerar mitt program lösningar väldigt fort.
Man kan skönja ett mönster.
Fantastiskt! Vilket spännande mönster. Vore verkligen kul att se om det går att bevisa att samma mönster gäller för alla tal n under en viss gräns varefter inga tal fungerar. Vad för program är det du har utformat? Eller snarare hur skrev du koden?
Här är mitt program:
import sys
n = int(sys.argv[1])
def look(l, k, n):
if k == 0:
print(l)
return
for i in range(0, 2*n-k-1):
if l[i] == 0 and l[i+k+1] == 0:
l2 = l[:]
l2[i] = k
l2[i+k+1] = k
look(l2, k-1, n)
look([0]*(2*n), n, n)
Idén är att försöka placera de högsta korten först.
Laguna skrev:Här är mitt program:
import sys
n = int(sys.argv[1])
def look(l, k, n):
if k == 0:
print(l)
return
for i in range(0, 2*n-k-1):
if l[i] == 0 and l[i+k+1] == 0:
l2 = l[:]
l2[i] = k
l2[i+k+1] = k
look(l2, k-1, n)
look([0]*(2*n), n, n)
Idén är att försöka placera de högsta korten först.
Tack så mycket! Verkligen spännande koncept att undersöka. Och hur långt mönstret håller är också en intressant fråga.
Jag bara gissar, men jag gissar att det gäller obegränsat långt.
Ett sätt att upptäcka oändligt många fall det inte fungerar på är att studera kortplatserna. Vi färgar de platserna vi lägger kort på svart eller vitt (omväxlande). Eftersom det totalt är ett jämnt antal kort så behövs lika många svarta som vita platser. Prova att räkna antalet platser som behövs via kortvalörerna också (paret med tvåor behöver exempelvis en svart och en vit plats).
Mitt program upptäckte en intressant sak: det gick mycket snabbt att hitta lösningar ända upp till 43 och 44, men för 47 har jag inte fått några lösningar ännu. Inte 48 heller, men däremot 52. Men inte 51. Sedan hittar jag lösningar fläckvis (och det börjar ta några sekunder också.) Högsta jag provade och fick lösningar för hittills var 83.
Jag borde studera hur lösningarna ser ut också, det finns säkert mönster som upprepar sig.
Laguna skrev:Mitt program upptäckte en intressant sak: det gick mycket snabbt att hitta lösningar ända upp till 43 och 44, men för 47 har jag inte fått några lösningar ännu. Inte 48 heller, men däremot 52. Men inte 51. Sedan hittar jag lösningar fläckvis (och det börjar ta några sekunder också.) Högsta jag provade och fick lösningar för hittills var 83.
Jag borde studera hur lösningarna ser ut också, det finns säkert mönster som upprepar sig.
Spännande! Att talen n=4r+1 och n=4r+2 ej kan sorteras korrekt är bevisat på grund av Johans resonemang om växelvis indelning i två grupper. Således får vi att antalet udda par ej får vara udda vilket de är i dessa två fall. Således är den delen klargjord men den slumpmässiga karaktären hos högre tal är ju väldigt intressant.
