Ruudukkopulma

Pakko täyttää siis värillä. Paljon kiitoksia!

Täytyy myös miettiä onko eri tavalla täytetty ruudukko, jos ruudukkoa kääntää 90,180 tai 270 astetta. Ja myös tuleeko joka väriä käyttää vähintään kerran tms. Silloin ongelma vaikeutuu.

Esim. onko valkoisella täytetty ruudukko, jossa on musta ruutu vasemassa alakulmassa sama kuin ruudukko, jossa musta ruutu oikeassa alanurkassa (90 asteen kierto). Kierroissa täytyy jakaa 5^64-5 luvulla 4 (viidellä vähentäminen seuraa siitä, että laudat voivat olla 5 tapaa yksivärisiä)

ffffs kirjoitti:

Täytyy myös miettiä onko eri tavalla täytetty ruudukko, jos ruudukkoa kääntää 90,180 tai 270 astetta. Ja myös tuleeko joka väriä käyttää vähintään kerran tms. Silloin ongelma vaikeutuu.

Esim. onko valkoisella täytetty ruudukko, jossa on musta ruutu vasemassa alakulmassa sama kuin ruudukko, jossa musta ruutu oikeassa alanurkassa (90 asteen kierto). Kierroissa täytyy jakaa 5^64-5 luvulla 4 (viidellä vähentäminen seuraa siitä, että laudat voivat olla 5 tapaa yksivärisiä)

... yksiväriset ruudukot, koska niistä ei löydy erilaisia kopioita käänneltäessä -- symmetrian vuoksi.

Mutta entäs kaikki muut kuviot, jotka ovat myös symmetrisiä tiettyjen akseleiden läpi?

nkorppi kirjoitti:

... yksiväriset ruudukot, koska niistä ei löydy erilaisia kopioita käänneltäessä -- symmetrian vuoksi.

Mutta entäs kaikki muut kuviot, jotka ovat myös symmetrisiä tiettyjen akseleiden läpi?

Ei tuo 5^64 ratkaisu mihinkään muutu, vaikka ruudukkoa saisikin käännellä vaakatasossa. Mikä tahansa kuvio mistä tahansa kuviosta 90, 180 tai 270 astetta kääntämällä sitten syntyykin, on se joka tapauksessa jo kertaalleen mukana tuossa 5^64:ssa.

topikoo kirjoitti:

Ei tuo 5^64 ratkaisu mihinkään muutu, vaikka ruudukkoa saisikin käännellä vaakatasossa. Mikä tahansa kuvio mistä tahansa kuviosta 90, 180 tai 270 astetta kääntämällä sitten syntyykin, on se joka tapauksessa jo kertaalleen mukana tuossa 5^64:ssa.

... mutta ideana onkin laskea kaikki kääntämällä syntyvät kuviot SAMAKSI kuvioksi.

Tällöin laskettavien kuvioiden määrä putoaa hieman yli neljäsosaan, kuten alla todistin. Katso sieltä tarkat luvut.

... miten päädyit tuohon lukuun ja mitä se edustaa. Voitko selventää?

nkorppi kirjoitti:

... miten päädyit tuohon lukuun ja mitä se edustaa. Voitko selventää?

pallot ja laatikot ongelmasta: Kuinka monella eri tavalla n samanlaista palloa voidaan jakaa k laatikon kesken. Ratkaisussa ajatellaan laatikot vierekkäin, jolloin täytettäviä paikkoja on n k-1.
Mahdollisia tapoja on yhtä monta kuin on n-kombinaatioita n k-1 alkioisesta joukosta.

Tehtävän tapauksessa ajatellaan että värit ovat laatikoita (k=5) ja ruudut palloja (n=64), jolloin ruudukko voidaan täyttää 68C64 eri tavalla.

jens kirjoitti:

pallot ja laatikot ongelmasta: Kuinka monella eri tavalla n samanlaista palloa voidaan jakaa k laatikon kesken. Ratkaisussa ajatellaan laatikot vierekkäin, jolloin täytettäviä paikkoja on n k-1.
Mahdollisia tapoja on yhtä monta kuin on n-kombinaatioita n k-1 alkioisesta joukosta.

Tehtävän tapauksessa ajatellaan että värit ovat laatikoita (k=5) ja ruudut palloja (n=64), jolloin ruudukko voidaan täyttää 68C64 eri tavalla.

