Så var runde 2 av Abel-konkurransen over...

[sEirik]

Vanskelige oppgaver... jeg fikk bare til 2 av dem. Men da slipper jeg å tenke på å reise til finaler og styr og stell

Det var en oppgave der som var litt interessant.

31 røvere hadde funnet en gullskatt på ikke mer enn 20 000 mynter, og skulle fordele den likt mellom seg. Når de fordelte myntene, kom de frem til at de fikk 30 mynter til overs. Røverlederen tenkte at dette problemet kunne løses enkelt, så han hogg hodet av den ene røveren, slik at det bare var 30 røvere igjen. Nå var det imidlertid 29 mynter til overs etter fordelingen. Røverlederen kappet hodet av en røver til, slik at de nå bare var 29 røvere, og da kunne man fordele myntene likt på alle sammen.

Jeg kan tenke meg at dette kan løses på et eller annet vis med kongruensregning;

[tex]g \equiv 30\ {\rm mod}\ 31[/tex]
[tex]g \equiv 29\ {\rm mod}\ 30[/tex]
[tex]g \equiv 0\ {\rm mod}\ 29[/tex]

Går det an å løse oppgaven med et slikt likningssett kanskje?

[ingentingg]

Det går an vet du.
Kjenner du til kinesisk rest teorem?. Det kan du bruke til å løse likninger på formen:

[tex]g\equiv a_1 mod \ b_1\\g\equiv a_2 mod \ b_2 \\ g\equiv a_3 mod \ b_3[/tex]

Hvis [tex]b_1, b_2 \ og \ b_3[/tex] er har 1 som største felles divisor.

I dette tilfelle er jo 31 og 29 primtall og 30 = 3*10 så da er jo det greit.

[Magnus]

Hehe. Ja, får se det positive i det.

Jepp. Et slikt likningssett er ganske greit å løse, enten kan du bruke kinesiske restklasseteorem (da alle er relativt primiske) eller gjøre som dette:

[tex]g \equiv 0 \pmod{29} \Longrightarrow g = 29k\ k\in\mathbb Z[/tex]

[tex]29k \equiv 29 \pmod{30} \Longrightarrow k \equiv 1 \pmod{30}[/tex]

Hvilket gir: [tex]k = 1 + 30Q[/tex]

[tex]g = 29(1+30Q)[/tex]

[tex]29(1+30Q) \equiv 30 \equiv -1 \pmod {31}[/tex]

[tex]29 - 29Q \equiv -1 \pmod {31}[/tex]

[tex]-2 + 2Q \equiv -1 \pmod{31}[/tex]

[tex]2Q = 1(mod 31)[/tex]

[tex]2Q - 31x = 1[/tex]

Diofantisk likning:

[tex]31 = 2*15 + 1[/tex]

[tex]1 = 31-2*15 \[/tex]

Q = -15 + 31t [tex]\forall t\in\mathbb Z[/tex]

Ser at Q på må være positiv.

Q = -15 +31 = 16

Følgelig blir g = 29(1+30Q) = 13949.

Dette er én måte å gjøre den på. De løser den helt sikkert ved ulikhet.