a) На ри­сун­ке спра­ва ввер­ху по­ка­за­но рас­по­ло­же­ние до­ми­но­шек на доске ко­то­рое не поз­во­ля­ет прой­ти из левой ниж­ней клет­ки в пра­вую верх­нюю. Дей­стви­тель­но, по­пасть в (серую) об­ласть пра­вее самой ниж­ней до­ми­нош­ки нель­зя, по­сколь­ку сна­ча­ла мы долж­ны под­нять­ся выше пер­вой до­ми­нош­ки, и тогда мы уже выше серой по­ло­сы (а вниз хо­дить нель­зя). Далее, нель­зя по­пасть в ана­ло­гич­ную серую об­ласть пра­вее сле­ду­ю­щей до­ми­нош­ки и т. д. Эта кон­струк­ция обоб­ща­ет­ся на любую доску раз­ме­ра

За­ме­ча­ние. Для упро­ще­ния до­ка­за­тель­ства можно было бы до­ба­вить ещё го­ри­зон­таль­ные до­ми­нош­ки над вер­ти­каль­ны­ми, чтобы оста­вал­ся един­ствен­ный путь по доске, упи­ра­ю­щий­ся в итоге в по­след­нюю вер­ти­каль­ную до­ми­нош­ку (ри­су­нок спра­ва внизу).

б) На­чаль­ная и ко­неч­ная клет­ки лежат на глав­ной диа­го­на­ли доски и имеют «ко­ор­ди­на­ты» и До­ка­жем, что в любую сво­бод­ную клет­ку этой диа­го­на­ли можно по­пасть.

Дей­стви­тель­но, пусть мы дошли до клет­ки Если клет­ка сво­бод­на, то хоть одна из кле­ток и не за­ня­та и через неё можно прой­ти на клет­ку

Если же клет­ка за­ня­та, то из её со­се­дей за­ня­та ровно одна клет­ка, причём по сто­ро­не, по­это­му один из двух путей из в не за­крыт.

Ответ: а) не все­гда; б) все­гда.