How many days for hunting?

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]

• 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. – Sayed Mohd Ali Sep 3 at 14:13
• This problem is an application of Sperner Theorem for antichains. – P.-S. Park Sep 10 at 21:41

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.

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

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: 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 's left, which can be added without any problem.

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

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