

Rizwan Ansary
Assignment 4
The Architecture of Complexity
1. Name the two most important things/concepts which you learned from the reading thechapter "The Architecture of Complexity"
1.1. give a one paragraph explanation why you consider these concepts important
1.2. arethe concepts relevant to your work, to your interest, .... – if yes, why?
I found it very interesting how it is possible to build a strong empire/political system by strengthening subunits at the grassroots level. I think it is especially relevant in the context of the efforts that are currently underway in the same vein in Pakistan, the country I originate from.
The Mutilated "8x8" Matrix
1. try to find an answer to this problem! ‡ document briefly your thinking — including all theimportant intermediate steps and failing attempts (i.e., create a "thinkaloud protocol")
Based on my intuition, it was quie evident to me that it the problem could not be solved. However, the way these puzzles are, I did want to work out a solution. Since the dominoes were occupying two cells, I reduced the board to a 8X4 grid (32 cells) such that each domino now occupied only one cell. That representation certainly did not help at all since it did not allow me to represent the excluded corner cells. I reverted to an 8x8 representation and tried laying out the dominoes in horizontal and vertical direction. That helped me better understand why it was not possibe to fit the 32 pieces. I asked a friend to "collaborate" with me in trying to solve the problem. He is not taking this class. It turned out that he had already seen it before (unlike myself) and told me that it was unsolvable. In search of a mathematically satisfying proof I went to Google and read a paper "A Simple Formalization and Proof for the Mutilated Chess Board" by Lawrence C. Paulson. It showed a new approach of coloring the cells and then seeing that there are not equal number of black and white squares.
2. which resources did you use to solve the problem?
I tried working out things in my mind in the very begining. I used various rounds of pen and paper for the 8x4 formulation. After reading the paper I used a chess board in one of my PC games.
3. which process did you use?
4. which practice (of you or others) did you use?
I am not sure what can be the difference between my answers to both of these questions so I will answer them together.
My method was mostly trial and error. In the beginning when I was not convinced of its insolvability, i thought of exhaustive search but I dropped the idea after seeing the proof. I did try to use a little bit of pattern matching. I also wondered if it is possible for dominoes to overlap somehow (useless idea). I also tried a collaborative effort by working with my friend as well as by using Google to find an answer.
5. could computers be useful to solve this problem?
Computers can be used if exhaustive search is adopted as a strategy. However, since the answer to the problem (more precisely, the reason for the lack of a solution) depends completely on the two corner squares, therefore, it does not matter how we put squares in the middle rows and what combinations do we use.
6. what have you learned solving the problem: in general and for our course?
7. what have you learned not being able to solve the problem: in general and for our course?
(i) I think it is necessary to have a clear representation to better understand the problem.
(ii) One should try out different approaches. Although in this context, this was more out of need than innovation but nonetheless, it is useful.
(iii) Different people approach the problem in different ways. It helps to collaborate.
(iv) Collaboration does not always solve the problem. Some problems require thinking deeply and visualizing alternative scenarios.
(v) Proof by contradiction is a useful tool. I would be very interested in knowing what types of problems are best suited for solving by this method.

