You have an unlimited supply of 2 types of coins(coin-1 and coin-2). You are asked to build a pile of 1000 coins such that the number of coins between any two coin-2 is not equal to five. So what is the maximum number of coin-2 that can be included in the pile?
i know permutation and combination bit well but this question seems different and unique to me, how to tackle such problem? please help, thank you.
Evaluate the pile from bottom to top and list all the locations of coin-2: $\{x_{1},…,x_{m}\}$.
Say that there are no coin-2 pair with five coins between them. Then there are no $i<j$ that satisfy $x_{i}+6=x_{j}$ because otherwise there will be five coins between coin number $i$ and coin number $j$. Consequently, $\{x_{1},…,x_{m}\}$ and $\{x_{1}+6,…,x_{m}+6\}$ are $2m$ distinct integers between $1$ and $1006$. This give us an upper bound for $m$; $2m\leq1006\to m\leq 503$
However, $503$ is not the answer. Notice that $\{x_{1},…,x_{m}\}$ and $\{x_{1}+6,…,x_{m}+6\}$ are identical in modulo $6$ so if we write these in modulo $6$ we will get even number of each of $0,1,2,3,4,5$. Write $1$ to $1006$ in modulo $6$ and you’ll see that $1,2,3,4$ appear $168$ times while $5,0$ appear $167$ times. Means at least one number with $0$ in modulo $6$ and one number with $5$ in modulo $6$ will not appear. Therefore the upper bound need to be revised: $2m\leq 1006-2\to m\leq 502$
Turn out, stacking $6$ coin-2 and $6$ coin-1 alternatingly gives us the desired pile and a total of $502$ coin-2.