On annettu nxm-ruudukko yksikköneliöitä ja sivellin, jonka leveys on 1. Siveltimellä vedetään suora viiva ruudukon lävistäjää pitkin siten, että viiva on mahdollisimman paksu ja siveltimen keskipiste on aina lävistäjällä (eli siis sivellin on aina kohtisuorassa lävistäjää vasten). Kuinka monessa ruudussa on maalia siveltimen vedon jälkeen?
Sivellinprobleema
maalarimiespohtija
19126
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 19
Vanhimmat
Nyt menee vähän arvaamallla ja ilman pidempää pohtimista. Olettaen m > n, suhde m/n on ratkaiseva. Rajoittuen tapauksiin 2 < n < m < 2n veikkaisin 4n-2 ruudussa tai jotain sinne päin.
Lausekkeen on pakko riippua sekä m:stä että n:stä.
ämmistä ei ole muuta kuin harmia, tässä se taas nähtiin...
>Lausekkeen on pakko riippua sekä m:stä että n:stä.
Nimenomaan, kuten yllä on esitetty. Suhde m/n on ratkaiseva. Saattaa olla että rajoitteessa 2 < n < m < 2n tuo kerroin 2 ei ole ihan tarkka. Kun m/n kasvaa sen yli, vastaus 4n-2 muuttuu, seuraavaksi ehkä 6n-4 :ksi.
Otetaan kaksi tapausta: molemmissa n=100, toisessa m=101, toisessa m=199. Väitätkö että vastaus riippuu vain n:stä ja on sama molemmissa? Vaikka lävistäjän pituus on ekassa 142 ja tokassa 222.
Ylläoleva kirjoitus lienee provo, tai sitten kaverilla ei ole ymmärrystä matematiikan käsitteistä. Väite on jotain muuta kuin arvaamallla ja ilman pidempää pohtimista esitetty tulos.
Tämä ongelma ei alunperin kiinnostanut minua, mutta kai se jossain alitajunnassa on pyörinyt. Taidankin pohtia sitä hieman lisää.
Heti alkuun on myönnettävä, että tuo 4n-2 pitää paikkansa vain erityistapauksissa. Tuli näet eräs ajatusvirhe alkuun, se m/n suhde ei päde yleisesti.
Uskallan kuitenkin väittää, että on olemassa ruudukot kooltaan (n,m), (n,m 1) ja (n,m 2) joilla se pätee. Eli rivien lisääminen ei kasvata maalillisten yksikköneliöiden määrää.
Ounastelen lisäksi, että joissain tapauksissa rivin lisääminen jopa vähentää niitä. Vaikka siis lävistäjän pituus tällöin kasvaa.
Joo, en tuohon analyyttistä ratkaisua osaa kehittää. Mahtaako ketjun aloittajalla olla? Laskennallisesti ongelmaa voi tutkia. Onko aloittajalla jokin tietty ruudukon koko mielessä?
Aika hakusessa sulla, ei mulla!
"Mahtaako ketjun aloittajalla olla? Laskennallisesti ongelmaa voi tutkia."
En ole varma, mutta seuraava voisi toimia. Sijoitetaan ruudukko koordinaatistoon, jonka kärkipisteet ovat (0,0), (n,0), (0,m) ja (n,m). Sitten lasketaan lävistäjälle yhtälö ja myös tuolle ykkösen levyiselle kaistaleelle suoran yhtälöt, joka on yhdensuuntainen lävistäjän kanssa. Sitten summataan jokaiselta pystysuoralta ruuturiviltä, montako ruutua on tyhjänä yläosassa ja montako alaosassa, olkoon kokonaissumma S_yla S_ala. Lopputulos on mn-S_ala-S_yla. Taitaa lausekkeessa esiintyä max ja min, kun summauksessa voi tulla ruudukon reunat vastaan.
Tapauksessa m=n (neliöruudukko) nähdään hyvin simppelisti että ratkaisu on 3*n-2. Joten ei tuo 4*n-2 pidä paikkansa.
Näin on.
Kaava riippuu suhteesta m/n.
Silloin kun suhde m/n on kokonaisluku, kaava on helppo keksiä:
m/n = 1 => 3n - 2
m/n = 2 => 4n - 2
m/n = 3 => 7n - 4
m/n = 4 => 10n - 6
m/n = 5 => 11n - 6
m/n = 6 => 14n - 8
j.n.e.
Myös silloin kun suhde m/n on puolikkaan kerrannainen, kaava on helpohko. Tässä tapauksessa n:n on oltava parillinen, koska muutoin m ei olisi kokonaisluku.
m/n = 1.5 => 4n - 2
m/n = 2.5 => 6n - 4
m/n = 3.5 => 8n - 4
m/n = 4.5 => 10n - 6
m/n = 5.5 => 12n - 6
m/n = 6.5 => 14n - 8
....
Seuraavassa n:n on oltava kolmella jaollinen
m/n = 4/3 => 4n - 2
m/n = 5/3 => 13n/3 - 2
m/n = 7/3 => 17n/3 - 4
Seuraavassa hieman toisenlainen tarkastelu. Tutkitaan maalia saavien ruutujen määrää n*m ruudokossa pitäen n kiinteänä muutamilla perättäisillä m:n arvoilla.
Olkoon n vaikkapa 17 ja juoksutetaan m välillä 20..30
(n,m) => lukumäärä
(17, 20) => 62
(17, 21) => 63
(17, 22) => 64
(17, 23) => 67
(17, 24) => 68
(17, 25) => 71
(17, 26) => 72
(17, 27) => 73
(17, 28) => 76
(17, 29) => 77
(17, 30) => 78
Hmm... nouseva lukujono jossa muutama merkillinen hyppy. Katsotaanpa n:n arvolla 12
(12, 12) => 34
(12, 13) => 40
(12, 14) => 42
(12, 15) => 46
(12, 16) => 46
(12, 17) => 48
(12, 18) => 46
(12, 19) => 52
(12, 20) => 50
(12, 21) => 56
(12, 22) => 56
(12, 23) => 56
(12, 24) => 68
(12, 25) => 60
Mielenkiintoista todeta että kun rivien lukumäärä kasvaa 21=>22=>23, maaliruutujen määrä pysyy samana. Edelleen, joskus yhden rivin lisääminen vähentää maaliruutujen määrää
Kokeilin analyyttisen geometrian avulla ratkaista tehtävää, kun kärkipisteet ovat (0,0), (0,n), (m,n), (m,0). Sain tuon siveltimen toiseksi rajaviivaksi yhtälön
y=n/m(x-1/(2*sqrt(1 (m/n)^2)))-m/(2nsqrt(1 m^2/n^2))
No, ei vaikuta ihan mukavalta summata tuollaista lauseketta. Vähän epäilen, että tehtävän kaava ei ole mitenkään nätti, mutta sen voi esittää summalausekkeena.
Tuolla on vinkki: http://math.stackexchange.com/questions/406008/how-many-squares-contains-paint
Eipä tuo vinkki "Hint: how many vertical and horizontal lines does the paintbrush cross? You need to think about the width of the brush. Draw a picture for a few small cases." tuo analyyttistä ratkaisua yhtään lähemmäksi. Numeerinen ratkaiseminen ei ole mikään ongelma.
Mitä metodia käytät numeeriseen laskemiseen? Luulisi, että jos menetelmäsi toimii kaikille numeerisille tapaksille, niin sille voidaan vääntää symbolinenkin kaava.
>Mitä metodia käytät numeeriseen laskemiseen?
Yksinkertaisesti Excelissä ensin valitsen ne hilan pisteet, joiden etäisyys lävistäjästä on puolikasta pienempi, Näiden avulla määritän ne yksikköneliöt, joiden jokin nurkkapiste kuuluu tuohon pistejoukkoon. Tekninen toteutus yhdelle pisteelle menee. yhdellä Excelin rivillä ja tuloksena saadaan niiden tähän hilappisteeseen liittyvien yksikköneliöden numerot joihin tulee maalia. Aktiivisten rivien määrä on siis sama kuin hilapisteiden määrä. Viimeisellä sarakkeella lasketaan montako eri yksikköneliötä saatiin.
Hmm. Löysin kaavan, mutta en tiedä miten se todistetaan: https://oeis.org/A226246/internal
Hyvin bongattu. Woodsin ratkaisu on sikäli hieno, että se on analyyttinen ratkaisu, omani oli numeerinen algoritmi. Tosiaan tuon SYT-funktion avulla homma hoituu.