Fórum: Héttusa feladatok

A huszárok 3 ütéses elrendezésének inkább ezt őrizzük meg:

Sajnos nem tudok 2 képet egyszerre bevinni, így külön következnek az ábrák - és gúlától elnézést a dupla ékezetért :-)

Káli gűla mindent ismer, így csak azért foglalom össze, hogy jól lássék egy helyen az aktuális tudásunk...

32 huszár, mindegyik pontosan 3 másikat üthet: https://puzzling.stackexchange.com/questions/94766/knights-attacking-exactly-three-knights

18 vezér, mindegyik 3 másikat üthet: https://kvant.mccme.ru/pages.html 2009/4 borító (Némi utánolvasással kiderül, hogy királynőkre ez egy régi puzzle, több helyen is felbukkant, Scott Kim zseniális dizájnertől származik. Érdemes elolvasni a róla szóló teljes fejezetet Martin Gardner The Last Recreations c. könyvében.)

Bástyából nem lehet pontosan 3 ütéses sereg: a bal alsó sarokhoz legközelebbi max kettőt (fel és jobbra állót) tud támadni.

20 futó, mindegyik 1 másikat üthet: https://puzzling.stackexchange.com/questions/94421/chess-pieces-attacking-exactly-once/94479#94479

Huszárok, mindegyik pontosan 1 másikat üthet: 32-nél többet nem lehet, a táblát lefedjük négyes ciklusokkal, valamelyik négyelemű ciklusba 2-nél több bábu kerülne. https://www.linux-magazine.com 2018/211/knight-s-tour/figure-2

Huszárok, mindegyik pontosan 2 másikat üthet: 32-nél többet nem lehet. Programmal végignéztem, és nem talált 32-nél nagyobb halmazt.

17. kérdés. (a) Helyezzünk el a sakktáblán 30 huszárt úgy, hogy mindegyik pontosan 2 másikat támad. (b) Helyezzünk el a sakktáblán 38 huszárt úgy, hogy mindegyik legfeljebb 2 másikat támad. (c) Hány huszárt lehet elhelyezni a sakktáblán úgy, hogy mindegyik pontosan 4 másikat támad?

A következőt sem találtam:

Néhány új elrendezés (amiket eddig nem találtam).

Kiegészíteném Róka Sándor táblázatát.

Elnézést, ha valamin átsiklottam...

8. kérdés. Királyok pontosan 2 ütéssel kérdésre a válasz 32. Több nem lehet, ez valamennyire pepecselős, de megoldható kézzel. Tegyük fel, hogy 33 király van a táblán, és mindegyik 2 másikkal szomszédos. Ekkor például a bal oldali féltáblán 16-nál, és pl. a bal felső negyedben 8-nál több bábu van. Felosztjuk a táblát 2x2-es kis négyzetekre az ábra szerint. Egy háromkirályos négyzet bábui ciklust alkotnak, az ilyen királyokkal szomszédos mezők mindig üresek. Emiatt 2 háromelemű négyzet nem lehet egymás mellett, ha pedig csúcsban találkoznának (pl. \(\displaystyle A,D\)), akkor a másik két négyzet (\(\displaystyle B,C\)) legfeljebb egyelemű lehetne. Tehát a bal felső negyedben csak 9=3+2+2+2 kiosztásban lehetnek bábuk. Sem \(\displaystyle |B|=3\), sem \(\displaystyle |C|=3\) nem lehet, mert abból \(\displaystyle |A|=1\) következne az a8 különleges helyzete miatt. Tehát vagy \(\displaystyle |A|=3\), vagy \(\displaystyle |D|=3\).

A középső ábra mutatja az \(\displaystyle |A|=3\) esetet. \(\displaystyle B\) csak a második oszlopában tartalmazhatja a két királyt, ekkor a d8 a másik szomszédos királlyal (e7 vagy e8) hármas ciklust alkot, így blokkolja a c6, d6 mezőket. Hasonlóan blokkolt a c5, c6 mezőpár is \(\displaystyle C\) oldaláról, tehát \(\displaystyle D\)-ben legfeljebb csak d5-ön lehetne bábu, ami viszont ellentmondás.

