Kvant Math Problem 92

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m12s
Source on kvant.digital

Problem

Petya plans to spend all 90 days of the holidays in the village, strictly following this schedule: every second day (that is, every other day) he goes swimming in the lake, every third day he goes to the store for groceries, and every fifth day he solves math problems. (On the first day, Petya did all three activities and became very tired.) How many "pleasant" days will Petya have, when he only needs to go swimming, without going to the store or solving problems? How many "boring" days, when he has nothing to do at all?

Exploration

The schedule repeats with period $\operatorname{lcm}(2,3,5)=30$. Within each block of $30$ days, the same pattern of activities reappears. Since $90=3\cdot 30$, it suffices to count the desired days in one $30$ day block and then multiply by $3$.

A pleasant day is a day divisible by $2$, but not divisible by $3$ or $5$. Among the integers from $1$ to $30$, there are $15$ multiples of $2$. Some of them are also multiples of $3$ or $5$, and those must be excluded.

The dangerous point is double counting. If one subtracts the multiples of $6$ and the multiples of $10$, then the multiples of $30$ are removed twice and must be restored once.

A boring day is a day divisible by none of $2,3,5$. It is convenient to count the complement. In $30$ consecutive days, the number of days having at least one activity equals the number divisible by $2$, $3$, or $5$. Inclusion-exclusion gives that count.

To test the reasoning, examine the first $10$ days. Swimming occurs on days $2,4,6,8,10$. Pleasant days are $2,4,8$, because $6$ is also a store day and $10$ is also a problem day. Boring days are $1,7$. The counting method must reproduce these local patterns when scaled to a full period.

Problem Understanding

Petya performs three periodic activities. Swimming occurs every second day, shopping every third day, and solving problems every fifth day. Day $1$ belongs to all three schedules, so activity days are exactly the integers congruent to $1$ modulo the corresponding period, or equivalently, after shifting the numbering, the divisibility formulation above.

The problem asks for two quantities during a $90$ day interval. The first is the number of days when Petya swims and does nothing else. The second is the number of days when he does nothing at all.

This is a Type C problem, because we are asked to determine exact numerical values.

The core difficulty is organizing the overlaps correctly. The periods overlap on days divisible by several numbers simultaneously, so inclusion-exclusion is required.

The answers should be $24$ pleasant days and $24$ boring days. Since the pattern repeats every $30$ days and $90$ consists of three such periods, the problem reduces to counting within one period.

Proof Architecture

First, establish that the entire schedule repeats every $30$ days, because $30$ is the least common multiple of $2,3,5$.

Next, count pleasant days in one period. A pleasant day is divisible by $2$ but not by $3$ or $5$. Begin with all multiples of $2$, subtract multiples of $6$ and $10$, then restore multiples of $30$.

Then, count days with at least one activity in one period using inclusion-exclusion on multiples of $2$, $3$, and $5$.

Finally, subtract this number from $30$ to obtain boring days in one period, and multiply both counts by $3$ to obtain the totals for $90$ days.

The step most likely to fail under scrutiny is the inclusion-exclusion count, because overlapping multiples such as $30$ can easily be added or subtracted the wrong number of times.

Solution

The activities repeat periodically with periods $2$, $3$, and $5$. Their common repetition period equals

$$\operatorname{lcm}(2,3,5)=30.$$

Hence the pattern of activities during days $1$ through $30$ repeats identically during days $31$ through $60$ and during days $61$ through $90$.

We first count pleasant days in one $30$ day block.

A pleasant day is a swimming day that is neither a shopping day nor a problem-solving day. Thus the day number must be divisible by $2$, but not divisible by $3$ or $5$.

Among the integers from $1$ to $30$, there are

$$\frac{30}{2}=15$$

multiples of $2$.

Among these, the multiples of both $2$ and $3$ are the multiples of $6$, and there are

$$\frac{30}{6}=5$$

such days.

The multiples of both $2$ and $5$ are the multiples of $10$, and there are

$$\frac{30}{10}=3$$

such days.

The multiple of $2$, $3$, and $5$ simultaneously is the multiple of $30$, namely one day. This day was subtracted twice, so it must be added back once.

Therefore the number of pleasant days in one period equals

$$15-5-3+1=8.$$

Since the $90$ days consist of three identical periods of length $30$, the total number of pleasant days equals

$$3\cdot 8=24.$$

Now we count boring days.

A boring day is a day on which none of the three activities occurs. We first count the days on which at least one activity occurs.

In one $30$ day period, the numbers of multiples of $2$, $3$, and $5$ are

$$15,\qquad 10,\qquad 6.$$

The pairwise overlaps are the multiples of

$$6,\qquad 10,\qquad 15,$$

whose counts are

$$5,\qquad 3,\qquad 2.$$

The triple overlap consists of the multiples of $30$, whose count is

$$1.$$

By inclusion-exclusion, the number of days with at least one activity equals

$$15+10+6-5-3-2+1=22.$$

Hence the number of boring days in one $30$ day period equals

$$30-22=8.$$

Over $90$ days, the number of boring days equals

$$3\cdot 8=24.$$

Thus Petya has

$$\boxed{24}$$

pleasant days and

$$\boxed{24}$$

boring days.

Verification of Key Steps

The first delicate point is the interpretation of the schedule. Since Petya performed all three activities on day $1$, the swimming days are

$$1,3,5,\dots$$

if counted directly from the statement. Shifting every day number down by $1$ transforms this into divisibility by $2$, $3$, and $5$. Such a shift preserves all counts, because it is a bijection between the $90$ original days and the integers from $0$ to $89$.

The second delicate point is the pleasant-day count. Starting from the $15$ multiples of $2$, subtracting the $5$ multiples of $6$ and the $3$ multiples of $10$ removes the multiple of $30$ twice. Without restoring it, the result would be

$$15-5-3=7,$$

which is incorrect. Listing the pleasant days in the first $30$ day block confirms the correct count:

$$2,4,8,14,16,22,26,28.$$

There are exactly $8$ such days.

The third delicate point is the inclusion-exclusion count for active days. A careless computation might subtract the triple overlap too many times. The correct bookkeeping is

$$|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|.$$

Substituting the numerical values gives

$$15+10+6-5-3-2+1=22.$$

Hence exactly $8$ days in each period have no activity.

Alternative Approaches

Instead of inclusion-exclusion, one may classify the $30$ residue classes modulo $30$. A pleasant day corresponds to a residue divisible by $2$ but coprime to $15$. The admissible residues are

$$2,4,8,14,16,22,26,28,$$

giving $8$ pleasant days per period.

For boring days, one may use Euler's totient function. A day is boring precisely when its residue modulo $30$ is relatively prime to $30$. Since

$$\varphi(30)=30\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=8,$$

there are $8$ boring days in each period, hence $24$ in $90$ days. The inclusion-exclusion method is preferable here because it treats both questions uniformly and uses only elementary counting.