En ond professor har bestemt seg for å flytte rundt på studentene sine. Salen er fullsatt og studentene sitter på stoler som er plassert rektangulært med [tex]m\cdot n[/tex] stoler til sammen. For alle studentene gjelder:
1) Studenten skal sitte på en ny stol.
2) Studenten skal sitte på en stol som er til høyre, venstre, ovenfor eller nedenfor den gamle stolen.
Vis at den onde professoren kan gjøre dette hvis [tex]m\cdot n[/tex] er like og ikke hvis [tex]m\cdot n[/tex] er odde.
En ond professor
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Nebuchadnezzar
- Fibonacci
- Innlegg: 5648
- Registrert: 24/05-2009 14:16
- Sted: NTNU
Kan dette forklares så enkelt som at la oss anta at [tex]m\cdotn[/tex] er odde, da er antall stoler delelig på 2. Som fører til at to og to elever kan bytte stoler. Om vi har at [tex]m\cdotn[/tex] er odde kan dette skrives som [tex]2k+1[/tex] og av dette ser vi at det er en elev som ikke kan bytte plass når [tex]nm[/tex] er odde.
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
-
Fibonacci92
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
Hvis m*n er et partall kan vi flytte på følgende måte:
Antar uten tap av generalitet at antall pulter i hver rad er et partall. (Hvis mn er et partall må enten m eller n være et partall)
- Begynner i pulten i det bakerste venstre hjørnet og flytter eleven et hakk oppover. Eleven som opprinnelig satt på plassen ovenfor den første eleven flyttes også et hakk oppover og slik gjentas prosessen til du kommer til eleven på første rad.
-Eleven på første rad flyttes nå et hakk til høyre og så flyttes den eleven som opprinnelig satt på den plassen et hakk nedover. Vi flytter elevene nedover til vi igjen kommer på bakerste rad. Eleven som opprinnelig satt der flyttes en pult til høyre.
-Slik kan prosessen gjentas helt til vi ender opp i nederste høyre hjørne. Den eleven som sitter der flyttes nå til bakerste venstre hjørne, og nå har alle elevene byttet plass i henhold til reglene.
Merk at dette systemet ikke fungerer på en rad med et odde antall pulter fordi vi til slutt ender opp i det fremste høyre hjørnet, og vi kan ikke flytte den eleven til startpulten på lovlig vis.
Antar uten tap av generalitet at antall pulter i hver rad er et partall. (Hvis mn er et partall må enten m eller n være et partall)
- Begynner i pulten i det bakerste venstre hjørnet og flytter eleven et hakk oppover. Eleven som opprinnelig satt på plassen ovenfor den første eleven flyttes også et hakk oppover og slik gjentas prosessen til du kommer til eleven på første rad.
-Eleven på første rad flyttes nå et hakk til høyre og så flyttes den eleven som opprinnelig satt på den plassen et hakk nedover. Vi flytter elevene nedover til vi igjen kommer på bakerste rad. Eleven som opprinnelig satt der flyttes en pult til høyre.
-Slik kan prosessen gjentas helt til vi ender opp i nederste høyre hjørne. Den eleven som sitter der flyttes nå til bakerste venstre hjørne, og nå har alle elevene byttet plass i henhold til reglene.
Merk at dette systemet ikke fungerer på en rad med et odde antall pulter fordi vi til slutt ender opp i det fremste høyre hjørnet, og vi kan ikke flytte den eleven til startpulten på lovlig vis.
Hvis jeg ikke misforstår, vil ikke da den siste eleven flyttes lengre enn han har lov til?Fibonacci92 skrev: -Slik kan prosessen gjentas helt til vi ender opp i nederste høyre hjørne. Den eleven som sitter der flyttes nå til bakerste venstre hjørne, og nå har alle elevene byttet plass i henhold til reglene.
La oss si du skal flytte elevene. Du velger ut en elev. Du følger han til den nye plassen sin, og velger så eleven som opprinnelig satt der. Så følger du denne eleven til plassen sin, og følger nestemann videre, helt til du er tilbake til den opprinnelige plassen (for du må ende opp her til slutt, èn av dem må sitte her). Siden du kun kan bevege deg vertikalt og horisontalt, er det opplagt at antall turer "ned" og turer "opp" er like, og på samme måte antall turer til "venstre", og turer til "høyre" er like. Altså summerer antall elever du har fulgt til nå til et partall.
Nå velger du en elev som ikke var med i mengden elever du fulgte til sin plass i stad (hvis det er flere igjen). På samme måte flytter du et partall elever denne ganger også.
Du fortsetter å gjøre dette til det ikke er flere elever igjen. Summen av elever du har fulgt er dermed en sum av partall, så m*n må være et partall.
Dersom nå m*n er et partall, kan vi anta at antall kolonner er et partall. Begynn nederst til venstre. Gå oppover til toppen, gå èn til høyre, og deretter ned til nest siste plass. Gå èn til høyre, og opp til toppen. Ta nok en høyresving, og fortsett dette til du har rukket øverst til høyre. Gå nå helt ned, og rett til venstre tilbake til første pult. Ved å la elevene flytte seg i denne banen, er vi ferdige.
(Fibonacci: det var kanskje dette du mente?)
De kan altså flyttes hvis og bare hvis m*n er et partall.
Nå velger du en elev som ikke var med i mengden elever du fulgte til sin plass i stad (hvis det er flere igjen). På samme måte flytter du et partall elever denne ganger også.
Du fortsetter å gjøre dette til det ikke er flere elever igjen. Summen av elever du har fulgt er dermed en sum av partall, så m*n må være et partall.
Dersom nå m*n er et partall, kan vi anta at antall kolonner er et partall. Begynn nederst til venstre. Gå oppover til toppen, gå èn til høyre, og deretter ned til nest siste plass. Gå èn til høyre, og opp til toppen. Ta nok en høyresving, og fortsett dette til du har rukket øverst til høyre. Gå nå helt ned, og rett til venstre tilbake til første pult. Ved å la elevene flytte seg i denne banen, er vi ferdige.
(Fibonacci: det var kanskje dette du mente?)
De kan altså flyttes hvis og bare hvis m*n er et partall.
Fin losning! Jeg kom frem til det samme. men har et tilleggssporsmaal: hvordan kan jeg vaere sikker paa at argumentene er (av mangel paa bedre ord) «logisk atomaere»? Det er forholdsvis enkelt aa foelge argumenter i aritmetikken, da pene implikasjonspiler viser veldig tydelig hva som foelger av antagelsene osv., men naar argumentene formuleres med ord (som er like presist?) finner jeg det vanskelig(ere) aa se om paastander/argumentasjonen kan deles videre opp i mindre biter (som maa bevises og dermed muligens vaere gale).
-
Fibonacci92
- Abel
- Innlegg: 665
- Registrert: 27/01-2007 22:55
Ahh.. jeg tolket det som om vi kunne flytte en elev så langt vertikalt eller horisontalt en bare vil, og ikke at eleven måtte sitte på en plass rett ved siden av. (Oppgaven blir kanskje mye enklere da?)
Jeg skjønner ikke helt hva du mener egentlig, kan du forklare litt nærmere?Emomilol skrev:Fin losning! Jeg kom frem til det samme. men har et tilleggssporsmaal: hvordan kan jeg vaere sikker paa at argumentene er (av mangel paa bedre ord) «logisk atomaere»? Det er forholdsvis enkelt aa foelge argumenter i aritmetikken, da pene implikasjonspiler viser veldig tydelig hva som foelger av antagelsene osv., men naar argumentene formuleres med ord (som er like presist?) finner jeg det vanskelig(ere) aa se om paastander/argumentasjonen kan deles videre opp i mindre biter (som maa bevises og dermed muligens vaere gale).
EDIT: Mener du at om argumentet kan gjøres mer rigorøst som om det var en algebraisk utregning?
Hvis man gjør det på denne måten kan man uansett hva m og n er ta utgangspunkt i hver kolonne og flytte hver elev èn plass opp, og den øverste helt ned.Fibonacci92 skrev:Ahh.. jeg tolket det som om vi kunne flytte en elev så langt vertikalt eller horisontalt en bare vil, og ikke at eleven måtte sitte på en plass rett ved siden av. (Oppgaven blir kanskje mye enklere da?)
Hvordan vet man at argumentet holder vann (og ikke bare er overbevisende) naar det ikke er saa tydelig hva som logisk foelger av hva?Charlatan skrev:Jeg skjønner ikke helt hva du mener egentlig, kan du forklare litt nærmere?
EDIT: Mener du at om argumentet kan gjøres mer rigorøst som om det var en algebraisk utregning?
En annen løsning (for nm odde):
Bruk et sjakkbrekk som analogi. Gitt at [tex]nm[/tex] er odde, kan vi wlog si at antallet svarte ruter er en mer enn antallet hvite ruter. Hvis en elev kun kan flyttes opp, ned, til høyre eller tjl venstre, må enhver elev på en svart rute flyttes til en hvit rute og vice versa. Men det er flere svarte ruter enn hvite ruter og dette er derfor umulig.
Bruk et sjakkbrekk som analogi. Gitt at [tex]nm[/tex] er odde, kan vi wlog si at antallet svarte ruter er en mer enn antallet hvite ruter. Hvis en elev kun kan flyttes opp, ned, til høyre eller tjl venstre, må enhver elev på en svart rute flyttes til en hvit rute og vice versa. Men det er flere svarte ruter enn hvite ruter og dette er derfor umulig.
Èg er Islendingur 