Breain teasers

Here are two interesting problems I came across recently. Take my words; they are worth giving a try. You might not come up with a correct answer quickly. The key is to keep on trying and never to give up. Providing this sort of exercises to the brain from time to time is a very good practice particularly to fight against decline of thinking power with aging.

(1) The problem of circles

I read this problem in a web site. It is really interesting. The challenge is to find the maximum number of closed regions that can be formed by overlapping a given number of equal sized circles. Each region that counts must fall within at least one circle. The answer for the case with two circles is obvious; we can form 3 regions. It doesn't even deserve a pictorial illustration. 3 circles is also a pretty simple case. It is shown in the picture in the beginning of the article. The result is 7 regions. What about the case with 4 circles? Now the problem is getting more challenging. However, I guess anyone with average thinking ability can come up with the answer after few minutes of brainstorming. The answer is illustrated below.

What we have done is placing the forth circle between the 3 circles in the orientation for the previous case. The result is 13 regions. However, there's a little problem. How can one be certain that this is the orientation yielding the maximum number of regions? 13 is the correct answer in this case, but how can we prove that it is?

We clearly observe that the difficulty of the problem problem grows exponentially with the number of circles. Furthermore we do not have a proof even if we come up with a decent solution. The issue is that the ad hoc thinking we used for the simple cases just do not work when the problem gets more complex. Ad hoc methods generally do not generate proofs either. The problem asks us to come out of the frame and think smarter to arrive at an enlightening solution. Can we do it? Yes, it is possible. All one needs to do is to defeat the inertia to engage in thinking and continue with willpower. 

Here we go...My challenge is: What is the maximum number of regions that can be formed by overlapping 10 circles?

(2) The problem of Aluminium plates

This is a practical engineering problem. One of my friends who works in an Aluminium factory came up with this question regarding a problem encountered in their day to day operations. They get fairly big square shaped Aluminium plates and are asked to cut rectangular pieces of various sizes out of them. The requests come at different times so they do not know the sizes of all the pieces they need to cut from a single square. When they get a request for an Aluminium piece, they cut it from one of many available half cut Aluminium squares by guessing the best one to cut from. When few pieces are cut from a square it might look like this.

At a given time our friends have many plates with this type of shapes. The pieces are always cut with parallel edges to that of the initial square. Therefore there are no slant cuts. After a square is consumed to a level that is no more usable (no pieces with a given minimum size can be cut from the remainder) they add it to a recycling phase where those remainders are melted to make new squares. Understandably, this melting process is quite costly and optimum usage of an Aluminium square before recycling will definitely save them a good amount of money. Therefore the problem is to come up with a systematic way (an algorithm..forget this word if you are not a computer engineer) to cut pieces from Aluminium squares in an optimal way.

We can formulate the problem like this. Given all the shapes of remaining Aluminium squares and the size of the rectangular piece to cut, how to find the best square to cut from and the best place in it to cut the piece? Remember that figuring out the optimality criteria is also a part of the solution. After all what our friends in the Aluminium factory need is to cut more pieces from squares.

I will post my analysis and solutions to these problems in a later post. Until then, happy thinking.