Eli toisin sanoen ideana on laittaa jonoon 68 palloa, ja sitten katsoa kuinka monella tavalla voimme poistaa niistä neljä: näin syntyvät, välein erotellut osajonot edustavat värejä. (Jos kaksi peräkkäistä poistetaan, yksi väri jää välistä pois.)

Ongelma on siinä, että nyt sekä palloille että väreille on etukäteen valittava tietty järjestys. (Muuten et tietäisi mitkä pallot eli 'ruudut' kuuluvat mihinkin väriin.)

Mutta nyt esim. on mahdotonta, että toka pallo saisi ekan värin, mikäli eka pallo saa jonkun muun värin. Ruudukossa tämän tulisi olla mahdollista.

Mielestäni 'pallot ja laatikko'-metodi toimii vain silloin, jos palloja ei ole 'labelled'. Mutta ruudukossa jokaisella pallolla on 'label', eli koordinaatit.

nkorppi kirjoitti:

Eli toisin sanoen ideana on laittaa jonoon 68 palloa, ja sitten katsoa kuinka monella tavalla voimme poistaa niistä neljä: näin syntyvät, välein erotellut osajonot edustavat värejä. (Jos kaksi peräkkäistä poistetaan, yksi väri jää välistä pois.)

Ongelma on siinä, että nyt sekä palloille että väreille on etukäteen valittava tietty järjestys. (Muuten et tietäisi mitkä pallot eli 'ruudut' kuuluvat mihinkin väriin.)

Mutta nyt esim. on mahdotonta, että toka pallo saisi ekan värin, mikäli eka pallo saa jonkun muun värin. Ruudukossa tämän tulisi olla mahdollista.

Mielestäni 'pallot ja laatikko'-metodi toimii vain silloin, jos palloja ei ole 'labelled'. Mutta ruudukossa jokaisella pallolla on 'label', eli koordinaatit.

alkuperäinen ongelma on analoginen ongelman 'Kun 64 samanlaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' kanssa.

Aiemmin tarjottu ratkaisu oli analoginen ongelman 'Kun 64 erilaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' ratkaisun kanssa, mutta huomasitte ettei ruutuja voida samanarvoistaa.

Ongelmaksi ei muodostu tieto siitä, mikä ruutu on minkin värinen, koska ollaan kiinnostuneita ainoastaan mahdollisten jakojen lukumäärästä. Paikat voidaan 'labeloida' antamalla niille järjestysnumerot 1-68 ja valitaan sieltä 64 numeroa näyttämään ruutujen paikat. En ehkä ymmärtänyt mitä hait takaa.

Edellämainitulla tuloksella ei liene paljonkaan
tekemistä alkuperäisen kysymyksen kanssa.

Ensimmäisen vastaajan vastaus lienee oikein jos
lautaa ei saa käännellä.

Jos laudan käänteleminen sallitaan menee kysymys
yli minun kykyjeni.

Uskon kuitenkin pystyväni todistamaan nimimerkki
"jensin" vastauksen (814385) olevan vähintään
tuhatkertaisesti väärässä.

jousimies13 kirjoitti:

Edellämainitulla tuloksella ei liene paljonkaan
tekemistä alkuperäisen kysymyksen kanssa.

Ensimmäisen vastaajan vastaus lienee oikein jos
lautaa ei saa käännellä.

Jos laudan käänteleminen sallitaan menee kysymys
yli minun kykyjeni.

Uskon kuitenkin pystyväni todistamaan nimimerkki
"jensin" vastauksen (814385) olevan vähintään
tuhatkertaisesti väärässä.

mielenkiinnolla odottamaan

jens kirjoitti:

alkuperäinen ongelma on analoginen ongelman 'Kun 64 samanlaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' kanssa.

Aiemmin tarjottu ratkaisu oli analoginen ongelman 'Kun 64 erilaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' ratkaisun kanssa, mutta huomasitte ettei ruutuja voida samanarvoistaa.

Ongelmaksi ei muodostu tieto siitä, mikä ruutu on minkin värinen, koska ollaan kiinnostuneita ainoastaan mahdollisten jakojen lukumäärästä. Paikat voidaan 'labeloida' antamalla niille järjestysnumerot 1-68 ja valitaan sieltä 64 numeroa näyttämään ruutujen paikat. En ehkä ymmärtänyt mitä hait takaa.

... juuri sitä, että mielestäni alkuperäisessä ongelmaa ei voida mallintaa 'samanlaisilla palloilla'.

