Betrakt hjørnene i et regulært n-gon i planet med sentrum i origio. La disse være startpunktene.
La et trekk være å forflytte et punkt gjennom et annet med et heltallig multippel k > 1 av avstanden mellom dem.
Eksempel: Hvis vi betrakter en trekant vil et trekk være å forflytte det øverste hjørnet, punktet A, gjennom hjørnet til venstre, punktet B, med et multippel k av sidekanten mellom dem. Dvs. på linja gjennom punktene. Et videre trekk kan være å forflytte B gjennom hjørnet til høyre, punktet C, med et multippel k av lengden mellom B og C.
Er det mulig etter et endelig antall trekk å få et av de n punktene til å havne i origo?
n-gon
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Jeg har ingen fullstendig løsning, men tror jeg kan vise resultatet for primtallspotenser [tex]n=p^r[/tex]. La [tex]F=\mathbb{Q} [ \zeta][/tex] der [tex]\zeta[/tex] er en primitiv n-te rot av enheten være den n-te syklotomiske utvidelsen av Q. Det er da kjent at [tex][F:Q]=\phi(n)[/tex]. Betrakt så mengden [tex]B= \{ 1, \zeta, \ldots, \zeta^{\phi(n)-1 \}[/tex]. Vi har identiteten [tex]\sum_{k=0} ^{p-1} \zeta^{kp^{r-1}}=0[/tex], så vi har [tex]\zeta^a = -\sum_{k=1}^{p_-1} \zeta^{a+kp^{r-1}}[/tex] for alle [tex]a[/tex], så B utspenner F. Da F har dimensjon [tex]\phi(n)=|B|[/tex] som vektorrom over Q er B altså en basis for F.
Startpunktene er da enten elementer av denne basisen, og har derfor koordinater [tex](0, \ldots, 0, 1, 0, \ldots, 0)[/tex], eller har, av identiteten vår, koordinater der ethvert element enten er 0 eller -1 (der eksakt [tex]p[/tex] av koordinatene er -1). Spesielt er alle koordinatene til startpunktene i denne basisen forskjellige fra nullvektoren mod [tex]k[/tex]. (Siden [tex]k>1[/tex].)
Da et trekk som flytter punkt [tex]a[/tex] gjennom punkt [tex]b[/tex] flytter a til [tex]a+k(b-a) \equiv a \pmod k[/tex] ser vi at koordinatene (mod k) ikke endres av et trekk, og derfor ikke av en endelig følge av trekk. Siden koordinatene til alle startpunktene er forskjellige fra nullvektoren mod k, mens origo er nullvektoren mod k, er det umulig å få et av startpunktene til å havne i origo gjennom en endelig følge av trekk.
I fare for å ta veldig feil tror jeg et tilsvarende argument skal virke for det generelle tilfellet, men jeg har ikke klart det ennå.
Startpunktene er da enten elementer av denne basisen, og har derfor koordinater [tex](0, \ldots, 0, 1, 0, \ldots, 0)[/tex], eller har, av identiteten vår, koordinater der ethvert element enten er 0 eller -1 (der eksakt [tex]p[/tex] av koordinatene er -1). Spesielt er alle koordinatene til startpunktene i denne basisen forskjellige fra nullvektoren mod [tex]k[/tex]. (Siden [tex]k>1[/tex].)
Da et trekk som flytter punkt [tex]a[/tex] gjennom punkt [tex]b[/tex] flytter a til [tex]a+k(b-a) \equiv a \pmod k[/tex] ser vi at koordinatene (mod k) ikke endres av et trekk, og derfor ikke av en endelig følge av trekk. Siden koordinatene til alle startpunktene er forskjellige fra nullvektoren mod k, mens origo er nullvektoren mod k, er det umulig å få et av startpunktene til å havne i origo gjennom en endelig følge av trekk.
I fare for å ta veldig feil tror jeg et tilsvarende argument skal virke for det generelle tilfellet, men jeg har ikke klart det ennå.
Jepp, dette ser bra ut!
Hvis du ønsker et tips for det alternative tilfellet:
Hvis n ikke er en primtallspotens kan den faktoriseres til to relativt primske faktorer a og b mindre enn n. Betrakt den naturlige basisen for kropputvidelsen av Q med en primitiv a'te rot og b'te rot som arves fra basisene (som per induksjonshypotese utspenner kroppsutvidelsene over {-1,0,1}) til røttenes respektive kropputvidelser.
Det er godt mulig et tilsvarende argument vil fungere generelt. Legg gjerne ut en slik løsning hvis du finner en.
Hvis du ønsker et tips for det alternative tilfellet:
Hvis n ikke er en primtallspotens kan den faktoriseres til to relativt primske faktorer a og b mindre enn n. Betrakt den naturlige basisen for kropputvidelsen av Q med en primitiv a'te rot og b'te rot som arves fra basisene (som per induksjonshypotese utspenner kroppsutvidelsene over {-1,0,1}) til røttenes respektive kropputvidelser.
Det er godt mulig et tilsvarende argument vil fungere generelt. Legg gjerne ut en slik løsning hvis du finner en.
Jeg har prøvd litt, men ikke fått et tilsvarende argument til å virke i det generelle tilfellet. Induksjonstilnærmingen du beskriver i hintet virker uansett mye lettere, så etter å ha sett på tipset har jeg rotet meg fram til følgende:
Vi indukterer på [tex]n[/tex]. Anta at vi for alle [tex] 0 <n<k[/tex] har at det finnes en basis [tex]\{ 1, \zeta, \zeta ^2, \ldots, \zeta^{\phi(n)-1} \}[/tex](der [tex]\zeta[/tex] en primitiv [tex]n[/tex]-te rot av enheten) som utspenner punktene i et [tex]n[/tex]-gon over {-1,0,1}. Vi viser at det samme holder for [tex]n=k[/tex]. Vi har enten at [tex]k[/tex] kan skrives på formen [tex]k=ab[/tex] der [tex]a, b[/tex] er to relativt primiske heltall strengt mindre enn [tex]k[/tex], eller at [tex]k[/tex] er en primtallspotens. Om [tex]k[/tex] er en primtallspotens gir den forrige posten min at konklusjonen holder.
Anta så at [tex]k=ab[/tex]. Vi har da at det finnes basiser for [tex]a[/tex] og [tex]b[/tex] som utspenner de respektive kroppsutvidelsene over {-1, 0, 1} som beskrevet. Med andre ord kan enhver [tex]a[/tex]-te rot av enheten skrives (unikt) på formen [tex]a_0+a_1 \zeta_a + \ldots +a_{\phi(a)-1}\zeta_a^{\phi(a)-1}[/tex], der [tex]a_i \in \{-1, 0, 1 \}[/tex], og tilsvarende for [tex]b[/tex]. Betrakt så mengden [tex]B[/tex] bestående av alle elementer som er produkter av ett element fra hver av de to basene. Vi har da [tex]|B|=\phi(a) \phi(b)=\phi(ab)=\phi(k)[/tex].
Dessuten har vi at enhver [tex]ab[/tex]-te rot av enheten kan skrives som produktet av en a-te rot og en b-te rot av enheten (siden [tex]a[/tex]og [tex]b[/tex] er relativt primiske), som henholdsvis kan skrives som nevnt før på formen [tex]a_0+a_1 \zeta + \ldots +a_{\phi(a)-1}\zeta^{\phi(a)-1}[/tex] som beskrevet før, og tilsvarende er b-te roten i produktet på formen [tex]b_0+b_1 \zeta_b + \ldots +b_{\phi(b)-1}\zeta_b^{\phi(b)-1}[/tex]. Ganger vi så sammen disse to uttrykkene får vi et uttrykk på formen [tex]\sum c_{i,j} \zeta_a ^i \zeta_b ^j[/tex], der [tex]c_{i,j}=a_ib_j[/tex], så [tex]c_{i,j} \in \{-1, 0, 1 \}[/tex]. Elementene [tex]\zeta_a^i \zeta_b ^j[/tex] er jo elementene av mengden B, så vi har at mengden B utspenner kroppsutvidelsen F av Q med en k-te rot av enheten over [tex]\{-1,0,1\}[/tex] (siden [tex]|B|=\phi(k)=[F:Q][/tex] er dette da en basis for utvidelsen), og vi er ferdige: vi har funnet en basis som oppfyller kravet vårt.
Altså har vi vist at kroppsutvidelsen F av Q alltid har en basis slik at startpunktene utspennes av [tex]\{-1, 0, 1 \}[/tex]. Det samme argumentet som tidligere gir da at startpunktenes koordinater ikke endres mod [tex]k[/tex] (her brukt i betydningen 'hopplengden'), og da ingen av startpunktene er lik origo (som er det eneste punktet som er null mod k som utspennes av [tex]\{-1,0,1\}[/tex]) i utgangspunktet kan ingen av dem bli det etter en endelig sekvens trekk.
Vi indukterer på [tex]n[/tex]. Anta at vi for alle [tex] 0 <n<k[/tex] har at det finnes en basis [tex]\{ 1, \zeta, \zeta ^2, \ldots, \zeta^{\phi(n)-1} \}[/tex](der [tex]\zeta[/tex] en primitiv [tex]n[/tex]-te rot av enheten) som utspenner punktene i et [tex]n[/tex]-gon over {-1,0,1}. Vi viser at det samme holder for [tex]n=k[/tex]. Vi har enten at [tex]k[/tex] kan skrives på formen [tex]k=ab[/tex] der [tex]a, b[/tex] er to relativt primiske heltall strengt mindre enn [tex]k[/tex], eller at [tex]k[/tex] er en primtallspotens. Om [tex]k[/tex] er en primtallspotens gir den forrige posten min at konklusjonen holder.
Anta så at [tex]k=ab[/tex]. Vi har da at det finnes basiser for [tex]a[/tex] og [tex]b[/tex] som utspenner de respektive kroppsutvidelsene over {-1, 0, 1} som beskrevet. Med andre ord kan enhver [tex]a[/tex]-te rot av enheten skrives (unikt) på formen [tex]a_0+a_1 \zeta_a + \ldots +a_{\phi(a)-1}\zeta_a^{\phi(a)-1}[/tex], der [tex]a_i \in \{-1, 0, 1 \}[/tex], og tilsvarende for [tex]b[/tex]. Betrakt så mengden [tex]B[/tex] bestående av alle elementer som er produkter av ett element fra hver av de to basene. Vi har da [tex]|B|=\phi(a) \phi(b)=\phi(ab)=\phi(k)[/tex].
Dessuten har vi at enhver [tex]ab[/tex]-te rot av enheten kan skrives som produktet av en a-te rot og en b-te rot av enheten (siden [tex]a[/tex]og [tex]b[/tex] er relativt primiske), som henholdsvis kan skrives som nevnt før på formen [tex]a_0+a_1 \zeta + \ldots +a_{\phi(a)-1}\zeta^{\phi(a)-1}[/tex] som beskrevet før, og tilsvarende er b-te roten i produktet på formen [tex]b_0+b_1 \zeta_b + \ldots +b_{\phi(b)-1}\zeta_b^{\phi(b)-1}[/tex]. Ganger vi så sammen disse to uttrykkene får vi et uttrykk på formen [tex]\sum c_{i,j} \zeta_a ^i \zeta_b ^j[/tex], der [tex]c_{i,j}=a_ib_j[/tex], så [tex]c_{i,j} \in \{-1, 0, 1 \}[/tex]. Elementene [tex]\zeta_a^i \zeta_b ^j[/tex] er jo elementene av mengden B, så vi har at mengden B utspenner kroppsutvidelsen F av Q med en k-te rot av enheten over [tex]\{-1,0,1\}[/tex] (siden [tex]|B|=\phi(k)=[F:Q][/tex] er dette da en basis for utvidelsen), og vi er ferdige: vi har funnet en basis som oppfyller kravet vårt.
Altså har vi vist at kroppsutvidelsen F av Q alltid har en basis slik at startpunktene utspennes av [tex]\{-1, 0, 1 \}[/tex]. Det samme argumentet som tidligere gir da at startpunktenes koordinater ikke endres mod [tex]k[/tex] (her brukt i betydningen 'hopplengden'), og da ingen av startpunktene er lik origo (som er det eneste punktet som er null mod k som utspennes av [tex]\{-1,0,1\}[/tex]) i utgangspunktet kan ingen av dem bli det etter en endelig sekvens trekk.
Dette ser riktig ut, men en liten ting gjenstår å vise: at [tex]\zeta_a^i\zeta_b^j[/tex] kun oppstår èn gang i summen over [tex]c_{ij}\zeta_a^i\zeta_b^j[/tex], for hvis ikke kan vi få en rot med et slikt ledd: [tex](c_{i_1j_1}+c_{i_2j_2})\zeta_a^{i_1}\zeta_b^{j_1}[/tex] som har en koeffisient som ikke nødvendigvis ligger i {-1,0,1}.
Det viste jeg ikke, nei. Kan tette hullet nå: [tex]i[/tex] løper i summen fra og med 0 til og med [tex]\phi(a)-1[/tex], og tilsvarende for [tex]j[/tex]. Altså får vi kun problemer dersom [tex]\zeta_a ^{i_1} \zeta_b ^{j_1} =\zeta_a ^{i_2} \zeta_a ^{j_2}[/tex] for distinkte [tex]i_1, i_2[/tex] og distinkte [tex]j_1, j_2[/tex]. Anta at dette skjer. Skriver vi [tex]\zeta_a=e^{\frac {2\pi i} a}[/tex] (i er her den imaginære enheten, men kommer fra nå av kun til å være en summasjonsindeks) og tilsvarende for b får vi at dette er ekvivalent med [tex]bi_1 +aj_1 \equiv bi_2 + aj_2 \pmod {ab}[/tex], som igjen gir at [tex]b(i_1-i_2) \equiv a(j_2-j_1) \pmod {ab}[/tex], så [tex]a[/tex] deler [tex]|i_1-i_2|[/tex]. Men dette er umulig, da dette er et positivt tall strengt mindre enn [tex]\phi(a)<a[/tex], og vi har en motsigelse. Altså opptrer [tex]\zeta_a ^i \zeta_b ^j[/tex] kun én gang i summen.