Question of difficult matrix problem, minimum number of times

103 Views Asked by At

There is a $n$×$n$ matrix $A_n$. All entries are $0$ at first.

$\left( \begin{array}{ccc} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right) $

The example of $5$×$5$ matrix at an initial condition.

Next, you choose m numbers $b_1, b_2, .. b_m$. $(1 \leq b_k \leq n)$ Then, entries $a(i,j)$ will come to $1$. $(i,j = b_1, b_2, .. , b_m)$

$\left( \begin{array}{ccc} 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right) $

The example when $n = 5 ,m = 3$ and you choose $b_1 = 1, b_2 = 2, b_3 = 4$.

I want to make all entries into $1$ in the minimum number of times for $n, m$. I call this minimum times $F(n,m)$. Please solve for $F(n,m)$.

Examples: $F(n,n) = 1, F(n,2) = n(n-1)/2, F(4,3)=3, F(7,3)=7$

I know $ \lceil n(n-1)/m(m-1) \rceil \le F(n,m)$