Mielestäni 'jakojen määrä' ei vastaa 'erilaisten ruudukkojen määrää' missään mielessä. Nimenomaan 'erilaisista ruudukoista' kysyttiin.

En käsitä miksi et hyväksy tarjottua ratkaisua, eli 5^64, tai miksi ajattelet oman ratkaisusi parantavan sitä.

Jos ruudukon symmetriat (esim. ruudokon keskustan suhteen) tulee ottaa huomioon, tietenkin ratkaisu muuttuu ja on jokseenkin helppo laskea sekin.

jens kirjoitti:

alkuperäinen ongelma on analoginen ongelman 'Kun 64 samanlaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' kanssa.

Aiemmin tarjottu ratkaisu oli analoginen ongelman 'Kun 64 erilaista palloa jaetaan viiteen laatikkoon, kuinka monta eri jakoa voidaan suorittaa?' ratkaisun kanssa, mutta huomasitte ettei ruutuja voida samanarvoistaa.

Ongelmaksi ei muodostu tieto siitä, mikä ruutu on minkin värinen, koska ollaan kiinnostuneita ainoastaan mahdollisten jakojen lukumäärästä. Paikat voidaan 'labeloida' antamalla niille järjestysnumerot 1-68 ja valitaan sieltä 64 numeroa näyttämään ruutujen paikat. En ehkä ymmärtänyt mitä hait takaa.

... jos valitsisitkin 64 labeloitua numeroa 68:sta, mitä hyötyä tästä valinnasta on, ellet ole päättänyt missä järjestyksessä aiot luetella niitä?

Jos luettelet ne labeloimisjärjestyksessä, et selvästikään kuvaa kaikkia vaihtoehtoisia ruudukkoja.

Siispä nämä valinnat eivät riitä erilaisten ruudukkojen kuvaamiseen.

Yksinkertainen esimerkki:

Kuinka monta kahden värin 2*2-ruudukkoa on olemassa? Niitä on tietenkin 2^4. Jos ruudukkoa saa käännellä tasossa, elikä symmetriat käsitellään, ruudukkoja on 6:

10
01

11
01

00
10

11
00

00
00

11
11

Mutta omalla laskutavallasi (4 2-1)C4 = 5C1 = 5. Todellakin, jos meillä on neljä identtistä palloa, on viisi 'jakoa' kahteen laatikkoon: Ensimmäisessä laatikossa on joko 0,1,2,3 tai 4 palloa. Mutta tämä ei mitenkään liity ruudukkotehtävään.

jens kirjoitti:

mielenkiinnolla odottamaan

Väritetään ylimmäinen vaakarivi neljällä värillä,
erilaisia tuloksia 4 ^ 8 = 65536.

Väritetään vasen pystyrivi neljällä värillä alkaen
toisesta positiosta, tuloksia 4 ^ 7 = 16384.

Väritetään kaikki muut ruudut viidennellä värillä.

Ymmärrykseni mukaan meillä on nyt erilaisia kuvioita
65536 * 16384 = 1 073 741 824 kpl. Tämä ylittää "jos"-
kirjoituksessa mainitun luvun yli "tuhatkertaisesti".

Näitä kuvioita voimme kiertää 90, 180 ja 270 astetta,
jolloin saamme eri kuvioita nelinkertaisen määrän.

Todellisuudessa kuvioita on paljon enemmänkin, mutta
kuten aikaisemmin sanoin, se menee yli kykyjeni.

jousimies13 kirjoitti:

Väritetään ylimmäinen vaakarivi neljällä värillä,
erilaisia tuloksia 4 ^ 8 = 65536.

Väritetään vasen pystyrivi neljällä värillä alkaen
toisesta positiosta, tuloksia 4 ^ 7 = 16384.

Väritetään kaikki muut ruudut viidennellä värillä.

Ymmärrykseni mukaan meillä on nyt erilaisia kuvioita
65536 * 16384 = 1 073 741 824 kpl. Tämä ylittää "jos"-
kirjoituksessa mainitun luvun yli "tuhatkertaisesti".

Näitä kuvioita voimme kiertää 90, 180 ja 270 astetta,
jolloin saamme eri kuvioita nelinkertaisen määrän.

Todellisuudessa kuvioita on paljon enemmänkin, mutta
kuten aikaisemmin sanoin, se menee yli kykyjeni.

... ruudukkojen määrän, kun sallimme kierrot? Helppo homma.

Huomaa, että ruudukosta voi kierrettäessä saada joko 1,2 tai 4 erilaista 'fiksattua ruudukkoa', riippuen siitä riittääkö kvadrantti (1) tai puolisko (2) määrittelemään ruudukon tai ei (4).

