Tænkeboks: Hvad er det maksimale antal tripler?
more_vert
close

Få de daglige nyheder fra Version2 og Ingeniøren. Læs mere om nyhedsbrevene her.

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser, og du accepterer, at Teknologiens Mediehus og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, job og tilbud m.m. via telefon og e-mail. I nyhedsbreve, e-mails fra Teknologiens Mediehus kan der forefindes markedsføring fra samarbejdspartnere.

Tænkeboks: Hvad er det maksimale antal tripler?

Illustration: Ingeniøren

Denne uges opgave er fra professor Lars Døvling Andersen, Institut for matematiske fag ved Aalborg Universitet:

Opgave 17: Her er 7 tripler udtaget fra mængden {1,2,3,4,5,6,7}:

{1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3}

(Et tripel består af forskellige elementer). Triplerne har egenskaben (*): Intet par af elementer forekommer sammen i mere end ét tripel.

Da alle par forekommer i triplerne ovenfor, er 7 klart det maximale antal tripler fra mængden {1,2, …, 7}.

– Hvad er det maximale antal tripler, der opfylder (*), udtaget fra mængden {1,2, …, n} for n lig med henholdsvis 8,9,10,11 og 12?
– – –

Vi bringer løsningen i næste uge, men fra søndag eftermiddag ligger opgaven også på adressen ing.dk/fokus/taenkeboksen, hvor I kan diskutere jeres forslag til løsninger.

/ Lynch

Illustration: MI Grafik
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Løsningerne må være i disse intervaller: 8: 24, 9: 27-36, 10: 30-40, 11: 33-55, 12: 36-60. Jeg leder stadig efter den gyldne visdom som kan finde det rigtige tal (ud over at prøve sig frem, og det synes jeg ikke er sjovt).

  • 0
  • 0

OK Kim, jeg er kommet frem til andet resultat; 8: 8; 9:9; 10:10; 11:11; 12:16. Det med at prøve sig frem, ja det blev hurtigt svært og uoverskueligt.
Nå jeg så på løsningen med n=7 og satte tallene op i en urskive med 1-7 og tegnede triplen (1, 2, 4), så kunne jeg se at de andre tripler kom frem ved at dreje denne løsning rundt i urskiven. Hvert tal går igen 3 gange, med naboen til venstre + genboen til højre, naboen til højre med med gen-genboen til højre, genboen til venstre og gen-genboen til venstre.
Med n=8, 9, 10 eller 11 får jeg at de nye kombinationer kommer til at indeholde naboer, genboer eller gen-genboer, og alle de kombinationer er indeholdt. Kun med n=12, kan jeg lave 4 tripletter med ækvadistante talkombinationer uden naboer, genboer eller gen-genboer.
Vel. Intuitivt synes jeg, at mine antal kombinationer virker små, så jeg må overveje om der er smuttet noget i min analyse.

  • 0
  • 0

Ha, jeg har glemt at det var antallet af tripler, man skulle svare, jeg har skrevet antal af par, der kunne fordeles i tripler, så det skal være intervallerne: 8: 8, 9: 9-12, 10: 10-39, 11: 11-18 og 12: 12-20.

  • 1
  • 0

1;2;3;4;5;6;7;8;9;10;11;12
Kunne efterfølgende være opskriften, i det to på hinanden følgende tal ikke optræder mere end en gang, eller har jeg misforstået noget?

1 2 4
2 3 5
3 4 6
4 5 7
5 6 8
6 7 9
7 8 10
8 9 12
9 10 , 1
10 11, 2
11 12 , 3
12, 1 , 4

  • 0
  • 0

Jeg får samme øvre grænse for antallet af tripler som Kim Bygum: 8: 8, 9: 12, 10: 13, 11: 18 og 12: 20. Et generelt udtryk for den øvre grænse er floor[n * floor[(n-1)/2]/3], hvor floor[] betyder rundet ned til nærmeste heltal.

Udtrykket opstår som følger: Hvert tal kan maksimalt indgå i floor[(n-1)/2] tripler. For eksempel hvis n=8 kan tallet 1 kun indgå i 3 tripler, fx {1,2,3}, {1,4,5} og {1,6,7}. Selvom 1 endnu ikke er blevet "parret" med tallet 8, er det blevet parret med alle andre tal, og der kan derfor ikke laves flere tripler hvor 1 indgår. Hvis alle n tal indgår i det maksimale antal tripler, har vi nfloor[(n-1)/2] elementer vi kan lave tripler med. Det maksimale antal tripler vi kan lave af dette er floor[nfloor[(n-1)/2]/3].

For n = 8, 9, 10 og 12 er det lykkedes mig at finde eksempler på hvordan den øvre grænse kan nås, ved hjælp af et simplet python-script bestående af en funktion, der kalder sig selv rekursivt. Men for n = 11 har jeg prøvet alle mulige kombinationer, så jeg tror ikke den øvre grænse ikke nås (ligesom den ikke kan for 5). Så for 11 bliver det reelle antal tripler altså 17 i stedet for 18.

Eksempler på maksimale antal tripler:

n=8; 8 tripler:
{{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,8},{3,5,7},{3,6,8},{4,7,8}}

