Gold Bar Division Problem

The regular readers of this blog have by now figured out, and most correctly so, that this is going to be yet another post on Puzzle. I got this one from a friend of mine in IIT Bombay who shares my passion for brainteasers. This one appeared in one of the interview question dumps that gets circulated.

Problem Statement

So here goes the statement of the puzzle:

Amongst Bengalis Durga Puja is the biggest festival of the year and usually takes place in the month of October. Rajiv is a Bengali man, who needs money for buying gifts for his family during Durga Pujas. He plans to use his inherited 31cm gold bar as a security against taking the money. October has 31 days, Rajiv plans to give 1 cm of gold each day to the money lender and get some money from him.

However, Rajiv wants to make as few gold pieces as possible. So the obvious solution of making 31 x 1cm bars is out of question. He can rely on a scheme like giving 2 x 1cm bar on days one and two, then giving 3cm bar on day three and taking back the previous bars.

Find out the minimum number of gold bars, their individual sizes and how does Rajiv manage to use them.

Solution

The solution is rather simple. Rajiv needs to divide the gold bars into sizes 1, 2, 4, 8, 16, which adds up to 31. The scheme is very simple and best explained by a diagram of how each number from 1 to 31 will be made.

16	8	4	2	1	Value
0	0	0	0	1	1
0	0	0	1	0	2
0	0	0	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
0	0	1	1	0	6
0	0	1	1	1	7

 

Along similar lines the table will be extended till 31. The point to note here is that the numbers have a binary representation. So in problems of this nature (i.e. divide in minimum parts) where the weights of each part are non negative, the trick is to use the binary notation. The division have to be done using the binary positional numbers whose general representation is of the form 2^n for n = ( 0, 1, 2, … }.

Generally when the individual parts have two states we can safely assume binary representation. In this case the two states are: “with Rajiv”, “with money-lender”. Similarly for three states we will have to use ternary representation. I have an excellent example of usage of ternary number system, which I will be posting soon, so check back this space soon.

Trisecting an Angle

In mathematics the problem of trisecting an angle is a very interesting one. Perhaps more so, due to its seemingly impossible nature when compared to the similar problem of bisection of an angle which is easily achieved using compass and straightedge. Several literature have shown the problem to be impossible to solve using Euclidian geometric construction tools. However the problem is not impossible in nature. I have got a brilliant way of doing this using a very old technique originally attributed to Archimedes, the famous Greek mathematician.

The construction does not follow the Euclidean rules of construction which were used to prove its impossibility. However there is a bit out confusion about the rules themselves, as they are nowhere clearly mentioned in the writings of Euclid. However, most of the scholars agree on a set of rules apparent from the constructions described by Euclid. The following construction circumvents the rules, but does manage to trisect an angle accurately.

Archimedes’s method of Trisection of Angle

Let the angle to be trisected be AOB as shown in the figure. The trisected angle is PRA where 3xPRA = AOB (will be proved).

The steps of construction:

1. Using compass draw a circle with O as center. The intersection of the circle with OB is marked as P.

2. Draw like PR intersecting the circle at Q, such that QR = OP, where the point R is collinear with O and A. This is achieved by marking the distance OP on the straightedge and aligning the markings with the like OA extended backwards. Although it may seem a difficult procedure, it is actually quite easy to do.

3. Angle PRO is the trisected angle of AOB

Proof of Correctness

The proof is quite easy. I have put it down in a step by step way:

1. OP = OQ, as P and Q are points on circumference and O is the center of the circle.

2. triangle_POQ is isosceles, so angle_PQO = angle_QPO

3. angle_QOP + angle_PQO + angle_QPO = 180
   => angle_QOP = 180 – 2*angle_QPO

4. angle_RQO = 180 – angle_PQO = 180 – angle_QPO

5. triangle_RQO is also isosceles as QR = OP = QO, so angle_QOR = angle_QRO

6. angle_RQO + angle_QRO + angle_QOR = 180
   => 180 – angle_QPO + angle_QRO + angle_QOR = 180
   => angle_QRO + angle_QOR = angle_QPO
   => angle_QPO = 2*angle_QRO

7. angle_AOB + angle_POR = 180
   => angle_AOB + angle_QOP + angle_QOR = 180
   => angle_AOB + (180 – 2*angle_QPO) + angle_QRO = 180
   => angle_AOB – 2*angle_QPO + angle_QRO = 0
   => angle_AOB – 2*(2*angle_QRO) + angle_QRO = 0
   => 3*angle_QRO = angle_AOB
   => angle_QRO = (1/3) * angle_AOB

8. Hence we conclude that angle_QRO is the trisection of angle_AOB

So what is the catch?

There is no catch, the proof is indeed correct. In the beginning I have mentioned that the problem is impossible in nature, yet the proof that we showed is correct. The problem lies with the point 2 of the construction. The step required us to do a marking on the straightedge, which is not permissible in Euclidean constructions.

Bending the Rules !!

So you can actually intersect an angle after all, using the standard set of tools only. But the construction is not Euclidian. The interesting part is that this construction is quite old, but somehow this did not receive much publicity as the problem itself. Sometimes to solve a problem you have to bend the rules a bit.

Hollow Rhombus, a change in perspective

What is Hollow Rhombus?

For all those of you who do not know what exactly is Hollow Rhombus, here is a little intro for that. Hollow Rhombus is a homework problem given to students learning programming in procedural languages like BASIC, C, C++, Java etc. The problem goes like:

Write a program to input a word and print it out in the following format (for input word “HAPPY”):

