Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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