Interesting math problem

Question

In a far-away country, every shop is owned by one of three companies. One day, a new law was instituted to fight the monopoly. If at the end of any given day one of the companies owns more than half of all the shops and the number of shops it owns is divisible by 5, then the company must close all but 1/5 of its shops. Is it possible that three days after the law takes into effect the number of shops owned by each company decreased?

Answer 1

Assume that the companies are called $A$, $B$ and $C$ and they have initially $a$, $b$ and $c$, respectively. Assume also that they close in that order: $A$ first, then $B$ and finally $C$ (since a permutation of a solution is also a solution).

To start, forget about the condition that shops close only if their number is a multiple of $5$. In the mathematical world, you can have fractions of shops! And if you have a rational solution of the problem, you can obtain a solution that satisfies all the conditions of the problem by multiplication by the right constant.

Now, let's see what happening:

1. $A$'s shops close first: this means that $a>b+c$. Because of the new law, company $A$ has to keep only $a/5$ shops. The $b$ and $c$ shops of companies $B$ and $C$ are unaffected.

2. $B$'s shops close: this means that $b>\frac{a}{5}+c$. Because of the new law, company $B$ has to keep only $b/5$ shops. The $a/5$ and $c$ shops of companies $A$ and $C$ are unaffected.

3. $C$'s shops close: this means that $c>\frac{a}{5}+\frac{b}{5}$. Because of the new law, company $C$ has to keep only $c/5$ shops. The $a/5$ and $b/5$ shops of companies $A$ and $B$ are unaffected.

Therefore, $(a,b,c)$ should satisfy a system of linear inequalities

$$a>0, b>0, c>0, a-b-c>0, a-5b+5c<0, a+b-5c<0$$

You can find a solution by trial and error. For example, after reordering, the solutions by @vujazzman and @Hans work.

You can also visualize the solution set in space: since each inequality represents an open half-space, the solution set is the interior of a (possibly empty, possibly unbounded) polyhedron. Note that, if non-empty, it cannot be bounded since a multiple of a solution is also a solution.

---

It is not that hard to find solutions by hand. Write $c=5k$, $b=5(k+q)$ and $a=5(k+q+r)$, where $k$, $q$ and $r$ are positive integers.

The linear equations are equivalent to

$$ r>k, q+r<4k, 2q+r<3k $$

We can check for small values of $k$. For $k=1$, there is no solution. But there is one with $k=2$: $q=1$ and $r=3$. This gives $c=10$, $b=15$ and $a=30$.

Answer 2

Its possible. Take, for instance the number of owned shops at the outset to be 45, 75, 125. Then after day 1, the owned shops number 25, 45, 75. After day 2, they number 15, 25, 45, and after day 3, they number 9, 15, 25.

Answer 3

The set $\{325, 170, 100\}$ works.