Normat 51:2, 83–85 (2003) 83
Oppgaver
Oppgavene 431–432 er hentet fra canadiske matematikkolympiader, og 433–434 fra
Putnam-konkurransen.
431. Gitt 7 distinkte reelle tall. Vis at det blant disse fins minst ett par x, y slik at
0
x y
1+xy
1
3
.
432. Vis at et reelt tall x er rasjonalt hvis og bare hvis vi i følgen
x, x +1,x+2,x+3,...
kan finne tre distinkte ledd som danner en geometrisk progresjon.
433. For hvilke reelle tall x konvergerer rekken
n=1
1
n sin(1/n)
x
?
434. La p være et odde primtall. Bevis at
p
j=0
p
j
p + j
j
2
p
+ 1 (mod p
2
).
Løsninger
406. La n 2 være et positivt heltall. Til å begynne med er det n lopper på en
horisontal linje, der ikke alle er i samme punkt. For et positivt reelt tall definerer
vi et trekk på følgende måte:
Velg to lopper, den ene i punktet A og den andre i B, der A ligger til
venstre for B.
La loppen i A hoppe til punktet C på samme linje, men til høyre for B,
slik at BC/AB = .
Bestem alle verdier for slik at det for hvert punkt M på linjen og hver utgangs-
posisjon for de n loppene, finnes en endelig følge av trekk som vil flytte alle loppene
til punkter til høyre for M. (Fra den internasjonale matematikkolympiaden i Taejon,
2000.)
Løsning: Vi følger den offisielle løsningen. For enkelhets skyld antar vi at loppene
befinner seg på den reelle tallinjen, og vi angir på naturlig måte posisjonen til
hver av loppene med det tilsvarende tallet. Det er nærliggende å tro at en gunstig
strategi for å komme langt til høyre er at vi i hvert trekk lar loppen lengst til venstre
hoppe over loppen lengst til høyre. Etter k trekk har vi da fått en konfigurasjon
oppgaver.tex,v 1.4
84 Oppgaver Normat 2/2003
hvor to parametere er av interesse: Vi lar d
k
betegne den største avstanden mellom
to lopper (altså diameteren av loppe/punkt-mengden), mens
k
er minste avstand
mellom to nabolopper. Det er klart at d
k
(n 1)
k
,ogfork n 1 har vi også
helt sikkert
k
> 0.
Etter trekk nummer k+1 har vi fått en ny avstand mellom to nabolopper, nemlig
d
k
. Hvis dette er den nye minsteavstanden, er
k+1
= d
k
, og hvis ikke, er i hvert
fall
k+1
k
. I alle tilfeller har vi
k+1
k
min
1,
d
k
k
min{1,(n 1)}.
Hvis 1/(n 1), er
k+1
k
for alle k, det vil si at minsteavstanden ikke avtar.
Det betyr igjen at posisjonen til den loppen som til enhver tid er lengst til venstre,
endres i skritt som alle er større enn en passende positiv konstant. Dermed kan vi
få alle loppene så langt til høyre som vi måtte ønske.
Hva nå om <1/(n 1)? Vi påstår at da fins det en startkonfigu rasjon som er
slik at vi ikke kan få loppene forbi et visst punkt M . Faktisk er det slik for enhver
startkonfigurasjon.
Betrakt en vilkårlig følge av trekk. La s
k
være summen av alle tallene som re-
presenterer posisjonene etter det k-te trekket, og la w
k
være det største av disse
tallene (altså posisjonen til loppen lengst til høyre). Legg merke til at s
k
nw
k
. Vi
skal vise at følgen (w
k
) er begrenset.
I trekk nummer k +1hopper en loppe fra a over b og lander på c. Da er s
k+1
=
s
k
+ c a. Ifølge spillereglene er c b = (b a), som er ekvivalent med (c a)=
(1 + )(c b). Derfor er
s
k+1
s
k
= c a =
1+
(c b).
Anta at c>w
k
, altså at den loppen som nettopp hoppet, nå er lengst til høyre, slik
at w
k+1
= c. Siden b var posisjonen til en eller annen loppe etter det k-te trekket,
er b w
k
, og
(1) s
k+1
s
k
=
1+
(c b)
1+
(w
k+1
w
k
).
Denne ulikheten holder også hvis c w
k
, for da er w
k+1
w
k
=0og s
k+1
s
k
=
c a>0.
Betrakt nå følgen
z
k
=
1+
w
k
s
k
for k =0, 1, 2,....
Ulikheten (1) viser at z
k+1
z
k
0, så z
k
z
0
for alle k.
Vi har antatt at <1/(n 1).Daer1+ > n, og vi kan skrive
z
k
=(n + µ)w
k
s
k
, hvor µ =
1+
n>0.
Dette gir oss ulikheten z
k
= µw
k
+(nw
k
s
k
) µw
k
. Det følger at w
k
z
0
/µ for
alle k.
Løst av: Jørgen Hilden, København, DK; Peter Kirkegaard, Gentofte, DK.
oppgaver.tex,v 1.4
Normat 2/2003 Oppgaver 85
408. (Innsendt av Hans Georg Killingbergtrø, Leksvik, NO.) I hver av ti fløyels-
poser ligger 55 tilsynelatende helt like mynter. Åtte av posene inneholder 13-grams
ekte sølvmynter, i én pose er myntene av bly overtrukket med sølv og veier 14 gram,
og i én pose har de en liten kjerne av aluminium innstøpt i sølv og veier 12 gram.
Kan en ved å plukke utsøkte antall mynter fra posene og avlese deres samlede
vekt i én veiing finne posen me d for tunge og posen med for lette mynter?
Løsning (etter Peter Kirkegaard, Gentofte, DK): La vekten av en ekte sølvmynt
være P . De lette myntene veier da P 1 og de tunge P +1. Antall poser kalles L,
og antall mynter per pose M. I oppgaven er da
(1) P = 13,L= 10,M= 55.
Vi tar ut a
i
mynter fra pose i (0 a
i
M, 1 i L), og ved samlet veiing av
disse myntene konstaterer vi vekten V , altså
(2)
L
i=1
a
i
b
i
= V,
der b
i
er vekten av en mynt fra pose i. Vi vet at det fins indekser j og k (j = k)
slik at
b
j
= P 1,b
k
= P +1,b
i
= P for i = j, k .
Vi skal nå forsøke å bestemme j og k fra ligningen (2), som vi omskriver til
L
i=j, k
a
i
P + a
j
(P 1) + a
k
(P + 1) = V,
altså
(3) a
k
a
j
= V
L
i=1
a
i
P.
Oppgaven går ut på å velge a
1
,...,a
L
slik at (3) bestemmer j og k entydig. Det
er klart at den spesielle verdien P = 13 er likegyldig – det eneste det dreier seg om
er å sikre at diffensavbildningen (j, k) a
k
a
j
blir injektiv. Da vil nemlig ligning
(3), med j og k som de eneste ukjente, ha høyst 1 løsning. En faktisk veiing gir
selvsagt en løsning (j, k).
Med verdiene (1) gjelder det at det kan dannes 110 differenser =0av tallene
0–55, og siden vi har bruk for 90 forskjellige differenser, skulle det være «plass»
nok. Det viser seg at det ikke er lett å konstruere (a
i
) for hånd, men et søk med
PC viser at det, bortsett fra permutasjoner, fins bare to løsninger:
(a
i
) = (0, 1, 6, 10, 23, 26, 34, 41, 53, 55),(4)
(a
i
) = (0, 2, 14, 21, 29, 32, 41, 49, 54, 55),(5)
der (5) fås av (4) ved speil-substitusjonen a
i
:= M a
Li+1
. Programmet viste
også at for L = 10 er M = 55 den minste verdien som gir løsninger, idet det ikke
fins løsninger for M = 54.
Løsningsforslag sendes Arne Strøm, Økonomisk institutt, Universitetet i Oslo, Postboks
1095 Blindern, NO–0317 Oslo, Norge innen 29. februar 2004. Forslag til nye oppgaver
er velkomne når som helst. Vennligst oppgi kilde til oppgaver som ikke er egenproduserte.
oppgaver.tex,v 1.4