A jobb oldali ábrán látszik a \(\displaystyle |D|=3\) eset. Belátjuk, hogy \(\displaystyle |E|+|F|+|G|+|H|\le7\). Feltehetjük, hogy \(\displaystyle E,F,G,H\) egyike sem 3 elemű, mert \(\displaystyle E\) a \(\displaystyle C\)-beli, \(\displaystyle F\) a \(\displaystyle D\)-beli elrendezés miatt biztosan nem az, \(\displaystyle |H|=3\) esetén \(\displaystyle |F|\le1\) és \(\displaystyle |G|\le1\), tehát \(\displaystyle |E|+|F|+|G|+|H|\le7\) adódna, ha pedig \(\displaystyle |G|=3\) lenne, abból \(\displaystyle |E|=1\) és \(\displaystyle |H|=1\) vagy \(\displaystyle |F|=1\) következne, azaz ismét \(\displaystyle |E|+|F|+|G|+|H|\le7\) adódna. Ha tehát \(\displaystyle F,G,H\) kételeműek, akkor – ilyen sorrendben nézve – csak az ábra szerinti párokat tartalmazhatják. Így viszont b4-re nem kerülhet bábu, mert a2 árván maradna, tehát a5 csak a4-en, c3 csak b3-on folytatható, ami b3-nál hibához vezet. Ez ismét ellentmondás, ami tehát igazolja, hogy 32-nél több király nem lehet ezzel a tulajdonsággal.

A 32 király elérhető, de csak két körrel, a külső kör a sarkok nélkül 24 peremmezőből áll, a belső kör ugyanígy 8 mező a középső 4x4-es négyzet szélén. Összefüggő, húr nélküli királykör legfeljebb 31 elemű lehet, ezt megkapjuk, ha a 24 peremmezőből álló kört jobbról "benyomjuk" a h7-g6-f6-e6-d6-c5-c4-d3-e3-f3-g4-h3-h2 görbe mentén.

Ha viszont pontosan 2 helyett legfeljebb 2 ütést kívánnánk, akkor már lehet 33 király a táblán: az egyik sarok 3 szomszédján, és további három, ezzel párhuzamos, de sarok nélküli L-alakú csoportban.

Augusztus 2-án, szűkebb körben eljutott hozzám dr. Császár Gyula válasza az [57.hsz.]-ben látott 8. kérdésre. Azóta eltelt több, mint 3 hét, e körben nem találkoztam kiegészítéssel, cáfolattal, ezért most felteszem dr. Császár Gyula példával illusztrált, bizonyítandó állítását/sejtését:

Az OEIS-ben található 26-os elrendezés: A051754

Hopsssz ...
Valóban. Nem vettem észre. Köszönöm.

A 27-esben és a törpésben is az a feladat, hogy az \(\displaystyle \{1, 2, 3, 4, 5, 6, 7\}\) halmaznak válasszuk ki a lehető legtöbb 3-elemű részhalmazát úgy, hogy bármely két részhalmaznak legfeljebb egy közös eleme legyen.

Van egy kedves élményem a feladatról.
A törpés feladatot elmondtam Danka Emmának (most volt hatodikos). Talán még magyaráztam volna, miről szól a feladat, de már jön is Emma a válasszal:

Legfeljebb 7 nap lehet. Ha a törpepárokat nézzük, 21 pár van. Egy pár legfeljebb egy hármasban lehet. Egy hármasban 3 db párost látunk. Ha a hármasok száma \(\displaystyle m\), akkor \(\displaystyle 3m\le21\), \(\displaystyle m\le7\).

A 27-es megoldása itt olvasható.

javítás: A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon. 8 vagy több nap így nem lehet.

helyett legyen inkább

A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon, minden pár maximum egyszer. 8 vagy több nap így nem lehet.

Igen, ez megegyezik a 27-as feladattal, szöveg és megoldás: https://ematlap.hu/hettusa-2/1409-hettusa4-megoldasok-megjegyzesek .

Hét napra konstrukció: A "Fano sík" nevű kombinatorikai konstrukció, lásd ábra. A zöld pöttyök a törpék, és a 6 egyenes szakasz, illetve a kör által meghatározott hármasok maradnak otthon minden nap. Az ábráról leolvasható hogy ez jó. (Ábra a linkelt Érintő cikkből.) Bővebben: https://hu.wikipedia.org/wiki/Fano-sík

Hétnél több nap nem lehet: A hét törpe 21 párt alkot. Minden nap pontosan 3 pár marad otthon. 8 vagy több nap így nem lehet.

