1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ So basically this is equal to building a string of length 1000 from A and B, so that the substring "BAAAAAB" is not present. $\endgroup$ Commented Aug 25, 2021 at 9:02
  • $\begingroup$ The approach of every even coin (only) is coin-2 is no good, since there are presumably 5 coins between positions 2 and 8. The approach of every third coin, would work but is inferior to repeating the pattern of BBBBAAAAAA. This pattern leads to 400 coins. So the problem semi-reduces to showing that 400 is maximum, or showing an example for $k > 400$ and then proving that $k$ is maximum. $\endgroup$ Commented Aug 25, 2021 at 9:32
  • $\begingroup$ @MattiP. Although I could easily be wrong, I am interpreting the problem differently than you have commented. As I see it, there must be no occurrence of BxxxxxB, where x can be A or B. $\endgroup$ Commented Aug 25, 2021 at 9:33
  • $\begingroup$ Correction to my 1st comment: bbaabbaabbaa... seems to work, so the maximum seems to be at least 500 (since 1000 is divisble by 4). $\endgroup$ Commented Aug 25, 2021 at 9:41
  • $\begingroup$ @user2661923 I got 502 as maximum $\endgroup$ Commented Aug 25, 2021 at 9:46

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ yes, I got it, bbbbbbaaaaaabbbbbbaaaaaa... works. Now, you have to prove that 502 is a maximum (if possible). $2^{1000} \approx 10^{300}$ is clearly too big to pc-computer-sanity-check. A reasonable alternative is to sanity-check the lesser case of 30 coins, since $2^{30} \approx 10^9$ should be small enough to pc-computer-sanity-check. $\endgroup$ Commented Aug 25, 2021 at 10:16
  • $\begingroup$ Check my second paragraph, I have proven that the maximum cannot be higher than $503$. If we want to have $503$, all numbers from $1$ to $1006$ must appear, try it and you’ll realize why $502$ is the max $\endgroup$ Commented Aug 25, 2021 at 10:19
  • $\begingroup$ +1 to your answer. However, I question the validity of your proof, which assumes that the optimal approach is to have blocks of consecutive coin-2's, followed by blocks of consecutive coin-1's. While I strongly suspect that this is true, it is unclear to me that you have proven it. However, it could be my shortcoming: it could be that you have actually proven it, and I am simply not grasping it. $\endgroup$ Commented Aug 25, 2021 at 10:22
  • $\begingroup$ @user2661923 I revised it, how about now? $\endgroup$ Commented Aug 25, 2021 at 10:43
  • $\begingroup$ Yes, it finally sank in, elegant proof. $\endgroup$ Commented Aug 25, 2021 at 10:49

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.