Well, first we can notice that we can think about the table being covered with dominos. Each possible domino we can put on the table ends up increasing our final sum by one, since one of the two squares will be completed after the other and will count the first one as an adjacent completed square. All it is left to do now is to count how many different dominos can we put on an m*n table. By watching the top left corner of any domino we can notice that it can go to (m-1)n (if dominos are vertical) + m(n-1) (that's if dominos are horizontal)=2mn-m-n possible positions. Hence, not only that we know that the sum is constant, but we know it's exact value: 2mn-m-n.
1838 Views
See similar Oxbridge Preparation Mentoring tutors