Egy sakktáblán minden sorban és oszlopban 2 báb van (összesen 16), elérhető-e néhány báb levételével, hogy minden sorban és oszlopban 1 báb álljon? Letudná nekem a megoldást valaki vezetni?

Igen; például ha a két főátlóban állnak a bábuk, akkor minden sorban és oszlopban 2-2 áll, majd ha az egyik főátlót felszámoljuk, akkor a másik átlóban maradtak kielégítik a feltételeket.

Hogy ez tetszőleges felállásnál igaz lesz, azt nem nehéz belátni, ugyanis bármelyik felállásból sor- és oszlopcserével megkapható az előbb felvázolt eset.

Nem kapható meg a két főátlós eset bármely másikból sor és oszlopcserével.

Például ha az a8-h1 és a7-g1 átlókon állnak bábuk, és még egy h8-on, ez nem rendezhető át, hiszen itt a bábuk nem 4-esével téglalapokban helyezkednek el, ellentétben a két főátlós esettel.

Ettől függetlenül az állítás igaz, azaz mindig levehető 8 bábu, hogy minden sorban és oszlopban 1 darab álljon.

Annyit segítek, hogy valószínűleg azt kell hozzá alkalmazni, amit most tanulsz.

Az első válasz nagyrészt helyes. Annyiban téved, hogy oszlop- és sorcserékkel csak az egyik átlóba tudunk biztosan figurákat mozgatni, a maradék 8 szétszórtan lesz.

Egy másik megoldási ötlet: vegyünk el egy tetszőleges figurát a tábláról a 16 közül. Ezzel a következő levehető bábu már kényszerítve van 2 lehetőségre, ugyanis a levett bábu két “párját” már nem vehetjük le, tehát ezeknek a párja mindenképpen lekerül. Persze ez a két kényszer eshet egybe. Gondolod végig, hogy hova vezethet és hova nem, ha ezt a kényszert követjük végig, ameddig csak lehet.

A sakktábla egy 8+8-as páros gráf szomszédsági mátrixa, amelyben minden csúcs 2 fokú. Azt kell belátni, hogy van a gráfban teljes párosítás.

Pl vagy úgy csinálod, ahogy Baluba írja, hogy a gráf szétesik diszjunkt körökre, vagy belátod, hogy teljesül a Kőnig-Hall feltétel. Vagy akárhogy máshogy.