# Tag Info

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