Jiiri and Mari both wish to tile an n×n chessboard with cards shown in the picture (each card covers exactly one square). Jiiri wants that for each two cards that have a common edge, the neighbouring parts are of different color, and Mari wants that the neighbouring parts are always of the same color. How many possibilities does Jiiri have to tile the chessboard and how many possibilities does Mari have?
Problem
Source: 2003 Estonia National Olympiad Final Round grade 12 p1
Tags: Tiling, combinatorics, Chessboard, Coloring