Counting question / solution verification

Question

In a $100$ day period, each of six friends goes swimming on exactly $75$ days. There are $n$ days on which at least $5$ friends swim. Find the largest and smallest possible values of $n$.

My attempt at a solution:

The largest value of $n$ occurs when exactly $5$ friends swim on as many days as possible.

We can achieve this by rotating the days on which each friend doesn't swim. If $A,B,C,D,E,F$ are the friends, then

• $A$ doesn't swim on days $1,7,13,19,\ldots,85,91-100$
• $B$ doesn't swim on days $2,8,\ldots,86,91-100$
• $C$ doesn't swim on days $3,9,\ldots,87,91-100$
• $D$ doesn't swim on $4,10,\ldots,88,91-100$
• $E$ doesn't swim on $5,11,\ldots,89,91-100$
• $F$ doesn't swim on $6,12,\ldots,84,90,91-100$

Therefore, the largest possible value of $n$ is $90$.

The smallest possible value of $n$ occurs when exactly $4$ friends swim on as many days as possible.

We can rotate these days as follows: $A$ doesn't swim on days $1,2$; $B$ doesn't swim on days $2,3$; $C$ doesn't swim on days $3,4$; $D$ doesn't swim on days $4,5$; $E$ doesn't swim on days $5,6$; $F$ doesn't swim on days $6,7$; $A$ doesn't swim on days $7,8;\ldots$

Continuing in this way, it is possible to ensure that exactly four people are swimming on days $1-75$ and all six people are swimming on days $76-100$.

Therefore, the minimum value of $n$ is $25$.

Are these bounds correct? How could I improve my arguments?

Answer 1

There are $6 \cdot 75 = 450$ swimmer-days, so there is an obvious upper bound to the number of 5-swimmer days of $\frac{450}{5}=90$. Your schedule is a concrete example of such, so 90 days must be the maximum.

A similar argument can be made about the lower bound. There you want to maximize the number of days in which 2 or more friends are not swimming. Any schedule with a day with 3 or more friends not swimming can be potentially improved by adjusting the schedule so that day has no more than 2 friends not swimming. Any schedule with a day where exactly 5 friends are swimming can be potentially improved by having all 6 friends swim that day, so as to conserve non-swimming days. So the best theoretical schedule uses has either 4 or 6 friends swimming each day, conserving the $6\cdot25=150$ nonswimming days to maximum effect to get 75 days with 4 or fewer friends swimming. You also achieved this schedule.

Answer 2

I asked the MiniZinc constraint solver to beat your solutions:

int: periodDays = 100;
int: swimmingDays = 75;
int: noOfFriends = 6;
set of int: Days = 1..periodDays;
set of int: Friends = 1..noOfFriends;
array[Friends, Days] of var bool: swimming;
var Days: n;

constraint forall(friend in Friends) (
  swimmingDays == sum([swimming[friend, day] | day in Days])
);

constraint (
  n == sum(day in Days)(
         5 <= sum([swimming[friend, day] | friend in Friends])
       )
);

solve minimize n;

output [ show((day div 10) mod 10) | day in Days] ++
       ["\n"] ++
       [ show(day mod 10) | day in Days] ++
       ["\n"] ++
       [if fix(swimming[1,day]) then "A" else " " endif | day in Days] ++
       ["\n"] ++
       [if fix(swimming[2,day]) then "B" else " " endif | day in Days] ++
       ["\n"] ++
       [if fix(swimming[3,day]) then "C" else " " endif | day in Days] ++
       ["\n"] ++
       [if fix(swimming[4,day]) then "D" else " " endif | day in Days] ++
       ["\n"] ++
       [if fix(swimming[5,day]) then "E" else " " endif | day in Days] ++
       ["\n"] ++
       [if fix(swimming[6,day]) then "F" else " " endif | day in Days] ++
       ["\n"] ++
       [show(sum([swimming[friend,day]|friend in Friends])) | day in Days] ++
       ["\n"] ++
       ["n=" ++ show(n)] ;

The minimum n solution provided by the Gecode solver backend:

0000000001111111111222222222233333333334444444444555555555566666666667777777777888888888899999999990
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
AAAAAAAAAAAAAAAAAAAAAAAAA                         AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBB                         BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC                         CCCCCCCCCCCCCCCCCCCCCCCCC
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD                         DDDDDDDDDDDDDDDDDDDDDDDDD
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE                         
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF                         
6666666666666666666666666444444444444444444444444444444444444444444444444444444444444444444444444444
n=25

The maximum n solution found by the G12 fd backend:

0000000001111111111222222222233333333334444444444555555555566666666667777777777888888888899999999990
1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA               AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA          AAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB               BBBBBBBBBBBBBBBBBBB          BBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC    CCCCCCCCCCCCCCC                     
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD                         DDDDDDDDDDD
               EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE          EEEEEEEEEEE
FFFFFFFFFFFFFFF               FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF          FFFFFFFFFFF
5555555555555555555555555555555555555555555555555555555555555555555555555555555000000000055555555555
n=90

Interestingly, none of the backends I tried succeeded in finding both solutions.