Feladat: B.3677 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Ablonczy Dávid ,  Birkner Tamás ,  Birkus Róbert ,  Bitai Tamás ,  Czank Tamás ,  Erdélyi Márton ,  Fehér Gábor ,  Filus Tamás ,  Gehér György ,  Gyenizse Gergő ,  Hegyháti Máté ,  Hujter Bálint ,  Koszta Botond ,  Kunovszki Péter ,  Kutas Péter ,  Nagy Csaba ,  Nagy-Baló András ,  Pálinkás Csaba ,  Stippinger Macrell ,  Strenner Balázs ,  Szabó Botond ,  Szabó Tamás ,  Szalkai Balázs ,  Szalóki Dávid ,  Szilágyi Dániel ,  Sziróczák Richárd ,  Ureczky Bálint ,  Vadász Gergely ,  Vass Márton 
Füzet: 2004/március, 160 - 161. oldal  PDF  |  MathML 
Témakör(ök): Számhalmazok, Részhalmazok, Feladat
Hivatkozás(ok):Feladatok: 2003/november: B.3677

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Az egyszerűség kedvéért a továbbiakban azt a számhalmazt, amely egy H számhalmaz elemeinek a k-szorosából áll, kH-val jelöljük. A feladat feltétele így αA=βB, miközben az 1βαA=B és az 1αβB=A halmazok a pozitív egészek közös elem nélküli előállítását adják. Megmutatjuk, hogy a megfelelő számpárok olyanok, hogy egyikük a másik valódi osztója, továbbá ezek mind megfelelőek.
Először azt látjuk be, hogy a nem ilyen tulajdonságú számpárokra nem valósítható meg a pozitív egészek megfelelő szétválasztása. Elsőként legyen α=β. Ilyenkor nyilván nem valósítható meg a kívánt szétosztás, hiszen ekkor az αA=βB egyenlőségből az A és B halmazok egyenlősége következik. A szimmetria miatt ezután föltehető, hogy α<β, és persze, ha (α;β) jó számpár, akkor (β;α) is az.
Nyilvánvaló, hogy ha k tetszőleges pozitív egész és (α;β) jó számpár, akkor (kα;kβ) is az, hiszen a megadott halmazok csak k-val szorzódnak. Ennek a tulajdonságnak a megfordítása is igaz: ha k a jó (α;β) közös osztója, akkor az (αk;βk) számpár is jó. Ezek szerint elegendő megtalálni a relatív prím jó számpárokat.
Legyen tehát (α;β)=1, és tegyük fel, hogy 1∈A. Ekkor α⋅1=α∈αA. Mivel ennek a halmaznak minden eleme βb alakban is előáll, azért 1∉B miatt α legalább 2β. Ez viszont nem lehetséges, hiszen föltevésünk szerint α<β. Így csak 1∈B lehetséges. Ekkor β⋅1=β∈βB=αA, azaz β az α többszöröse. Mivel feltettük, hogy relatív prímek, ez csak úgy lehetséges, ha α=1. Ezzel tehát beláttuk, hogy a relatív prím α<β megoldásokra α=1, β>1 szükséges.
Most megmutatjuk, hogy ez elégséges is, minden ilyen számpárhoz létezik megfelelő felosztás. Egyszerűen megadjuk a kívánt tulajdonságú halmazokat. Legyenek A elemei az m⋅β2k+1 alakú számok, ahol k tetszőleges nemnegatív egész, és m olyan egész szám, amit β már nem oszt. Az m⋅β2k alakú számok pedig legyenek B elemei. A számelmélet alaptétele szerint így minden pozitív egész a két halmaz közül pontosan az egyikbe került, továbbá a B halmaz elemeit β-val szorozva valóban az A-beli elemeket kapjuk és megfordítva. (Továbbra is α=1.)
A jó relatív prím számpárok tehát valóban olyanok, hogy (α;β) egyike 1, másika 1-nél nagyobb tetszőleges egész. Az összes megfelelő számpár pedig az ilyenek pozitív egész többszörösei, tehát azok, ahol a számpár egyik tagja valódi osztója a másiknak.
 
II. megoldás. α=β-t az előző megoldás szerint kizárhatjuk. Legyen αβ először 1-nél nagyobb egész szám; megmutatjuk, hogy ilyenkor van megfelelő szétosztás. A következő algoritmus szerint haladjunk sorra a pozitív egész számokon: ha a soron következő k számot még nem helyeztük el, akkor tegyük az A-ba, az αβ-szorosát pedig a B-be. Ez azt jelenti, hogy első lépésben az 1, ami természetesen még nem került helyre, az A-ba kerül, αβ>1 pedig B-be. Az eljárás egyértelmű, és minden pozitív szám bekerül a két halmaz egyikébe. Mivel ezzel B=αβA, nyilván teljesül a feladatban előírt αA=βB egyenlőség. (Érdemes meggondolni, milyen algebrai tulajdonságai vannak a halmaz számmal való szorzása műveletnek.) Hasonlóan adódik a felosztás, ha βα 1-nél nagyobb egész.
Még azt kell megmutatnunk, hogy ha sem αβ, sem βα nem egész, akkor nincsen megfelelő szétosztás. Legyen p olyan prím, amely sem α-nak, sem pedig β-nak nem osztója. Ha lenne megfelelő szétosztás, akkor p-nek is ott kellene lennie az egyik halmazban, például A-ban. Ekkor α⋅p∈αA=βB, tehát αpβ∈B. Ez viszont nem lehetséges, hiszen feltevésünk szerint β és αp relatív prímek, tehát ez a tört nem egész szám. Hasonlóan kapjuk, hogy p a B halmazban sem lehet.