A programozó munkája a legkönnyebb /2

Legyen egymasra meroleges 7 piros vonal! De zold es atlatszo tintaval!

Nézd meg hogy az `ls -v` mit csinál. Nekem úgy tűnik hogy az is a kevesebb oszlopra szavaz.

Az alternatív specifikáció ötleted nekem nem tetszik, nem tűnik tipikus, jól ismert viselkedésnek.

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):

1. 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).
    

2. 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.

Ha emberi sorrendben írod ki (balról jobbra), akkor látszik, hogy miért nincs megoldás, mert több hasáb lesz hiányos: 

 1  2  3  4  5  6  7

 8  9 10 11 12 13 14

15 16 17