10
$\begingroup$

There are $10$ hunters who are planning to go hunting in as a few days as possible. Every single day, they choose a group of people or a person to go for hunting, the rest is resting in the camp area. Next day, they choose again who is/are going to go for hunting etc. But they want to make sure of three things at the end of the hunting;

  • Any hunter would go for hunting without any other hunter in the group for at least one day. For example, if hunter $A$ goes with hunter $B$ for a day, hunter $A$ should go for a hunting at least one more time without hunter $B$, same goes for hunter $B$ of course etc.
  • As a group of 10 people, they want to go hunting as few days as possible.
  • Every hunter needs to go for hunting at least for a day.

So what is the least number of days is needed for hunters to complete hunting with the condition above?

If this question was asked for 3 people, the answer would be $3$ such as below;

[a,-,-]

[-,b,-]

[-,-,c]

$\endgroup$
  • $\begingroup$ can you define the groups? because in this way the hunter can also go with the group of 9 people and one will be only resting? atleast put limit on it. $\endgroup$ – Sayed Mohd Ali Sep 3 at 14:13
  • $\begingroup$ This problem is an application of Sperner Theorem for antichains. $\endgroup$ – P.-S. Park Sep 10 at 21:41
9
$\begingroup$

Extending MKBakker's answer, answering the unasked generic case of N hunters...

For $k > 2$,

You can arrange for $N = {k \choose 2}$ hunters to hunt in $k$ days. To do this, simply enumerate all the $k \choose 2$ combinations of 2 days. Assign each combination to a hunter, and that hunter hunts on those two days. Thus, each combination of 2 days has exactly one hunter who hunts on both days. Since each hunter hunts more than once, and no combination of 2 days has more than one hunter who hunts both, the desired criteria must be met.

For $k \leq 2$,

It is more efficient to just have each hunter hunt once, allowing $k$ hunters to hunt in $k$ days. This is trivially proven using brute force to examine all the non-empty subsets of a set of 1 or 2 hunters.

In the case of 10 hunters,

Since $10 = {5 \choose 2}$, it is possible to have 10 hunters hunt in 5 days. MBakker's answer provides such a combination; each of the 10 combinations of 2 of the 5 days is assigned to one of the hunters.

Proof that this is the maximum number of hunters who can hunt in $k$ days:

There are only $k\choose 2$ combinations of 2 days out of $k$. By the pigeon-hole principle, if we added another hunter, then either: 1) the extra hunter would hunt less than 2 times during the $k$ days, or 2) there would be a combination of 2 days when more than one hunter hunted both. The only way to meet the criteria would be to add an extra day.

$\endgroup$
  • $\begingroup$ I was expecting this kind of of answer, since yours explain it better, I will choose yours. $\endgroup$ – Oray Sep 4 at 7:22
11
$\begingroup$

The minimum number of groups I got so far is:

5

Consisting of:

[0,1,2,6]
[0,3,4,5]
[1,3,7,9]
[2,4,8,9]
[5,6,7,8]

NB: Compared to my initial answer, I changed 9->8,8->7,7->6,6->9 for clarity on the example below.

I got there by creating sequences of length N. The sequence on its own will be (part of) a group, and the transpose of that sequence will be divided over other groups. Creating the following set of blocks:

enter image description here
The blocks of [0,1,2] are the starting point. When trying to add the blocks of [3,4,5], we notice we need at least a 5th group, otherwise at least one item of [0,1,2] will be in the same group as an item of [3,4,5] twice. Adding [6,7,8] follows the same rule as [3,4,5]. The we just have the [9]'s left, which can be added without any problem.

$\endgroup$
  • $\begingroup$ since @user3294068 explaination is more general, I choose his answer as best answer. but you found it first though :) $\endgroup$ – Oray Sep 4 at 7:31
3
$\begingroup$

I think the least number of days is

$7$ days

Solution

Label the hunters $a,b,c,d,e,f,g,h,i,j$. Then, schedule as follows:

Day 1 $a,b,c$ hunt
Day 2 $d,e,f$ hunt
Day 3 $g,h,i$ hunt
Day 4 $a,d,g$ hunt
Day 5 $b,e,h$ hunt
Day 6 $c,f,i$ hunt
Day 7 $j$ hunts alone

$\endgroup$

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.