How many days for hunting?

Question

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]

Answer 1

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.

Answer 2

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

Answer 3

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