2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Septyni lenkimai

Taškai: 12

1. Paimkite languoto popieriaus lapą ir viršutiniame dešiniajame kampe pažymėkite stačiakampį plotą, tarkim, tris eilutes ir penkis stulpelius. Rašalo taškais pažymėkime atsitiktinius langelius.

2. Dabar perlenkime lapą per apatinę pažymėto ploto liniją. Kadangi rašalas vis dar drėgnas, gauname veidrodinį pažymėto ploto atvaizdą.

3. Kairėje pusėje pridėkime papildomų taškų visose veidrodinio vaizdo eilutėse. Dešinėje pusėje esantys skaičiai rodo gretimų eilučių skirtingų langelių skaičių.

4. Dar kartą sulenkime, tik šį kartą žemiau veidrodinio atvaizdo. Gauname naują veidrodinį atvaizdą.

5. Vėl pridėkime papildomų taškų visose eilutėse, esančiose  naujame veidrodiniame atvaizde. Jau dukart lenkėme popieriaus lapą ir dukart pridėjome naujų taškų.


6. Gauname taškais pažymėtų eilučių rinkinį, kuriame nustatome, kiek panašios gretimos eilutės, t. y. išsiaiškiname skirtingų langelių skaičių. Kai kurios eilutės yra panašios viena į kitą, pavyzdžiui, 3 ir 4 eilutės skiriasi tik vienoje vietoje. Kai kurios iš jų yra gana skirtingos, pavyzdžiui, 2 ir 3 eilutės skiriasi net trimis langeliais.

Dabar pradėkime nuo paprastesnio pradinio modelio 2x1 stačiakampyje, kaip parodyta piešinyje.

Septyniskart lankstykime popieriaus lapą ir pridėkime taškų, kad gautume gražų didelį piešinį. Kai tai atliksime (įvertinkime užuominą: geriau pasvarstykime prieš dirbdami iki galo), turėtume rasti skirtingiausias gretimas eilutes. Keliais langeliais jos skiriasi?

A. 1 B. 2 C. 7 D. 8
Paaiškinimas

Įsivaizduokite, kad šios eilutės koduoja dvejetainius skaičius. Septyniskart lankstydami popierių ir pridėdami taškų, gauname 256 skirtingus skaičius. Kaip galime būti tikri, kad jie yra skirtingi? Skaičiai yra nuo 0 iki 255. Pereidami visas eilutes iš viršaus į apačią, išvardijame visas 8 bitų kombinacijas, keisdami tik po vieną bitą.
Šis būdas, vadinamas Grėjaus kodu (https://en.wikipedia.org/wiki/Gray_code), yra labai naudingas daugeliu atvejų: kuriant saugią įrangą ir efektyvis algoritmus ar žaislus, pavyzdžiui, Kinų žiedų galvosūkius (https://en.wikipedia.org/wiki/Baguenaudier) ir Hanojaus bokštus (https://en.wikipedia.org/wiki/Tower_of_Hanoi).

Raktiniai žodžiai: Grėjaus kodas.

Atsakymas

Atsakymas yra 1, t. y. visos gretimos eilutės viena nuo kitos skiriasi tik vienoje vietoje.

Tačiau tikėtina, kad nedirbote iki galo. Modelis yra 256 eilučių ilgio!

Pradinėje schemoje eilutės akivaizdžiai skiriasi vienu langeliu. Parodysime, kad sulenkus lapą ir pridėjus taškų gretimos eilutės skiriasi tiksliai vienoje vietoje.

• Viršutinė dalis lieka tokia pat. Jei eilutės skiriasi vienoje vietoje, tai šis skirtumas ir išlieka.

• Apatinė dalis yra veidrodinis viršutinės dalies atvaizdas, tik papildytas tašku. Kadangi visos apatinės dalies eilutės turi šį tašką, jos skiriasi tuo pačiu taškų skaičiumi kaip ir pirmosios eilutės aukščiau, taigi skiriasi vienoje vietoje.

• Viršutinės dalies apatinė eilutė ir viršutinė eilutė apačioje yra tokios pat, išskyrus tai, kad iš apatinės dalies viršutinės eilės pradžioje yra papildomas taškas. Taigi skiriasi vienoje vietoje.

Kadangi dvi pirmojo vaizdo eilutės skiriasi vienoje vietoje, visos eilutės po visų žingsnių taip pat skiriasi tik vienoje vietoje.