matematikk.net

31 røvere skal dele et bytte som består av gullmynter, ikke flere enn 20 000 i alt. Men når de prøver å dele byttet likt, blir det 30 gullmynter til overs. Lederen for røverne antar der går opp hvis de bare var 30 røvere, så han kapper hodet av en av røverne. Men fremdeles blir det 29 mynter til overs. Lederen er ikke bedre enn at han prøver samme metode igjen, og nok et hode ruller. Denne gangen lar byttet seg dele likt på de 29 gjenværende skurkene. Hvor mange gullmynter består byttet av?

La x være antall mynter.

Må ha

[tex]x=31s+30=30t+29=29u[/tex] for positive heltall [tex]s,t,u[/tex].

Derfor må [tex]31s+1=30s+s+1=30t[/tex] eller likeledes [tex]30(t-s)=s+1[/tex].

[tex]30[/tex] må derfor dele [tex]s+1[/tex], så [tex]s=30v-1[/tex]. Innsatt får man

[tex]x=31(30v-1)+30=30*31v-1=29*32v+2v-1[/tex]

Siden [tex]29[/tex] deler [tex]x[/tex] må [tex]2v-1=29w[/tex]. Det minste antall mynter som oppfyller alle krav får man dersom [tex]v=15[/tex], så

[tex]x=29*32*15+29=13949[/tex]

Stemmer bra dette...

Jeg satt opp kongruenslikningssystemet, og brukte chinese remainder theorem:

[tex]x \equiv 30\pmod{31}[/tex]
[tex]x \equiv 29\pmod{30}[/tex]
[tex]x \equiv 0\pmod{29}[/tex]

ser forresten ut som om vi løser det likt etterhvert...

Janhaa skrev:Stemmer bra dette...

Jeg satt opp kongruenslikningssystemet, og brukte chinese remainder theorem:

[tex]x \equiv 30\pmod{31}[/tex]
[tex]x \equiv 29\pmod{30}[/tex]
[tex]x \equiv 0\pmod{29}[/tex]

ser forresten ut som om vi løser det likt etterhvert...

Tenkte først på det samme. Går vel an å løse det ganske "algoritmisk" ved bruk av nevnte metode (slik som i denne artikkelen: http://en.wikipedia.org/wiki/Chinese_remainder_theorem).