IMO 2009, oppgave 1

[Karl_Erik]

La [tex]n[/tex] være et positivt heltall og [tex]a_1, a_2, ... a_k[/tex] være forskjellige heltall fra mengden [tex]\left { 1, 2, 3, ... , n \right } [/tex] slik at [tex]n[/tex] deler [tex]a_i(a_{i+1} -1)[/tex] for [tex]i=1, 2, ... , k-2, k-1[/tex]. Vis at [tex]n[/tex] ikke deler [tex]a_k(a_1-1)[/tex]

[Magnus]

Gratulerer med hederlig omtale Karl Erik! Vil også gratulere Zivert og Jarle:) (og de andre om de befinner seg her)

[Magnus]

Prøver igjen ettersom jeg presterte å skru av PCen rett før jeg skulle poste sist. Klønete kan man si.

Anta først at [tex]n|a_1[/tex] i så tilfelle må [tex]a_1=n[/tex] og [tex]n|a_k[/tex], men det går ikke for [tex]a_k < n[/tex]. [tex]n[/tex] kan åpenbart ikke dele [tex]a_2-1[/tex] da [tex]a_2\leq n[/tex].

Så anta [tex]n=pq[/tex] og [tex]p | a_1[/tex] og [tex] q | a_2 - 1[/tex]. Da [tex]\gcd(a_2, a_2-1) = 1[/tex] følger det at [tex]q|a_3 - 1[/tex], ... , [tex]q | a_k - 1[/tex]. Så hvis [tex]pq | a_k(a_1 - 1)[/tex] må nødvendigvis [tex]q | a_1 - 1[/tex]. Men siden [tex] p | a_1[/tex] må i så fall [tex] p | a_k[/tex]. Virket igjen fører til at [tex]p | a_{k-1}[/tex] , ... , [tex]p | a_1[/tex].

Så [tex]p|a_1, p|a_2[/tex] og [tex]q|a_1 - 1, q|a_2-1[/tex] og dermed
[tex]p|a_1-a_2[/tex] og [tex]q|a_1-a_2[/tex]. Dette gir at [tex]n|a_1-a_2[/tex] en umulighet da [tex]a_1 \neq a_2[/tex] og [tex]|a_1-a_2| < n[/tex].

edit: rettet en brainfart.

QED.

[Karl_Erik]

Jeg er ikke helt sikker på hvem som er hvem her, men om jeg ikke tar helt feil lyder Sondre også navnet Sonki. Løsningen din er selvfølgelig flott den. Jeg tror vi løste den på så mange som tre forskjellige måter. Måten jeg likte best var å først legge merke til at [tex]a_i \equiv a_i a_{i+1} (mod n)[/tex] for [tex]i=1, 2, ... k-1[/tex], som gir [tex]a_1 \equiv a_1 a_2 \equiv a_1 a_2 a_3 \equiv ... \equiv \prod _{i=1} ^k a_i (mod n)[/tex].

Antar man at konklusjonen ikke stemmer får man også at [tex]a_k \equiv a_1 a_k (mod n)[/tex], som videre gir [tex]a_k \equiv a_1 a_k \equiv a_1 a_2 a_k \equiv ... \equiv \prod _{i=1} ^k a_i \equiv a_1 (mod n)[/tex], dvs [tex]a_1 \equiv a_k (mod n)[/tex], som siden [tex]a_i[/tex] alle er forskjellige tall i [tex] \left { 1, 2, ... n \right } [/tex] er umulig. Altså var antagelsen vår feil, og [tex]n[/tex] deler ikke [tex]a_k (a_1 - 1)[/tex].

[Magnus]

Ja, den var fin. (Produktet skal vel ikke gaa til n, dog).

[Karl_Erik]

Whoops, ja. Rettet på det nå - indeksen skulle selvfølgelig gå til [tex]k[/tex].

[Magnus]

Saann her gaar det naar man velger aa trykke 'siter' fremfor 'endre' ...