New answers tagged

2

You can do this with simple arithmetic You have 2000 elements The largest list you'll get after splitting is then 1000 elements Split again and get 500 Split again and get 250 Split again and get 125 Split again and get 63 (worst case) Split again and get 32 Split again and get 16 Split again and get 8 Then 4 Then 2 Then you compare once more And maybe ...


0

My preferred definition of a non-empty, full binary tree is: Definition 0. A pointed magma is an ordered triple $(X,\bullet,\star)$, such that $X$ is a set, $\bullet$ is an element of $X,$ and $\star$ is a function $X \times X \rightarrow X$. Definition 1. Write $F$ for the initial pointed magma. The elements of $F$ are called non-empty full binary ...


2

Here is a somewhat more general result. I will use $\oplus$ to denote logical exclusive or. Suppose we have a Boolean system of equations (equivalently, a system of linear equations in several variables $x_1,x_2,\ldots,x_n$ over $\mathbb{Z}/2\mathbb{Z}$). If the equations can be rewritten in a form where all the variables appear only as in XOR'ing pairs ...


1

The proof given by @Brian M. Scott is very pedagogical but I do think that understanding the geometric series approach is as well fundamental. It maybe difficult to obtain the adequate series, because of the interference of two "parameters": the (frequent) presence of an part of the development and its period (and, first of all, its length). In this case, ...


0

They don't. Here is a 9-dimensional associative non-commutative division algebra (over $\Bbb{Q}$): $$ D=\left\{\left(\begin{array}{ccc} x_1&\sigma(x_2)&\sigma^2(x_3)\\ 2x_3&\sigma(x_1)&\sigma^2(x_2)\\ 2x_2&2\sigma(x_3)&\sigma^2(x_1) \end{array}\right)\bigg\vert\ x_1,x_2,x_3\in E\right\}, $$ where $E=\Bbb{Q}(\cos2\pi/7)$ and $\sigma$ ...


1

It's because 0.0001100110011001... × 1010 ---------------------- 0.001100110011001... + 0.1100110011001... ---------------------- = 0.1111111111111... ---------------------- = 1.0000000000000...


4

Perhaps the simplest way to check is to verify that $1010\cdot0.0001100110011\ldots=1$. You can do this quite easily working entirely in binary notation: $$\begin{align*} 1010\cdot0.000\overline{1100}&=(1000+10)\cdot0.000\overline{1100}\\ &=1000\cdot0.000\overline{1100}+10\cdot0.000\overline{1100}\\ &=0.\overline{1100}+0.00\overline{1100}\\ ...


1

You can think of a binary sequence as a map from the natural numbers, $\mathbb N,$ to the set of values $\{0,1\}$. Whether you write express those maps, informally, as "$f(0),f(1),f(2),\dots$" or "$\dots,f(2),f(1),f(0)$" is essentially irrelevant, unless you want to mix the two notations and give them different meanings. Then you'd have to take some care ...


1

The particular family of algebras you are talking about has dimension over $\Bbb R$ a power of $2$ by construction: the Cayley-Dickson construction to be precise.


2

$2^{n-1}$ bitstrings of length $n$ start with $1$ (fix first position). Similarly, $2^{n-1}$ bitstrings of length $n$ end with $0$. We have double counted the case where $1$ and $0$ are fixed at first and last positions respectively. Number of such cases is $2^{n-2}$. Hence, $$2(2^{n-1}) - 2^{n-2} = 3\cdot 2^{n-2}$$


2

All possible bitstrings of length $n$ can be expressed as set via a regular expression: $$ L_n = (0 \mid 1)^n $$ for $n \ge 2$ we can decompose this into four disjoint subsets $$ L_n = (0|1) L_{n-2} (0|1) = (0 L_{n-2} 0) \cup (0 L_{n-2} 1) \cup (1 L_{n-2} 0) \cup (1 L_{n-2} 1) $$ The feasible words are in $$ L = (0 L_{n-2} 0) \cup (1 L_{n-2} 0) \cup (1 ...



Top 50 recent answers are included