Sivellinprobleema

maalarimiespohtija

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?

19

78

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Laskee,

      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.

      • Matikisti

        Lausekkeen on pakko riippua sekä m:stä että n:stä.


      • 6+9
        Matikisti kirjoitti:

        Lausekkeen on pakko riippua sekä m:stä että n:stä.

        ämmistä ei ole muuta kuin harmia, tässä se taas nähtiin...


    • Laskee,

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

      • 3+6

        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.


    • Laskee,

      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.

      • Laskee,

        Joo, en tuohon analyyttistä ratkaisua osaa kehittää. Mahtaako ketjun aloittajalla olla? Laskennallisesti ongelmaa voi tutkia. Onko aloittajalla jokin tietty ruudukon koko mielessä?


      • 11+4
        Laskee, kirjoitti:

        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!


      • maalarimiespohtija
        Laskee, kirjoitti:

        Joo, en tuohon analyyttistä ratkaisua osaa kehittää. Mahtaako ketjun aloittajalla olla? Laskennallisesti ongelmaa voi tutkia. Onko aloittajalla jokin tietty ruudukon koko mielessä?

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


    • 1+8

      Tapauksessa m=n (neliöruudukko) nähdään hyvin simppelisti että ratkaisu on 3*n-2. Joten ei tuo 4*n-2 pidä paikkansa.

    • Laskee,

      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

      • Laskee,

        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ää


    • kokkeilijakuopio

      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.

    • Laskee,

      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.

      • uteliasmiesjostain

        Mitä metodia käytät numeeriseen laskemiseen? Luulisi, että jos menetelmäsi toimii kaikille numeerisille tapaksille, niin sille voidaan vääntää symbolinenkin kaava.


    • Laskee,

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

    • maalarimiespohtija
    • Laskee,

      Hyvin bongattu. Woodsin ratkaisu on sikäli hieno, että se on analyyttinen ratkaisu, omani oli numeerinen algoritmi. Tosiaan tuon SYT-funktion avulla homma hoituu.

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Kela valvoo lasten tilejä.

      Tämä isoveli Kela kyttää jopa lasten yli 200,- euron rahat jotka on melko varmasti lahjaksi saatu. Se vaikuttaa perheen
      Yhteiskunta
      284
      3131
    2. Nainen, tervetuloa

      Tule luokseni eka vaikka viikoks tai pariksi. Saisin helliä, kannustaa ja tukea sua ja kokata lempi herkkujasi. Pääsisit
      Ikävä
      23
      2734
    3. TTK-tähti Saana Akiola paljasti tv-ohjelmassa tapahtuneen ahdistelun

      Olisko pitänyt suunnitella ulostulo paremmin? Nyt lehdet soittelevat kaikki 8 läpi ja kuusi sanoo ettei koskenut häntä.
      Maailman menoa
      20
      1853
    4. Mitä haluaisit sanoa hänelle

      Nyt tällä hetkellä?
      Ikävä
      130
      1851
    5. Elisa laskuttaa jo sähköpostilaskusta erikseen euron

      Paperilaskuista on otettu lisämaksua jo ajat sitten, mutta nyt Elisa ottaa euron siitä että lähettävät sähköisen laskun
      Maailman menoa
      115
      1606
    6. Olisit ollut varovaisempi

      Nyt jos minut hylkäät ja et meidän asiasta minulle mitään ilmoita niin ettet edes anteeksi pyydä, niin tiedä että minä e
      Ikävä
      35
      1594
    7. Oho! Susanna Laine kohtasi epäonnea lomareissulla Italiassa - Avaa tilannetta: "Vähän sahaavaa..."

      Ou nou! Tsemppiä kuitenkin loppulomaan Italiassa, Susanna Laine ja mahdollinen seuralainen! Lue lisää ja katso kuvat:
      Suomalaiset julkkikset
      7
      1370
    8. Ensitreffit alttarilla Jyrki paljastaa hääyön intiimiasioista kameroiden sammuttua: "Fyysinen..."

      Ooo-la-laa… Ensitreffit alttarilla -sarjassa alkaa hääparien välillä ns. tunteet kuumenemaan. Lue lisää: https://www.s
      Ensitreffit alttarilla
      2
      1143
    9. Väliämme on noin 6 km

      Niin lähellä ja niin kaukana. Sinä olet kotona, minä olen kotona. Olet jo unessa. Mutta kun herään, olet jo töissä ja vä
      Ikävä
      9
      1113
    10. Odotatko vielä

      Häntä?????
      Ikävä
      62
      1063
    Aihe