Nekem elsőre úgy tűnik, ez megegyezik a Héttusa 27. feladattal - más szövegezéssel. Így legfeljebb 7 napig lehet így szervezni.

A Héttusa (Érintő) feladataiban felbukkant már a hét törpe (21. és 28. feladatok). Itt vannak ismét.

16. kérdés: A hét törpe közül naponta hárman otthon maradnak, és a többiek elmennek a bányába dolgozni. Arra vigyáznak, hogy bármely két naphoz legfeljebb egy olyan törpe legyen, aki mindkétszer otthon maradt.
Legfeljebb hány napig lehet így megszervezni a munkába járást?

A 6. kérdést – Legfeljebb hány királynő helyezhető el a sakktáblán úgy, hogy mindegyik legfeljebb egy másikat tartson ütés alatt? – láttam feladva \(\displaystyle 20\times20\)-as táblára itt.

A Harvard-MIT Mathematics Tournament (February, 2004) Guts Round — Solutions pdf-ben keressétek, a 44. feladat az. Bizonyítják, hogy legfeljebb 26 királynő állhat a táblán, és 23 királynőt el tudnak helyezni.

Ezzel zárul a megoldásuk: The best possible number of queens is not known to us; the following construction gives 23.

Tudunk-e jobbat? 23-nál többet, vagy szorosabb korlátot 26-nál.

15. kérdés: Legfeljebb hány királynő helyezhető el a \(\displaystyle 20\times20\)-as sakktáblán úgy, hogy mindegyik legfeljebb egy másikat tartson ütés alatt?

12/b kérdés. Az összeg bármi lehet a két korlát között. Jelöljük \(\displaystyle \pi_{k}\)-val azt a permutációt, ami az első \(\displaystyle n-k\) elemet fixen hagyja, az utolsó \(\displaystyle k\) elemet pedig tükrözi: \(\displaystyle \pi_k(n-k+i)=n+1-i\)  (\(\displaystyle i=1,\ldots,k\)). Könnyű látni, hogy ha a sorozat vége egyesével nő vagy fogy, akkor a \(\displaystyle \pi_{k}\) permutációt alkalmazva az eltérésösszeg éppen \(\displaystyle (k-1)\)-gyel nő, és a sorozatvég monotonitása – eggyel rövidebb szakaszon – megmarad. Ezért ilyen permutációk alkalmas sorozatával megoldható, hogy az eltérések összege egyesével változzon, \(\displaystyle n-1\)-től kezdve egészen \(\displaystyle n(n-1)/2\)-ig:

1 2 3 4 5 6 7  <<<
1 2 3 4 5 7 6
1 2 3 4 7 6 5
1 2 3 7 6 5 4
1 2 7 6 5 4 3
1 7 6 5 4 3 2  <<<
1 7 6 5 4 2 3
1 7 6 5 2 3 4
1 7 6 2 3 4 5
1 7 2 3 4 5 6  <<<
1 7 2 3 4 6 5
1 7 2 3 6 5 4
1 7 2 6 5 4 3  <<<
1 7 2 6 5 3 4
1 7 2 6 3 4 5  <<<
1 7 2 6 3 5 4

Az eltérésösszeg az utolsó permutációban még nem maximális, mert – ahogyan a kitűzésben is szerepelt – az alternáló tulajdonság mellett az is kell ehhez, hogy a szélső elemek minimális abszolút értékűek legyenek (a sorozatot 0 körülinek gondolva). Ez a jobb szélen teljesül, mert oda a sorozatvég monotonitásának megszűntével az átlag (,,nulla") kerül. A bal szélső helyre viszont az 1-et a többi \(\displaystyle \lfloor n/2\rfloor-1\) darab, átlagnál kisebb (,,negatív") számmal felcserélve az alternáló tulajdonság megmarad, és rendre megkapjuk a hiányzó, egyre nagyobb összegeket adó permutációkat:

2 7 1 6 3 5 4
3 7 2 6 1 5 4

Érdemes megnézni a módszert nagyobb elemszámmal, például a százelemű permutációkon. Itt az eltérésösszeg 99 és 4999 (=4950+49) közé eshet. Keressünk először olyan sorrendet, ahol az eltérésösszeg 1234. Mivel \(\displaystyle 1234=99+98+\ldots+87+25\), ezért a keresett permutáció \(\displaystyle id\circ\pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_{88}\circ\pi_{26}\) (a kompozíciókat balról jobbra haladva végezve). Mivel

