The problem,

There are $1024$ people. Each person is having $1024$ similar fruits. No two persons are having same kind of fruits. Find the minimum number of transactions required so that each-person is having $1024$ different kinds offruits. Note that a single transaction is defined as exchange of any number of fruits between any two persons.

The suggested solution is as follows:

If $2$ people having $2$ fruits each then only one transaction will be required. If $4$ people having $4$ fruits each then $2 \times 2$ transactions are required. $8$ people having $8$ fruits each then $3 \times 4$ transactions will be required.Like this for $1024$ we would need a minimum of $10 \times 2^9 = 5120$

But I am not sure that I can fully construe this.Lets denote the fruits by alphabets,For two people initially we have

aa  bb

Hence,only one exchange of 'a' with 'b',will make it

ab  ab

But when when we have four people then,

aaaa bbbb cccc dddd

I tried but I could not make this to

abcd abcd abcd abcd 

in only $4$ steps,could anybody show me how to do this in $4$ steps?


In the first round do the transactions:

aaaa + bbbb $\to$ aabb + aabb (trading aa for bb)

cccc + dddd $\to$ ccdd + ccdd (trading cc for dd)

After this in the second round two pairs of people can do the transaction

aabb + ccdd $\to$ abcd +abcd (trading ab for cd)

Four transactions total. Apply a bit of recursive thinking.


aaaa bbbb cccc dddd ==> 1st and 2nd person exchanging two fruits

aabb aabb cccc dddd ==> 3rd and 4th person exchanging two fruits

aabb aabb ccdd ccdd ==> Person 1 gives an a and a b to person 3, and vice versa

abcd aabb abcd ccdd ==> Similar for 2 and 4

abcd abcd abcd abcd.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.