On parasta lähteä laskemaan tapauksia (1), (2) sekä (4) järjestyksessä.

(1) : Laskemme siis ruudukkoja, joissa sama kvadrantti monistetaan neljäksi (eri tavalla orientoiduksi) kvadrantiksi. Tätä voi käännellä miten haluaa, ja saamme vain yhden 'fiksatun ruudukon'.

Näitä on 5^16 kappaletta.

(2): Laskemme puoliskoja, joissa puolisko monistetaan kahdeksi eri tavalla orientuiduksi puoliskoksi, mutta vähennämme summasta jo lasketut 'fiksatut ruudukot'. Näitä käännellessä saamme kustakin kaksi 'fiksattua ruudukkoa'.

Näitä on siis (5^32-5^16)/2 .

(4): Loppuja ruudukkoja on tietysti

(5^64 - 5^32)/4 .

Siispä ruudukkoja on yhteensä

1/4(5^64 5^32) 1/2(5^16) =

1/4 * 5^64.

Eli tässä tapauksessa sattuu olemaan niin, että kääntely sallimalla saadaan neljäsosa siitä määrästä, kun kääntelyä ei sallittu.

Väitän, että kaava

1/4(k^(2n) k^n) 1/2(k^(n/2))

pätee kaikille n*n ruudukoille, jotka väritetään k:lla värillä, missä n on parillinen.

Esim. kun k = n = 2, saamme arvon 6, kuten pitääkin. Huomaa, että 6 = 3/8 * 2^4, joten kääntelyn salliminen ei yleisesti vähennä ruudukkojen määrää neljäsosaan.

nkorppi kirjoitti:

... ruudukkojen määrän, kun sallimme kierrot? Helppo homma.

Huomaa, että ruudukosta voi kierrettäessä saada joko 1,2 tai 4 erilaista 'fiksattua ruudukkoa', riippuen siitä riittääkö kvadrantti (1) tai puolisko (2) määrittelemään ruudukon tai ei (4).

On parasta lähteä laskemaan tapauksia (1), (2) sekä (4) järjestyksessä.

(1) : Laskemme siis ruudukkoja, joissa sama kvadrantti monistetaan neljäksi (eri tavalla orientoiduksi) kvadrantiksi. Tätä voi käännellä miten haluaa, ja saamme vain yhden 'fiksatun ruudukon'.

Näitä on 5^16 kappaletta.

(2): Laskemme puoliskoja, joissa puolisko monistetaan kahdeksi eri tavalla orientuiduksi puoliskoksi, mutta vähennämme summasta jo lasketut 'fiksatut ruudukot'. Näitä käännellessä saamme kustakin kaksi 'fiksattua ruudukkoa'.

Näitä on siis (5^32-5^16)/2 .

(4): Loppuja ruudukkoja on tietysti

(5^64 - 5^32)/4 .

Siispä ruudukkoja on yhteensä

1/4(5^64 5^32) 1/2(5^16) =

1/4 * 5^64.

Eli tässä tapauksessa sattuu olemaan niin, että kääntely sallimalla saadaan neljäsosa siitä määrästä, kun kääntelyä ei sallittu.

Väitän, että kaava

1/4(k^(2n) k^n) 1/2(k^(n/2))

pätee kaikille n*n ruudukoille, jotka väritetään k:lla värillä, missä n on parillinen.

Esim. kun k = n = 2, saamme arvon 6, kuten pitääkin. Huomaa, että 6 = 3/8 * 2^4, joten kääntelyn salliminen ei yleisesti vähennä ruudukkojen määrää neljäsosaan.

Tarkoitan tietysti d*d ruudukkoa, missä d = sqrt(2n). :)

nkorppi kirjoitti:

... juuri sitä, että mielestäni alkuperäisessä ongelmaa ei voida mallintaa 'samanlaisilla palloilla'.

Mielestäni 'jakojen määrä' ei vastaa 'erilaisten ruudukkojen määrää' missään mielessä. Nimenomaan 'erilaisista ruudukoista' kysyttiin.

En käsitä miksi et hyväksy tarjottua ratkaisua, eli 5^64, tai miksi ajattelet oman ratkaisusi parantavan sitä.

Jos ruudukon symmetriat (esim. ruudokon keskustan suhteen) tulee ottaa huomioon, tietenkin ratkaisu muuttuu ja on jokseenkin helppo laskea sekin.