\(\displaystyle id\circ\pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_{88}= \langle 1,100,2,99,\ldots,6,95,7,8,9,\ldots,94\rangle,\)

így \(\displaystyle \pi_{26}\)-tal az utolsó 26 elemet még tükrözve az eredmény:

\(\displaystyle \langle 1,100,2,99,\ldots,6,95,7,8,9,\ldots,68,94,93,92,\ldots,69\rangle.\)

Másik példa egy 4950 feletti eredményhez, pl. 4987-hez. Mivel \(\displaystyle 4987=4950+37\), ezért a teljesen alternáló \(\displaystyle \pi_{99}\circ\pi_{98}\circ\ldots\circ\pi_2\) permutációban a 38-at kell az 1-gyel felcserélni ahhoz, hogy az összeg 37-tel nőjön:

\(\displaystyle \matrix{ \langle 1,100,2,99,3,98,\ldots,37,64,38,63,39,62,\ldots,49,52,50,51\rangle \\ \Downarrow \\ \langle 38,100,2,99,3,98,\ldots,37,64,1,63,39,62,\ldots,49,52,50,51\rangle. }\)

Lemaradt: a 14. kérdéshoz.

Egy 18 átlót használó változat.

A Héttusa (ematlap.hu) legutóbbi fordulójában volt ez a feladat:

33. Egy 12-oldalú szabályos sokszögnek legfeljebb hány átlóját tudjuk megrajzolni úgy, hogy bármelyik legfeljebb egy másikat metszhet a sokszög belsejében?

A feladatsor, az 5. forduló itt van.
A kérdésre 14 a válasz. A megoldások már kint vannak az Érintő Facebook oldalán.

Ehhez kapcsolódva van egy új kérdésem.

14. kérdés: Egy 12-oldalú szabályos sokszögnek legfeljebb hány átlóját tudjuk megrajzolni úgy, hogy bármelyik legfeljebb két másikat metszhet a sokszög belsejében?

Rajzolgattam, az első próbálkozások 15 átlót adtak, majd találtam 17 átlót is, melyek teljesítik a feltételt.
A válasz talán 17?

A Kürschák verseny feladata volt 1962-ben:
Bizonyítsuk be, hogy egy konvex \(\displaystyle n\)-szög átlói közül nem lehet \(\displaystyle n\)-nél többet úgy kiválasztani, hogy bármely kettőnek legyen közös pontja.
A versenyen ez volt a legnehezebb feladat.
Megoldás: A konvex \(\displaystyle n\)-szög alakja nem számít. Feltehető tehát, hogy szabályosról van szó. Ebben az átlók iránya \(\displaystyle n\)-féle lehet, legfeljebb ennyi tehát a páronként metszők száma is.

Hoppá, 12/b túl könnyű lett, 6.5 trivi ellenpélda. Legyen

12/b' kérdés: a magasságkülönbségek összege lehet-e bármilyen egész szám 6 és 23 között?

12. kérdés: Legyenek a gyerekek magasságai \(\displaystyle M = \{m_i\}_i = \{-3,-2,-1,0,1,2,3\}\).

Egy üléssorrend során a magasságkülönbségek abszolút összege valami összeg amiben ezek a számok szerepelnek valamilyen előjelekkel; akik a szélén ülnek azok egyszer, akik középen, azok kétszer.

Világos, hogy \(\displaystyle 2 \cdot (0+1+1+2+2+3+3) - 1 - 0 = 23 \) -nál több nem lehet. (Mindenki pozitívan járul az összeghez 2x, a legkisebb abszolútértékűek meg csak 1x.) Az meg előáll úgy, hogy a két szélén a 0 és 1 ül, a többiek meg előjel szerint váltakozva, vagy a két szélén a 0 és -1 ül, a többiek meg előjel szerint váltakozva. Ezek mind maximálisak, és csak ezek.

12/b kérdés: Azt könnyű látni hogy a magasságkülönbségek összegének legkisebb értéke 6: sorban ülnek. Lehet-e bármilyen szám 6 és 23 között?

> A feladatot lehetne variálni. A kártya egyszeri használata marad, ám használat után az ATM blokkot ad, és akkor kiderül, milyen összeg volt a kártyán. (Esetleg csak pénz kifizetése esetén adja a blokkot.)

