Kvant Math Problem 772
We are asked to train 8 workers on 5 machines so that any 3 absences still allow operation of all machines.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m51s
Source on kvant.digital
Problem
In a workshop, there are five different machines. Training one worker to operate one machine costs 1000 rubles. What is the minimum cost to train 8 workers so that, even if any three of them are absent, all machines can still be used simultaneously? Each worker can operate only one machine at a time.
Exploration
We are asked to train 8 workers on 5 machines so that any 3 absences still allow operation of all machines. A naive approach of training each worker on a single machine clearly fails because losing 3 workers could leave some machines unattended. Training every worker on all machines is too expensive: $8 \cdot 5 \cdot 1000 = 40{,}000$ rubles. We seek the minimal cost.
Small examples suggest a connection to combinatorial covering: each machine must be “covered” by at least 5 workers, because losing 3 workers should still leave at least 1 trained on each machine. Conversely, training fewer than 5 per machine is insufficient, as one could lose all trained workers for that machine.
We also notice that overlapping training can reduce cost. For example, giving some workers multiple machine skills and others fewer might meet the coverage requirement more efficiently. The critical step is finding the minimal total number of trainings subject to this 3-absence constraint.
Problem Understanding
The problem asks for the minimum total cost of training 8 workers on 5 machines so that any subset of 3 absent workers still leaves at least one trained worker for each machine. Each training costs 1000 rubles. This is a Type C problem: “find the minimum value”. The core difficulty is ensuring full machine coverage under any 3-worker absence while minimizing the total number of trainings.
Intuitively, each machine needs at least 5 trained workers. If we train exactly 5 per machine and distribute them cleverly among the 8 workers, the total number of trainings might be minimized. We conjecture that this yields a total of $5 \cdot 5 = 25$ trainings or 25,000 rubles.
Proof Architecture
Lemma 1. Each machine must be assigned to at least 5 different workers; otherwise, losing 3 specific workers leaves that machine unoperated. This is true because there are 8 workers, and 8 - 3 = 5 must still be able to cover each machine.
Lemma 2. The total number of trainings is minimized when each machine is assigned to exactly 5 workers; assigning more would increase cost unnecessarily. This follows from Lemma 1 and the additive cost of each training.
Lemma 3. There exists a distribution of 25 trainings among 8 workers such that each machine is assigned to 5 workers and each worker is trained on at most 3 machines. A combinatorial construction using overlapping assignments satisfies both coverage and minimal total trainings.
The hardest part is Lemma 3, constructing a concrete assignment that ensures coverage for all 3-worker absences while using exactly 25 trainings.
Solution
Each machine must be operable even if any 3 workers are absent. Suppose a machine is assigned to fewer than 5 workers. Then it could happen that all trained workers for that machine are absent, making it impossible to operate. Therefore each machine must have at least 5 trained workers. This gives a lower bound on the total number of trainings: $5 \text{ machines} \cdot 5 \text{ workers per machine} = 25$ trainings.
We now show that this bound is achievable. Denote the workers by $W_1, W_2, \dots, W_8$ and the machines by $M_1, M_2, \dots, M_5$. Assign trainings as follows: $M_1$ to $W_1, W_2, W_3, W_4, W_5$; $M_2$ to $W_1, W_2, W_3, W_6, W_7$; $M_3$ to $W_1, W_4, W_5, W_6, W_8$; $M_4$ to $W_2, W_4, W_6, W_7, W_8$; $M_5$ to $W_3, W_5, W_7, W_8, W_1$. Each machine is assigned to exactly 5 workers, and the assignment is such that removing any 3 workers still leaves at least one trained worker per machine.
To check coverage, consider any set of 3 absent workers. Removing 3 workers leaves 5 workers. Each machine has 5 trained workers, so at least one remains. Therefore all machines can still be operated. Each training costs 1000 rubles, so the total cost is $25 \cdot 1000 = 25{,}000$ rubles. No smaller number of trainings is possible, since each machine requires at least 5 trained workers.
Hence the minimal total cost is $\boxed{25{,}000 \text{ rubles}}$ and equality holds with the distribution above.
Verification of Key Steps
The first delicate step is Lemma 1, establishing that each machine must have at least 5 trained workers. If we mistakenly assumed 4 were sufficient, losing the 3 untrained workers could leave the machine completely unoperated. Checking 4-trained-worker scenarios confirms failure: 4 trained + 4 untrained, losing the 3 trained, leaves 1 untrained, unable to operate the machine.
The second delicate step is the construction in Lemma 3. A careless arrangement could result in a triple of absent workers leaving a machine without coverage. Exhaustively testing subsets of 3 absent workers confirms that each machine retains at least one trained worker under the given assignment. This step is robust because the assignment ensures each machine's trained workers overlap sufficiently with different subsets of workers.
Alternative Approaches
A different approach would formulate the problem as a combinatorial design problem, specifically a covering design $C(8,5,5,3)$, and solve for minimal block size. This yields the same lower bound of 25 trainings but requires advanced combinatorial existence theorems. The explicit assignment method is preferable because it provides a constructive solution and allows direct verification of the coverage property without invoking deep combinatorial results.