La $n>2$ være et heltall. En kortstokk inneholder $\frac{n(n-1)}{2}$ kort, nummerert
\[1,2,3,\dotsc,\frac{n(n-1)}{2}.\]
To kort danner et magisk par hvis tallene er påfølgende, eller hvis tallene på de er $1$ og $\frac{n(n-1)}{2}$. For hvilke $n$ er det mulig å fordele kortene i $n$ bunker på en slik måte at det finnes nøyaktig ett magisk par blant kortene i hvilke som helst to bunker?
Baltic Way kombinatorikk
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Problemet kan løses vha. grafteori: Konstruerer en urettet graf med n noder som representerer de n bunkene. Mellom hvert par av noder lager vi én kant, som representerer at vi plukker ut dette paret (så det blir n(n-1)/2 kanter). Da er det mulig å fordele kortene slik at hvert par av bunker inneholder eksakt ett magisk par, hvis og bare hvis grafen er en eulersk krets (Eulerian cycle). Dette inntreffer kun når alle nodene har partallig grad, og dette skjer når n er odde.
Fordelingen av kort foregår altså ved å følge den eulerske kretsen der vi legger fra oss kortene i kronologisk rekkefølge ettersom vi følger kretsen.
Figuren viser en mulig fordeling av 10 kort når n=5, der vi starter med å legge kort nr. 1 i bunken helt til venstre. Deretter kort nr. 2 i bunken helt til høyre etc. Ved å følge tallene i kronologisk rekkefølge får vi en krets som bruker hver kant én gang og ender opp ved startnoden. Vi ser at hver node har grad 4.
edit
Fordelingen av kort foregår altså ved å følge den eulerske kretsen der vi legger fra oss kortene i kronologisk rekkefølge ettersom vi følger kretsen.
Figuren viser en mulig fordeling av 10 kort når n=5, der vi starter med å legge kort nr. 1 i bunken helt til venstre. Deretter kort nr. 2 i bunken helt til høyre etc. Ved å følge tallene i kronologisk rekkefølge får vi en krets som bruker hver kant én gang og ender opp ved startnoden. Vi ser at hver node har grad 4.
edit
Ja jeg løsningen min var litt annerledes; brukte induksjon på $n$.
Åpenbart kan ikke to kort i samme bunke danne et magisk par med seg selv. Hvis $n$ er et partall finnes det ifølge skuffeprinsippet en bunke $b$ med minst $\lceil\frac{n}{2}\rceil$ kort, og siden av ingen av disse danner magiske par med hverandre, danner de nøyaktig $2\lceil\frac{n}{2}\rceil=n+1$ magiske par totalt med de andre bunkene. Men da finnes det ifølge skuffeprinsippet en annen bunke som danner minst to par med $b$, slik at betingelsene ikke blir tilfredsstilt; en ønsket fordeling er derfor umulig når $2\mid n$.
Vi skal nå vise ved induksjon at en ønsket fordeling er mulig for alle odde $n$. Tilfellet $n=3$ løses ved å fordele ett kort til hver bunke. Anta nå at en fordeling som tilfredsstiller betingelsene er mulig for situasjonen hvor $n=2m-1$. Betrakt denne fordelingen, og introdusér to nye bunker $a$ og $b$ i tillegg til de $2m-1$ bunkene $v_1,v_2,\dotsc,v_{2m-1}$ vi har fra før av. Videre bruker vi grafteori (for enkelhetens skyld) slik at bunkene denoteres ved hjørner og et magisk par ved en kant.
Først forbinder vi $a$ og $b$ med en kant $(b,a)$. Deretter forbinder vi $v_1$ med disse to ved hjelp av kantene $(a,v_1)$ og $(v_1,b)$. Videre forbindes $v_2$ med $a$ og $b$ på samme måte, med kantene $(b,v_2)$ og $(v_2),a$. Vi fortsetter på samme måte, slik at alle kantene som legges til er:
\begin{align*}
(b,a)\\
(a,v_1)&,(v_1,b)\\
(b,v_2)&,(v_2,a)\\
(a,v_3)&,(v_3,b)\\
&\vdots \\
(a,v_{2m-1})&,(v_{2m-1},b)
\end{align*}
Nå legger vi ut tallene i stigende rekkefølge slik at kantene beskrevet rett ovenfor dannes, i den rekkefølgen de står. Da forbindes $a$ og $b$ med alle de andre hjørnene, og ifølge induksjonshypotesen står vi igjen med en komplett graf av størrelse $2m+1$, som ønsket. (Burde kanskje ha med noen setninger om at ingen par av kanter forbinder de samme to hjørnene, pluss at alle par av hjørner er forbundet med kanter, osv...)
Løsningen er litt "bare-hands" i stilen, men med litt renskriving tror jeg det blir ryddigere med induksjon enn den offisielle løsningen som viste en konstruksjon fra bunnen av for $n$ punkter. Det mest elegante er jo selvfølgelig å gjenkjenne at en Euler-circuit finnes, slik som du gjorde.
Åpenbart kan ikke to kort i samme bunke danne et magisk par med seg selv. Hvis $n$ er et partall finnes det ifølge skuffeprinsippet en bunke $b$ med minst $\lceil\frac{n}{2}\rceil$ kort, og siden av ingen av disse danner magiske par med hverandre, danner de nøyaktig $2\lceil\frac{n}{2}\rceil=n+1$ magiske par totalt med de andre bunkene. Men da finnes det ifølge skuffeprinsippet en annen bunke som danner minst to par med $b$, slik at betingelsene ikke blir tilfredsstilt; en ønsket fordeling er derfor umulig når $2\mid n$.
Vi skal nå vise ved induksjon at en ønsket fordeling er mulig for alle odde $n$. Tilfellet $n=3$ løses ved å fordele ett kort til hver bunke. Anta nå at en fordeling som tilfredsstiller betingelsene er mulig for situasjonen hvor $n=2m-1$. Betrakt denne fordelingen, og introdusér to nye bunker $a$ og $b$ i tillegg til de $2m-1$ bunkene $v_1,v_2,\dotsc,v_{2m-1}$ vi har fra før av. Videre bruker vi grafteori (for enkelhetens skyld) slik at bunkene denoteres ved hjørner og et magisk par ved en kant.
Først forbinder vi $a$ og $b$ med en kant $(b,a)$. Deretter forbinder vi $v_1$ med disse to ved hjelp av kantene $(a,v_1)$ og $(v_1,b)$. Videre forbindes $v_2$ med $a$ og $b$ på samme måte, med kantene $(b,v_2)$ og $(v_2),a$. Vi fortsetter på samme måte, slik at alle kantene som legges til er:
\begin{align*}
(b,a)\\
(a,v_1)&,(v_1,b)\\
(b,v_2)&,(v_2,a)\\
(a,v_3)&,(v_3,b)\\
&\vdots \\
(a,v_{2m-1})&,(v_{2m-1},b)
\end{align*}
Nå legger vi ut tallene i stigende rekkefølge slik at kantene beskrevet rett ovenfor dannes, i den rekkefølgen de står. Da forbindes $a$ og $b$ med alle de andre hjørnene, og ifølge induksjonshypotesen står vi igjen med en komplett graf av størrelse $2m+1$, som ønsket. (Burde kanskje ha med noen setninger om at ingen par av kanter forbinder de samme to hjørnene, pluss at alle par av hjørner er forbundet med kanter, osv...)
Løsningen er litt "bare-hands" i stilen, men med litt renskriving tror jeg det blir ryddigere med induksjon enn den offisielle løsningen som viste en konstruksjon fra bunnen av for $n$ punkter. Det mest elegante er jo selvfølgelig å gjenkjenne at en Euler-circuit finnes, slik som du gjorde.
-
Gjest
First assume a stack contains two cards that form a magic pair; say cards number i and i + 1.
Among the cards in this stack and the stack with card number i + 2 (they might be identical), there are two magic pairs — a contradiction. Hence no stack contains a magic pair.
Each card forms a magic pair with exactly two other cards. Hence if n is even, each stack must contain at least ⌈ n−1 ⌉ = n cards, since there are n − 1 other stacks. But then we need at least
22
nn > n(n−1) cards — a contradiction. 22
In the odd case we distribute the cards like this: Let a1, a2, . . . , an be the n stacks and let n = 2m+1. Card number 1 is put into stack a1. If card number km + i, for i = 1,2,...,m, is put into stack aj, then card number km+i+1 is put into stack number aj+i, where the indices are calculated modulo n.
There are
n(n−1) = (2m+1)(2m) =m(2m+1) 22
cards. If we look at all the card numbers of the form km + 1, there are exactly n = 2m + 1 of these, and we claim that there is exactly one in each stack. Card number 1 is in stack a1, and card number km+1 is in stack
Since
a1+k(1+2+3+···+m). 1+2+3+···+m= m(m+1)
and gcd(2m + 1, m(m+1) ) = 1, all the indices 2
1 + k(1 + 2 + 3 + · · · + m), k = 0, 1, 2, . . . , 2m
are different modulo n = 2m + 1. In the same way we see that each stack contains exactly one of the 2m + 1 cards with the numbers km + i for a given i = 2, 3, . . . , m.
Now look at two different stacks av and au. Then, without loss of generality, we may assume that u = v + i for some i = 1,2,...,m (again we consider the index modulo n = 2m + 1). Since there is a card in stack av with number km+i, the card km+i+1 is in stack av+i = au. Hence among the cards in any two stacks there is at least one magic pair. Since there is the same number of pairs of stacks as of magic pairs, there must be exactly one magic pair among the cards of any two stacks.
Solution 2 (found by Saint Petersburg). For the case of n odd, consider the complete graph on the vertices 1, . . . , n with n(n−1) edges. The degree of each vertex is n − 1, which is even, hence an Euler
2
cycle v1v2 ···vn(n−1) v1 exists. Place card number i into stack number vi. The magic pairs correspond 2
to edges in the cycle.
Among the cards in this stack and the stack with card number i + 2 (they might be identical), there are two magic pairs — a contradiction. Hence no stack contains a magic pair.
Each card forms a magic pair with exactly two other cards. Hence if n is even, each stack must contain at least ⌈ n−1 ⌉ = n cards, since there are n − 1 other stacks. But then we need at least
22
nn > n(n−1) cards — a contradiction. 22
In the odd case we distribute the cards like this: Let a1, a2, . . . , an be the n stacks and let n = 2m+1. Card number 1 is put into stack a1. If card number km + i, for i = 1,2,...,m, is put into stack aj, then card number km+i+1 is put into stack number aj+i, where the indices are calculated modulo n.
There are
n(n−1) = (2m+1)(2m) =m(2m+1) 22
cards. If we look at all the card numbers of the form km + 1, there are exactly n = 2m + 1 of these, and we claim that there is exactly one in each stack. Card number 1 is in stack a1, and card number km+1 is in stack
Since
a1+k(1+2+3+···+m). 1+2+3+···+m= m(m+1)
and gcd(2m + 1, m(m+1) ) = 1, all the indices 2
1 + k(1 + 2 + 3 + · · · + m), k = 0, 1, 2, . . . , 2m
are different modulo n = 2m + 1. In the same way we see that each stack contains exactly one of the 2m + 1 cards with the numbers km + i for a given i = 2, 3, . . . , m.
Now look at two different stacks av and au. Then, without loss of generality, we may assume that u = v + i for some i = 1,2,...,m (again we consider the index modulo n = 2m + 1). Since there is a card in stack av with number km+i, the card km+i+1 is in stack av+i = au. Hence among the cards in any two stacks there is at least one magic pair. Since there is the same number of pairs of stacks as of magic pairs, there must be exactly one magic pair among the cards of any two stacks.
Solution 2 (found by Saint Petersburg). For the case of n odd, consider the complete graph on the vertices 1, . . . , n with n(n−1) edges. The degree of each vertex is n − 1, which is even, hence an Euler
2
cycle v1v2 ···vn(n−1) v1 exists. Place card number i into stack number vi. The magic pairs correspond 2
to edges in the cycle.