HAPPY#HAPPY
HAPPY HAPPY
HAPP   APPY
HAP     PPY
HA       PY
H         Y
HA       PY
HAP     PPY
HAPP   APPY
HAPPY HAPPY
HAPPY#HAPPY

The whole point is to make students get acquainted with the various ways to use the looping statements like for, while, do-while. The problem is not a very easy one to solve for somebody who has just started with the looping constructs. It seemed to be quite an hurdle when I faced it back in std IX.

Usual Approach

The usual approaches towards solving the problem is to break up the figure into 6 parts:

First Line:
HAPPY#HAPPY

Left-Top:
HAPPY
HAPP
HAP
HA
H

Right-Top:
HAPPY
 APPY
  PPY
   PY
    Y

Left-Bottom:
HA
HAP
HAPP
HAPPY

Right-Bottom:
   PY
  PPY
 APPY
HAPPY

Last Line:
HAPPY#HAPPY

Then to code each part individually. The first and last lines are printed as it is. The top left and right parts are combined within a loop. Similarly the bottom parts are also combined within a loop (usually a for loop).

Sample Java Code for the usual approach

import java.io.* ;
public class gap
{
public static void main(String args[])throws IOException
{
 BufferedReader input = new BufferedReader( new InputStreamReader( System.in )) ;
 int j, k=0, x, y, z, Wl=0, sp=-1, st=0 ;
 String W="" ;

 System.out.print("\nENTER A WORD (MAX:19) : ") ;
 W = input.readLine() ;
 Wl = W.length() ;

 W = W+"#"+W ; // changing the string including a hash
 System.out.print("\n"+W ) ; // printing first-line

 for( j=0 ; j<Wl ; ++j )
 { // loop to generate top half
  System.out.println() ;
  sp += 2 ;// increasing space by 2
 
  for( x=0 ; x<(Wl-j) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=1 ; y<=sp ; ++y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
 
  ++st ;
 }

 st -= 2 ;
 for( k=Wl-1-1 ; k>=0 ; --k )
 { // loop to generate bottom half
  System.out.println() ;
 
  sp -= 2 ;
  for( x=0 ; x<(Wl-k) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=sp ; y>0 ; --y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
  --st ;
 }

 System.out.println("\n"+W+"\n") ; // printing last-line
}
}

Change in Perspective

The method that I have demonstrated so far to solve this looping problem is usual run-of-the-mill type. The coding is lengthy and the start and end loop values have to be carefully thought out. My brother, Bikkhan, who is in Std XII now had got this as a part of his programming assignments. When he came to me with this problem, I was quick to show him the common way of doing it by breaking it into 6 parts as demonstrated. It took him quite sometime, about 6 hours to come up with the Java code that you saw above.

I have been doing a lot of Prolog recently and I guess this is what led me to think recursively. Prolog does not have any traditional iterative statements, instead all sort of looping is achieved using recursion. To my surprise, thinking recursively had great effects on this program, and I solved it in almost no time in C++. The code length is very small compared to the former approach and I guess the logic is simpler too. So I guess its all about perspective. Here is a copy of my code in C++.

#include<iostream>
#include<string>

using namespace std;

int len;   // length of the input string

void hollow_rhombus ( string str, int n )
// str : is the string to be printed
// n   : is the step count
{
   cout<<str<<endl;

   if ( n < len )  // n==len indicates the middle line
   {
       string newstr=str;
       newstr[len-n] = newstr[len+n] = ' ';   // adding 2 new blanks
       hollow_rhombus ( newstr, n+1 );
       cout<<str<<endl;
    }
}

int main()
{
    string str;
    cin>>str;      // the word is taken as input

    len = str.length();
    str = str + "#" + str;     // first line is generated
    hollow_rhombus(str,0);     // calling the recursive function
}

Why talk about a silly looping exercise?

When I started writing this piece for my blog, my brother was the first one to ask about why did I like to share something trivial as this? After all this is another exercise in looping given to novice programmers. But what I felt was that this is a great example of how the right sort of problem analysis can lead to a simpler code, which is easier to write and read.

Win 7 RC1 Review

I was awaiting the release of Win 7 RC1 for quite some time. As a Microsoft Student Partner, I have a MSDN Premium subscription. So as a soon as it was available in MSDN (30th April), I downloaded it.

Here are my observations for the last 2 days:

• Win 7 continues to be FAST. I installed it on a AMD64 3000 with 1GB RAM and 6600GT ... worked great.

• Minor tweaks in taskbar ... check out the "task bar thumbnail overflow" feature

• Address Bar has been tweaked. In Win 7 Beta, if you browsed to a folder nested deep within the file structure the entire path could not be displayed and was truncated. In RC1, the parent folder and the current folder are always displayed.

• Jumplists tweaked a bit

• Search results are easier to view and understand. Snippets have been made longer and labeled up.

• Start Up, Shut Down and Hibernate times have become smaller ... or is it because of a clean install?

• AutoRun has been disabled by default in Flash drives

• Windows Media Player's "Lightweight Playback Mode" has been rechristened to "Now Playing Mode" which takes us less resources.

• UAC prompt now blacks out the desktop

• Couple of Psychedelic wallpapers ... this is so un-Microsoft-ish ... but I liked the design work ... keep it coming

• A friend reported some stuff about the battery meter in her laptop, but I’m not too sure about that

In summary. I see no new major feature. I was waiting for Win XP mode, but it was a disappointment not finding it in RC1. The new features are nothing but minor improvements from technical aspect, but it does beef up the usability of the OS. The improvements will enhance the UX and give a boost to the productivity.

In one line unless you are a UI geek, you would not see much improvements in Win 7 RC1 from Win 7 Beta. But if you just want to try Win 7 out after Vista or XP, this is a worthwhile download.