kiinnostunut nimen omaan pienimmästä ratkaisusta. Nähtävästi palloja tulee ajatella erilaisina, kuten esimerkissäsi näytit.

nkorppi kirjoitti:

... ruudukkojen määrän, kun sallimme kierrot? Helppo homma.

Huomaa, että ruudukosta voi kierrettäessä saada joko 1,2 tai 4 erilaista 'fiksattua ruudukkoa', riippuen siitä riittääkö kvadrantti (1) tai puolisko (2) määrittelemään ruudukon tai ei (4).

On parasta lähteä laskemaan tapauksia (1), (2) sekä (4) järjestyksessä.

(1) : Laskemme siis ruudukkoja, joissa sama kvadrantti monistetaan neljäksi (eri tavalla orientoiduksi) kvadrantiksi. Tätä voi käännellä miten haluaa, ja saamme vain yhden 'fiksatun ruudukon'.

Näitä on 5^16 kappaletta.

(2): Laskemme puoliskoja, joissa puolisko monistetaan kahdeksi eri tavalla orientuiduksi puoliskoksi, mutta vähennämme summasta jo lasketut 'fiksatut ruudukot'. Näitä käännellessä saamme kustakin kaksi 'fiksattua ruudukkoa'.

Näitä on siis (5^32-5^16)/2 .

(4): Loppuja ruudukkoja on tietysti

(5^64 - 5^32)/4 .

Siispä ruudukkoja on yhteensä

1/4(5^64 5^32) 1/2(5^16) =

1/4 * 5^64.

Eli tässä tapauksessa sattuu olemaan niin, että kääntely sallimalla saadaan neljäsosa siitä määrästä, kun kääntelyä ei sallittu.

Väitän, että kaava

1/4(k^(2n) k^n) 1/2(k^(n/2))

pätee kaikille n*n ruudukoille, jotka väritetään k:lla värillä, missä n on parillinen.

Esim. kun k = n = 2, saamme arvon 6, kuten pitääkin. Huomaa, että 6 = 3/8 * 2^4, joten kääntelyn salliminen ei yleisesti vähennä ruudukkojen määrää neljäsosaan.

... tietenkään ei pidä paikkaansa, että

1/4(5^64 5^32) 1/2(5^16) = 1/4 * 5^64

:D

mutta laskin pyöristää sen näin, jos kokeilet jakaa vasemman puolen luvulla 5^64.

Elikä tosiasiassa luku on 'vähän' suurempi kuin neljäsosa luvusta 5^64.

jousimies13 kirjoitti:

Väritetään ylimmäinen vaakarivi neljällä värillä,
erilaisia tuloksia 4 ^ 8 = 65536.

Väritetään vasen pystyrivi neljällä värillä alkaen
toisesta positiosta, tuloksia 4 ^ 7 = 16384.

Väritetään kaikki muut ruudut viidennellä värillä.

Ymmärrykseni mukaan meillä on nyt erilaisia kuvioita
65536 * 16384 = 1 073 741 824 kpl. Tämä ylittää "jos"-
kirjoituksessa mainitun luvun yli "tuhatkertaisesti".

Näitä kuvioita voimme kiertää 90, 180 ja 270 astetta,
jolloin saamme eri kuvioita nelinkertaisen määrän.

Todellisuudessa kuvioita on paljon enemmänkin, mutta
kuten aikaisemmin sanoin, se menee yli kykyjeni.

Ruudukkoja on
542101086242752217003726400434970855712890625
eli 5^64 kappaletta jos kääntelyä ei sallita.

Ruudukkoja on
135525271560688054250937420874834136962890624
eli 1/4(5^64 5^32) 1/2(5^16)

jens kirjoitti:

mielenkiinnolla odottamaan

... eli vaikka sallisimme kääntelyn, ruudukkoja on silti

135525271560688054250937420874834060668945312

Tämä luku on

166414253161205147750679863792719734117

kertaa niin iso luku kuin oma vastauksesi 814385.

nkorppi kirjoitti:

... eli vaikka sallisimme kääntelyn, ruudukkoja on silti

135525271560688054250937420874834060668945312

Tämä luku on

166414253161205147750679863792719734117

kertaa niin iso luku kuin oma vastauksesi 814385.

Sori tuli väärä luku. ääääh.

135525271560688054250937420874834136962890624

oli siis oikein.

Se on

166414253161205147750679863792719827799

kertaa niin iso kuin 814385.