Tag Info

Hot answers tagged

3

Some HINTS: In the first problem you can use induction on $n$. Let $d_1\le d_2\le\ldots\le d_n$ be a sequence of positive integers such that $$\sum_{i=1}^nd_i=2n-2\;.$$ First note that if $\sum_{i=1}^nd_i=2n-2$, then $d_1=1$, and $\sum_{i=2}^nd_i=2n-3$. And $2(n-1)>2n-3$, so we must also have $d_2=1$ and hence $\sum_{i=3}^nd_i=2n-4$. We now have $n-2$ ...


2

Your binary remainder is wrong. 1000111110 -------------- 10011)10101010100000 10011 ----- 100101 10011 ------ 100100 10011 ------ 100010 10011 ----- 11110 10011 ...


1

$$ \begin{align*} 10101010100000 -10011000000000&=10010100000\\ 10010100000 - 1001100000 &= 1001000000\\ 1001000000 - 100110000 &= 100010000\\ 100010000 - 10011000 &= 1111000\\ 1111000 - 1001100 &= 101100\\ 101100 - 100110 &= 110 \end{align*} $$ The remainder is 6.


1

It looks like you are doing $10_2 - 1_2 = 1_2$ Remember what the positional notation means in base $2$: Each place is twice the previous one. Expressedin base $10$, this is $2-1=1$. When you do $$\begin {align}10_2&\\ \underline{-\quad1_2}&\\ 1_2&\end {align}$$ you recognize that the $1$ in the twos place in the top line represents two in the ...


1

Are you familiar with the definitions of reflexive, symmetric and transitive relations? A reflexive relation is a binary relation on a set for which every element is related to itself. As you can clearly see $(0,0),(1,1)$ etc. are not contained in your relation, so it is not reflexive. A relation is symmetric if $aRb \implies bRa$. Once again, ...


1

Checking is easy: If $$x=0.{\bf q}{\bf p}{\bf p}{\bf p}{\bf p}\ldots\ ,\tag{1}$$ where the preperiod ${\bf q}$ and the period ${\bf p}$ are binary strings of length $r$ and $s$, respectively, then $$2^rx={\bf q}.{\bf p}{\bf p}{\bf p}{\bf p}\ldots$$ and consequently $$(2^r-1)x={\bf q}.{\bf p}-0.{\bf q}\ .$$ It follows that $$x={{\bf q}.{\bf p}-0.{\bf q}\over ...


1

It is natural to consider (and analyze) the Collatz map not as an operation on numbers but on strings. Most obvious candidates are the strings representing the numbers in bases $2$, $3$, and $6$. In base $6$ the Collatz map is "shift invariant" and works like a cellular automaton; the reason being that $:2$ and $\times3$ are the same in base $6$; ...


1

The de Bruijn sequences are extremal for the property you have in mind. For a $k$-element alphabet, these are cyclic sequences of length $k^n$ such that, as you slide an $n$-long window along the sequence, you see each one of the $k^n$ $n$-long strings exactly once -- therefore the longest repeated substring has length $n-1$. (For a non-cyclic sequence, ...


1

Let $\sim$ be an equivalence relation (reflexive, symmetric, transitive) on a set $S$. The equivalence class under $\sim$ of an element $x \in S$ is the set of all $y \in S$ such that $x \sim y$. An equivalence relation will partition a set into equivalence classes; the quotient set $S/\sim$ is the set of all equivalence classes of $S$ under $\sim$. At the ...


1

The short answer to "what does this mean": To say that $x$ is related to $y$ by $R$ (also written $x \mathbin {R} y$, especially if $R$ is a symbol like "$<$") means that $(x,y) \in R$. (Well, there may be some ambiguity about whether $(x,y) \in R$ is read as "$x$ is related to $y$ by $R$" or "$y$ is related to $x$ by $R$", but it doesn't matter in this ...


1

The binary reflected Gray code is defined inductively: The binary reflected Gray code of length $0$ is $G^0 = ()$ (empty list). Let $G^n = (g^n_1, \ldots, g^n_{2^n})$ be the binary reflected Gray code of length $n$. Then the binary reflected Gray code of length $n+1$ is $$G^{n+1} = (0g^n_1, \ldots, 0g^n_{2^n}, 1g^n_{2^n}, \ldots, 1g^n_1).$$ For example: ...


1

One intuitive approach to this problem is to let $B_n$ be the number of strings of length $n$ that contain 111, and let $A_{n,k}$ be the number of strings of length $n$ that do NOT contain 111 which end with $k$ 1's ($k=0,1,2$). Then obviously, $$B_n = 2*B_{n-1} + A_{n-1,2}$$ $$A_{n,0} = A_{n-1,0} + A_{n-1,1} + A_{n-1,2}$$ $$A_{n,1} = A_{n-1,0}$$ $$A_{n,2} ...


1

Let $1_n$ be the set of such strings of length $n$ ending in $1$. Similarly let $0_n$ be the set of such strings ending in $0$. Then we have $$ \begin{align} 1_{n+1}&=\{x\parallel 1\mid x\in 1_n\cup 0_n\}\\ 0_{n+1}&=\{x\parallel 0\mid x\in 1_n\} \end{align} $$ Define $A_n=|1_n|$ and $B_n=|0_n|$. Then we have from above $$ \begin{align} ...



Only top voted, non community-wiki answers of a minimum length are eligible