Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Közepiskolai matek!

522
Leírjuk az első néhány pozitív egész számot növekvő sorrendben.
A célunk az, hogy rendezzük át a számokat csökkenő sorrendbe. Egy lépésben
kicserélhetünk két olyan számot, melyek relatív prímek.
a) Minimálisan hány lépésre van szükség, ha az 1; 2; 3; 4; …; 100 számokat
írtuk le? Adjunk is meg egy minimális lépésszámú átrendezést!
b) Rendezzük át a számokat legfeljebb 12 lépésben, ha az 1; 2; 3; 4; …; 14
számokat írtuk le!
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Középiskola / Matematika

Válaszok

1
a) A feladat azt kéri, hogy a lehető legkevesebb lépéssel végezzük el. A legkevesebb lépéssel akkor tudjuk megcsinálni, hogyha mindenkit rögtön a helyére rakunk, ehhez az 1-et a 100-zal, a 2-t a 99-cel, ..., az 50-et az 51-gyel kell kicserélni, ehhez összesen 50 lépést teszünk, ez a legkevesebb.
A feladat megoldásához érdemes tudni azt a félig-meddig triviális megállapítást, hogy ha van két számunk, melyeknek van közös osztójuk, akkor a számok összege és különbsége is osztható lesz ezzel a számmal; például a 65 és a 91 számok különbsége 91-65=26, összegük 91+65=156, és mindegyik szám osztható 13-mal.
A számok összege minden esetben 101 (1+100=2+99=...=50+51, és ez azért van így, mert ha az egyik tagot növeljük 1-gyel, a másikat csökkentjük, akkor magát az összeget pont 0-val növeltük). A fenti megállapítás szerint az összeg tagjainak ugyanaz az osztója, mint a 101-nek. A 101-nek, mivel prímszám, két osztója van; az 1 és a 101. Értelemszerűen a 101 nem lehet 101-nél kisebb pozitív számoknak osztója, így marad az 1, tehát a cserélendő számok mind relatív pramek egymáshoz.
Tehát 50 lépésben megoldható úgy, hogy a számokat szimmetrikusan kicseréljük egymással.

b) A fenti metódus a legtöbb szám között működni fog. Ha megtesszük, ezt a számsort kapjuk:
14 13 3 11 5 6 8 7 9 10 4 12 2 1, ehhez 4 lépést tettünk meg.
Akikkel nem szeretnénk a továbbiakban foglalkozni, azokat töröljük le, hogy ne zavarjanak:
3 5 6 9 10 12, őket kellene csökkenő sorrendbe tenni legfeljebb 8 lépésben. Ez már talán nem fog kihívást okozni
0