Combinatorics + Diwali

Question

During the festival of Diwali, as a popular custom, people distribute sweets among their friends and neighbor. Many a times, because of growing number of sweet boxes to distribute, people generally gift the boxes they receive to some other person :)

This is beneficial in two ways, first, economically, secondly this practice discourages the stocking of sweet boxes which may get rotten over the time because of non-consumption. Now let us assume there are n families who are celebrating diwali and are practicing the above-mentioned custom of distributing sweet boxes.

What minimum amount of sweet boxes (in total) will suffice the distribution among them, such that each of them gift sweet boxes to every other family, and are left with at least one sweet box ?

Answer 1

Hint: "Everyone is left with at least one box." The answer lies within your question.

Answer 2

Each family needs to buy only 1 box and in total n boxes with each family buying one box is required. They would be giving this box to another family and ,as per the conditions mentioned in your question , would be also be getting one box in return . They can then pass this on and get another box in return . So it would be like a passing game of n sweet boxes among n families with each family having bought one sweet box.

Answer 3

I'm not entirely sure what the rules are, but the following may suffice:

Put all the families in a circle, in some arbitrary order. Each has purchased one box. First, they each gift to the next family along the circle (clockwise, say). Second, they each re-gift what they just received to the family two next along the circle. Third, they each re-gift to the family three next along the circle. And so on till the (n - 1)-th stage completes, and each family has gifted to each other family, each now left with precisely one box.

So, you see, we can get away with just n boxes, as others have noted, if this sort of thing is allowed.

Answer 4

Say there are $n=4$ families following this practice during Diwali, represented by the set $\{1,2,3,4\}$. As the question already mentions, each family must be left with atleast one gift, so the lower bound on the number of gifts is $n$.

The list of all giftings are -

$\\(1,2),(1,3),(1,4)\\ (2,3),(2,4)\\ (3,4)\\ $

Family-$1$ buys $4$ gifts and distributes $3$, Family-$2$ receives $3$ gifts and distributes $2$, Family-$3$ receives $2$ gifts and distributes $1$. Every family has gifted every other family. The total number of giftings would be $n\choose2$.