Thursday, October 2, 2008

Problem Solving

At least once in a while I should post something with some personal interest. It is strange how reading something which is happening in someones life that you don't even know can be entertaining. I suppose what is on my mind at the moment is problem solving.

There is an undergraduate problem solving contest here at the U where a new problem is posed once a month during the school year. People submit solutions at the end of the month and are assigned points based on their solutions to the problems 3 points for a correct one and +e points if you win. I have found that I can solve a significant fraction of the problems but that also sometimes I spend dozens of hours working on a problem only to be unable to solve it. This last problem really made me angry when I found out how it admits a really simple solution and even one that I sort of thought about before. you have a 7x7 checkerboard with a black square in the corner. What single tiles can you remove in order to make the board tileable by 2x1 dominoes? The answer is you can remove any black square and not any red squares. I worked on the problem for hours and made it more and more complicated... but I couldn't figure out how to prove that removing a red tile made the board untileable. The amazingly simple thing to realize is that there is one more black square to begin with on the board and every dominoe covers a red and black square thus removing a red square leaves the board untilable since it leaves the number of black and red squares unequal. An even more elegant solution deals with finding even paths on the board which gives you both the black and the red tile cases in one go. The really infuriating thing is that I considered both the fact that every dominoe covers a red and a black tile and the fact that the existence of eulerian paths on the dual graph of the board is related to the tiling.... and yet I didn't solve the damn thing. I guess I am really just not capable of doing personal happenings rants. I just get caught up in the details of whatever little abstract thing I mention. I'll do better next time.

No comments: