1
$\begingroup$

I ran into this question and I'm not really sure how to start.

we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$, we'll define $n_{w}$ as the number of times $w$ appears arround the circle.

prove that the numbers {$n_{000},n_{001},n_{010},n_{011},n_{100},n_{101},n_{110},n_{111}$} can all be more than 0 (all at once) if and only if:

$$ \sum_{w\in \{0,1\}^3}^{}{}n_{w}=100 $$ $$ n_{100}=n_{001}, n_{011}=n_{110}, n_{101}+n_{001}=n_{010}+n_{011}, n_{110}+n_{010}=n_{100}+n_{101} $$

i would get a clue and not the full answer,

Thank you very much in advance.

$\endgroup$
5
  • $\begingroup$ Odd. Unless I misunderstood the problem, 100 zeroes satisfy the second set of conditions but not the first.... $\endgroup$ – N. S. May 9 '13 at 14:32
  • $\begingroup$ I need it to answer both sets of conditions. $\endgroup$ – user76508 May 9 '13 at 14:34
  • $\begingroup$ and, it needs to be a proof, i can't use an example $\endgroup$ – user76508 May 9 '13 at 14:34
  • $\begingroup$ if and only if means that the two sets of conditions are equivalent. So if second is true, first cannot be false.... $\endgroup$ – N. S. May 9 '13 at 14:35
  • $\begingroup$ gotcha. i'll check it out $\endgroup$ – user76508 May 9 '13 at 14:36
3
$\begingroup$

I think that you need to add the assumption that $w$ is not constant, i.e., that it contains at least one $1$ and at least one $0$. For a HINT, note that $n_{101}+n_{001}$ is the number of subsequences of length $3$ that end with $01$, while $n_{010}+n_{011}$ is the number that begin with $01$. The other equalities are similar, even the first two: $n_{100}=n_{001}$ is equivalent to $n_{000}+n_{100}=n_{000}+n_{001}$.

You’ll also need to show that if one of these four quantities is non-zero, they all are, which isn’t too hard.

$\endgroup$
3
  • $\begingroup$ thank you very much, I'll try it. $\endgroup$ – user76508 May 10 '13 at 10:07
  • $\begingroup$ I'm looking at it now, and I see a problem. n101+n001 always equals n010+n011. $\endgroup$ – user76508 May 10 '13 at 10:12
  • $\begingroup$ @user76508: How is that a problem? That’s what should happen. $\endgroup$ – Brian M. Scott May 10 '13 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.