2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Spalvotasis šidoku

Taškai: 12

Šidoku yra jaunesnysis žinomo galvosūkio sudoku broliukas: imama 4x4 dydžio lentelė. Draugai Haris ir Silvija sudaro šidoku schemas iš keturių spalvų langelių (1 = raudonas, 2 = žalias, 3 = mėlynas, 4 = geltonas).

Visų keturių spalvų langelių (skaitmenų) turi būti po vieną kiekvienoje eilutėje, kiekviename stulpelyje ir kiekviename iš keturių 2x2 sektorių, t.y. jie negali kartotis.

Pagal nurodytas sąlygas draugai sudarė šias penkias schemas:

Silvija pastebi, kad C, D, E schemos gali būti gaunamos iš A arba B schemų, atliekant ne daugiau kaip tris iš šių operacijų (kiekvieną ne daugiau kaip vieną kartą):

- sukeisti visus vienos spalvos langelius su kitos spalvos langeliais (pvz., sukeisti visus raudonus langelius su žaliais, t.y. 1 sukeisti su 2)

- sukeisti 1-ą eilutę su 2-a eilute,

- sukeisti 3-ą eilutę su 4-a eilute,

- sukeisti 1-ą stulpelį su 2-u stulpeliu,

- sukeisti 3-ą stulpelį su 4-u stulpeliu.

Pavyzdžiui, paėmę schemą, pavaizduotą žemiau, ir keisdami 3-ą ir 4-ą eilutes (viena operacija), gauname A schemą.

Padėkite Hariui rasti, kuria schema (A ar B) gali būti pakeistos C, D ir E schemos:

C gali būti pakeista ___________

D gali būti pakeista ___________

E gali būti pakeista ___________

Paaiškinimas

Visos šidoku schemos (jų iš viso yra 288, iš kurių tik 12 yra kanoninės raudonos-žalia-mėlynos-geltonos spalvos, t.y. skaitmenys 1-2-3-4 pirmojoje eilutėje) gali būti suskirstytos į dvi lygiavertiškumo klases, t.y.  A ir B kategorijų, susijusių su šiomis operacijomis:
- spalvų (skaitmenų) sukeitimas;
- 1 eilutė sukeičiama su 2 eilute arba 3 eilutė su 4 eilute arba 1-2 eilutės su 3-4 eilutėmis
- tokie patys keitimai su stulpeliais
- atspindys ir sukimasis.
Šiuos rezultatus nepriklausomai gavo Gary McGuire ir Hugo van der Sandeno.
Žr. „Sveikųjų skaičių sekų“ enciklopedija internete, https://oeis.org/A109741 ir https://oeis.org/A107739
„šidoku“ (ir „sudoku“) galvosūkiai yra ypatingas lotyniškų kvadratų atvejis.

Raktiniai žodžiai: šidoku (sudoku 4x4), simbolių sukeitimas, geometrinės transformacijos, ekvivalentiškos klasės.

Atsakymas

Teisingas atsakymas:

C gali būti pakeista į B.
D gali būti pakeista į B.
E gali būti pakeista į A.

Iš tiesų, galima atlikti tokius keitimus:
- schemoje C sukeitus 3 ir 4 stulpelius, o po to mėlyną ir geltoną spalvas, yra gaunama schema B;
- schemoje D sukeitus 3 ir 4 eilutes yra gaunama schema C, o po to per du keitimus, kaip nurodyta aukščiau, yra gaunama schema B;
- pradedant nuo E atlikite tokią operacijų seką: sukeiskite 3 ir 4 eilutes, sukeiskite 3 ir 4 stulpelius ir sukeiskite mėlyną ir geltoną spalvas, tada gausite A.

Interaktyvi užduotis