n=9; 12 tripler
{{1,2,3},{1,4,5},{1,6,7},{1,8,9},{2,4,6},{2,5,8},{2,7,9},{3,4,9},{3,5,7},{3,6,8},{4,7,8},{5,6,9}}

n=10; 13 tripler:
{{1,2,3},{1,4,5},{1,6,7},{1,8,9},{2,4,6},{2,5,7},{2,8,10},{3,4,8},{3,5,9},{3,7,10},{4,7,9},{5,6,8},{6,9,10}}

n=11; 17 tripler (18 ikke muligt):
{{1,2,3},{1,4,5},{1,6,7},{1,8,9},{1,10,11},{2,4,6},{2,5,7},{2,8,10},{2,9,11},{3,4,8},{3,5,9},{3,6,11},{3,7,10},{4,7,9},{5,6,8},{6,9,10},{7,8,11}}

n=12; 20 tripler:
{{1,2,3},{1,4,5},{1,6,7},{1,8,9},{1,10,11},{2,4,6},{2,5,7},{2,8,10},{2,9,12},{3,4,8},{3,5,9},{3,6,10},{3,11,12},{4,7,11},{4,10,12},{5,6,12},{5,8,11},{6,9,11},{7,8,12},{7,9,10}}

Hvordan man kan forudse om den ovenståennde øvre grænse faktisk kan nås for et givent n, ved jeg ikke.

  • 0
  • 0

Kunne efterfølgende være opskriften, i det to på hinanden følgende tal ikke optræder mere end en gang, eller har jeg misforstået noget?

Nej, det er en gyldig løsning og kan laves for alle n >= 7. Men det giver kun et minimum for antallet af tripler, der kan for nogle tal være flere.

Jeg har fundet et maksimum antal tripler ved, at der for hver triplet skal "bruges" tre par, som indeholder 3 tal 2 gange hver. Dvs. hvis hvert tal indgår i fx 9 forskellige par (for n=10, kan det kun bruges til 4 tripletter, og det sætter en max på. 4x10=40 par eller 13 tripletter (jeg ved godt, jeg kom til at skrive 39 i min 2. post ovenfor).

Edit: Så at Jeppe har valgt samme strategi. Jeg mangler stadig at kunne beregne hvor mange der så rent kombinatorisk kan placeres. Der er fx ganske få tripletter for n=6 (og ikke 6, som man kunne tro)

  • 0
  • 0

Faktisk passer pengene for n=6. Her kan hvert tal maks indgå i 2 tripler, hvilket giver 2*6=12 "byggesten", af hvilke kan bygges maksimalt 4 tripler. Det kan man fx gøre således: {1,2,3}, {1,4,5}, {2,4,6}, {3,5,6}.

Men for n=5 og n=11 er det ikke muligt at nå den øvre grænse på hhv 3 og 18 tripler. Hvordan man udleder at det korrekte antal tripler her er hhv 2 og 17 i stedet, kan jeg ikke regne ud.

  • 1
  • 0

Eksemplet fra opgaven starter med 1,2,4 og så cyklisk forskydning/rotation.
Kunne man få det samme antal tripler (i andre kombinationer) hvis man var startet anderledes og med et andet system? Elementet 1,2,3 optræder jo ikke selvom Jeppe Juul starter med 1,2,3 i sin udvikling.

Det er godt nok en spøjs opgave.

  • 0
  • 0

I hvert for n=7 og n=8 findes der kun een løsning. Men denne kan selvfølgelig tage forskellige former ved at bytte om på tallenes rækkefølge og placering.

Fx: Jeg har opskrevet løsningen for n=8 så 1 "opbruges" først, derefter 2, 3, 4 osv., da jeg godt kan lide denne systematik:

{{1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,8},{3,5,7},{3,6,8},{4,7,8}}

Men hvis man substituerer 3->4, 4->8, 5->3, 6->7, 7->6 og 8->5 får man:

{{1,2,4},{1,8,3},{1,7,6},{2,8,7},{2,3,5},{4,3,6},{4,7,5},{8,6,5}}

Hvilket så kan sorteres så det matcher systematikken i opgavens løsning for n=7:

{{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,8},{6,7,1},{7,8,2},{8,1,3}}

  • 0
  • 0

Ja, mit script finder den optimale løsning ved at prøve alle kombinationer "fra en ende af".

Når jeg så har fundet den optimale løsning, opskriver jeg denne efter den systematik jeg beskriver: Først "opbruges" 1, så 2 osv. :)

  • 1
  • 0

Jeg synes at opgaven er uklart formuleret. Man skal altså udtage tripler så alle elementer er med mindst i een tripel, og hvert par med i højst een tripel, dvs. at der er OK at udelade et par. Det er ikke specielt klart, men fremgår af de fremlagte løsninger i den følgende uge. Jeg kan heller ikke forstå, hvorfor det er særlig interessant. Jeg kunne forestille mig, at man til testformål af software eller hardware systemer er mere interesseret i det laveste antal tripler, hvor hvert par er med mindst een gang.

  • 0
  • 1
Bidrag med din viden – log ind og deltag i debatten