Pages

Monday, October 25, 2010

Number of black cells

Each cell on an $n \times n$ checkerboard is to be painted black or white.

How many ways are there to paint the board such that each column and each row contains an even number of black cells?

How many ways are there to paint it such that each column and row contains an odd number of black cells?

1 comment:

  1. Yang pertama: Warnai (n-1)(n-1) kotak kecuali baris terakhir dan kolom terakhir secara sebarang, ada 2^(n^2-2n+1) cara. (n-1) kotak di kolom terakhir kecuali kotak terakhir ditentukan secara tunggal dari kotak-kotak yang sudah diwarnai, begitu pula (n-1) kotak di baris terakhir kecuali kotak terakhir. Sekarang cukup dibuktikan bahwa n-1 kotak di kolom terakhir (K) dan n-1 kotak di baris terakhir (B) menentukan warna yang sama untuk kotak terakhir. Ini jelas benar karena paritas kotak hitam di K sama dengan paritas kotak hitam di kotak (n-1)x(n-1) yang sama juga dengan paritas kotak hitam di B.

    ReplyDelete