Jó feladat. Az a helyzet, hogy nincs mindig megoldása. Ugyanis amit valójában elvársz, az a következő: azt várod el, hogy az első maradékos osztás adjon nulla maradékot, vagy a második maradékos osztás adjon nemnulla maradékot. (Ezeket a maradékos osztásokat mindjárt leírom formálisan is.) És van olyan n és c, hogy egyik elvárás sem teljesül.
Tehát formálisan (az alábbiakban n, c, q, q2, r és r2 mind egész számok):
- Első körben azt a maradékos osztást nézed, hogy n = q * c + r, ahol adott n>0 a tételek száma, adott c>0 a teljes oszlopok száma, keresett q>=0 a hányados (sorok száma a teljes oszlopokban), és keresett c>r>=0 a maradék (az utolsó, nem teljes oszlopban lévő sorok száma -- maradék lévén ez kisebb, mint az osztó; ha már annyi sor szerepelne az utolsó, nem teljes oszlopban, mint ahány teljes oszlop van, akkor a hányados nőne meg, vagyis eggyel több sor lenne a teljes oszlopokban).
Első körben azt várod el, hogy r=0 legyen; ekkor kapsz egy szép mátrixot, pontosan c oszloppal, és q sorral. (És ekkor rögtön adódik az is, hogy q pozitív, hiszen n = q * c.)
Ha viszont r>0 adódik, akkor van egy nem teljes utolsó oszlopod is, amivel megszegted az "oszlopszám=c" elvárást, tehát át kell térnünk eggyel kisebb oszlopszámra ((c-1)-re). Itt rögtön látjuk azt is, hogy ebben az esetben c>=2 (tehát (c-1) még mindig pozitív lesz); ugyanis ha az eredeti osztó c=1 volt (összesen 1 oszlopot kértünk), akkor q=n (n sorunk lesz) és r=0 (nincs maradék -- nincs nem teljes oszlop) -- vagyis c=1 esetén nem jutottunk volna ide (ahol r>0).
- Második körben azt a maradékos osztást nézzük, hogy n = q2 * (c-1) + r2, ahol adott n>0 továbbra is a tételek száma, adott (c-1)>0 az oszlopok (eggyel csökkentett, de a fentiek szerint még mindig pozitív) száma, keresett q2>=0 hányados (a sorok száma a teljes oszlopokban), és keresett (c-1)>r2>=0 maradék (az utolsó, nem teljes oszlopban lévő sorok száma).
Pontosabban (és ezen bukik a dolog): itt azt várjuk el, hogy r2>0 legyen. Ugyanis ha r2=0, akkor nincs betöltetlen oszlop, és kapunk egy szép mátrixot (c-1) oszloppal és q2 sorral -- ami viszont ismét megszegi az eredeti "oszlopszám=c" elvárást.
Vagyis a sejtésed az (más szóval: a specifikáció feltételezése az), hogy:
∀ n, c ∈ ℕ⁺: (∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)
Mivel ez egy olyan elsőrendű logikai állítás, amely univerzális kvantorral kezdődik, azért a cáfolatához elég egy ellenpéldát találni. Formálisan, a sejtés negáltja úgy néz ki, hogy először az egész elé kiragasztunk egy tagadást:
¬∀ n, c ∈ ℕ⁺: (∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)
Aztán a logikai "nem" operátort bevisszük az univerzális kvantoron belülre (amitől az egzisztenciális kvantorrá változik, a kvantált predikátum pedig negálódik):
∃ n, c ∈ ℕ⁺: ¬((∃ q ∈ ℕ⁺: n = q * c) ∨ (∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂))
Azután a De Morgan azonossággal a negálást szétosztjuk a logikai "vagy"-on (amitől a "vagy" "és"-sé változik, az operandusai pedig negálódnak):
∃ n, c ∈ ℕ⁺: ¬(∃ q ∈ ℕ⁺: n = q * c) ∧ ¬(∃ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n = q₂ * (c-1) + r₂)
Ismét a kvantoros játék:
∃ n, c ∈ ℕ⁺: (∀ q ∈ ℕ⁺: n ≠ q * c) ∧ (∀ q₂ ∈ ℕ, (c - 1) > r₂ ∈ ℕ⁺: n ≠ q₂ * (c-1) + r₂)
Ha ezt az állítást sikerül kielégíteni, akkor a sejtést megcáfoltuk.
Az általad adott n=18, c=7 számpár "létezik", és kielégíti a sejtés negáltját; vagyis cáfolja a sejtést:
(∀ q ∈ ℕ⁺: 18 ≠ q * 7) ∧ (∀ q₂ ∈ ℕ, 6 > r₂ ∈ ℕ⁺: 18 ≠ q₂ * 6 + r₂)
Ennek a konjunkciónak mindkét operandusa igaz, ugyanis:
- a 18 nem osztható 7-tel (bármely pozitív egésszel szorozzuk a 7-et, nem lesz a szorzat 18), valamint
- a 18-at 6-tal osztva 0 a maradék, ami pedig nem eleme az ℕ⁺ halmaznak (ha q₂ értéke 0, 1 vagy 2, akkor r₂ értéke rendre 18, 12, 6, amelyek egyike sem elégíti ki a 6>r₂ követelményt; ha q₂ értéke 3, akkor r₂=0, ami nem eleme az ℕ⁺ halmaznak; ha pedig q₂>3, akkor r₂ negatív, így nem eleme az ℕ⁺ halmaznak).
Összefoglalva: pontosan c oszloppal nem mindig megoldható a feladat; lehet, hogy (c-1) oszlopú mátrixot fogsz kapni. És ez az eset akkor áll fenn, ha c nem osztója n-nek, (c-1) viszont osztója n-nek.