Ezeket a kártya információs variánsokat leöli amit 71-ben írtam (kb amit 69-ben te írtál). Még azt a variánst is, hogy Dagobert kevesebbet tud, nem tudja hogy egy kártya el lett-e fogadva, csak a legvégén.

Dagobert konstans stratégiája nem használ információkat, a bank meg tudja garantálni, hogy annál többet ne tudjon felvenni semmilyen információ birtokában.

A válasz a 12. kérdésre: 23

Bocs, de az MI-vel írattam egy programot erre a feladatra, és közlöm azt, mivel eddig még nem volt beküldő.

Íme a válasza:

A program lefuttatása alapján a maximális különbségek összege: 23. Az alábbi 48 permutáció adja ezt az összeget:

(133, 135, 131, 136, 132, 137, 134)

(133, 135, 131, 137, 132, 136, 134)

(133, 135, 132, 136, 131, 137, 134)

(133, 135, 132, 137, 131, 136, 134)

(133, 136, 131, 135, 132, 137, 134)

(133, 136, 131, 137, 132, 135, 134)

(133, 136, 132, 135, 131, 137, 134)

(133, 136, 132, 137, 131, 135, 134)

(133, 137, 131, 135, 132, 136, 134)

(133, 137, 131, 136, 132, 135, 134)

(133, 137, 132, 135, 131, 136, 134)

(133, 137, 132, 136, 131, 135, 134)

(134, 131, 136, 132, 137, 133, 135)

(134, 131, 136, 133, 137, 132, 135)

(134, 131, 137, 132, 136, 133, 135)

(134, 131, 137, 133, 136, 132, 135)

(134, 132, 136, 131, 137, 133, 135)

(134, 132, 136, 133, 137, 131, 135)

(134, 132, 137, 131, 136, 133, 135)

(134, 132, 137, 133, 136, 131, 135)

(134, 133, 136, 131, 137, 132, 135)

(134, 133, 136, 132, 137, 131, 135)

(134, 133, 137, 131, 136, 132, 135)

(134, 133, 137, 132, 136, 131, 135)

(134, 135, 131, 136, 132, 137, 133)

(134, 135, 131, 137, 132, 136, 133)

(134, 135, 132, 136, 131, 137, 133)

(134, 135, 132, 137, 131, 136, 133)

(134, 136, 131, 135, 132, 137, 133)

(134, 136, 131, 137, 132, 135, 133)

(134, 136, 132, 135, 131, 137, 133)

(134, 136, 132, 137, 131, 135, 133)

(134, 137, 131, 135, 132, 136, 133)

(134, 137, 131, 136, 132, 135, 133)

(134, 137, 132, 135, 131, 136, 133)

(134, 137, 132, 136, 131, 135, 133)

(135, 131, 136, 132, 137, 133, 134)

(135, 131, 136, 133, 137, 132, 134)

(135, 131, 137, 132, 136, 133, 134)

(135, 131, 137, 133, 136, 132, 134)

(135, 132, 136, 131, 137, 133, 134)

(135, 132, 136, 133, 137, 131, 134)

(135, 132, 137, 131, 136, 133, 134)

(135, 132, 137, 133, 136, 131, 134)

(135, 133, 136, 131, 137, 132, 134)

(135, 133, 136, 132, 137, 131, 134)

(135, 133, 137, 131, 136, 132, 134)

(135, 133, 137, 132, 136, 131, 134)

Tehát a maximális különbség összege 23, és több különböző permutáció is elérheti ezt az összeget. ​

Valóban: A 13.a állítás igaz 3-, 4-, 5-szögre, de 6-szögre már nem, mint azt az ellenpélda is mutatja.

Ami a 13.b kérdést illeti: A problémát (angolul: diameter of the flip graph) már megoldották az összes konvex sokszögre. A megoldók: Daniel Sleator, Robert Tarjan, William Thurston és Lionel Pournin.

A megoldás 3-szögre 0, 4-szögre 1, 5-szögre 2, 6-szögre 4, 7-szögre 5, 8-szögre 7 stb. (OEIS A005152).

De még vannak ezzel kapcsolatos megoldandó problémák. Például, hogy mekkora a legkisebb átlócserés lépéstávolság (flip distance) két tetszőleges háromszögelés között. Érdekes, hogy nyitott kérdés még ennek a számítástechnikai komlexitása is (P, NP-komplett, NP-hard?).