Tag Info

Hot answers tagged

5

After $N=2T$ toggles, the average value of any bit is $$\sum_{k=0}^{T-1}\frac{(W-1)^{2T-2k-1}}{W^{2T}}{2T\choose 2k+1}\\ =\frac12-\frac12\left(\frac{W-2}W\right)^{2T}$$ and the second term is roughly $\frac12e^{-2N/W}$. Use enough toggles to make that difference small enough.


4

From right to left, the binary place values (mod 10) are $1, 2, 4, 8, 6, 2, 4, 8, 6, \dots$. You can add the reduced (mod 10) place values with $1$s in them, and then mod your answer by ten. In your example, $11001$, you would add $8 + 6 + 0 + 0 + 1=15\equiv 5 \pmod{10}$.


3

Hint Think of the binary number $k=b_{n}b_{n-1}...b_{2}b_{1}b_{0}$ as $k=b_{0}(1)+b_{1}(2)+b_{2}(4)+b_{3}(8)+b_{4}(16)+b_{5}(32)+...$ If $b_{0}$ and $b_{1}$ are both equal to zero, then every other term in that sum is divisible by $4$.


3

The thing you've asked to show isn't too hard: \begin{align} \sum_{i=0}^{n-2} \left(2^{-i+n-2} + 2^i\right) &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \sum_{i=0}^{n-2}\left(2^i\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(1 + 2 + \ldots + 2^{n-2}\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(2^{n-1} - ...


2

Mathematically, possibly the most "pure" numbering system is the system consisting of zero and the successor function $S$. In this system, instead of writing the first several non-negative integers as $0, 1,2,3,4,5,6$ and so forth, we write $$ 0,$$ $$ S(0),$$ $$ S(S(0)),$$ $$ S(S(S(0))),$$ $$ S(S(S(S(0)))),$$ $$ S(S(S(S(S(0))))),$$ and so forth. It's ...


1

EDIT: This answer is wrong, as I neglected that the contribution of $63780$ to the interval sum is $1$, not $0$. EDIT: This answer assumes we consider all numbers in the range $0 \dots 10^{100} - 1$, i.e. including $42$. The last digit is $0$. Since we're only interested in the last digit, we can do everything mod $10$. Consider any interval of numbers ...


1

Nice statement and I agree that your proof is valid. I'll flesh it out a little bit. I'll denote that language you defined above as $\{0, 1\}^*$. This language must have a countable number of elements since it is the countable union of finite sets. Now suppose every real number can be encoded uniquely as an element of this language. That means we have ...


1

Note that xor'ing with $2^m$ simply inverts the $m+1$-th binary digit from the right, and $\!\! \mod 2^{k+i}$ simply trunctates the binary number to the last $k+i$ binary digits. $a_1\times 2^{k+i}$ ends with $k+i$ zeroes, so all the equation requires is that $2^m$ ends with $k+i$ zeroes as well, that is $m\ge k+i$.


1

As, reversing the order, $$\sum_{i=0}^{n-2}2^{i-n+2}=\sum_{i=0}^{n-2}2^i$$ the global sum is $$2(2^{n-1}-1).$$


1

Applying the proof of the geometric series to this particular case: $$ MaxInt(n) = S(n) = \sum_{i=0}^{n-2} 2^i = 2^0 + 2^1 ... + 2^{n-3} + 2^{n-2} $$ Adding up each term in the series: $$ 2S(n) = (2^0 + 2^0) + (2^1 + 2^1) ... + (2^{n-3} + 2^{n-3}) + (2^{n-2} + 2^{n-2}) $$ Simplifying: $$ 2S(n) = 2^1 + 2^2 ... + (2 \cdot \frac{2^{n}}{2^3}) + (2 \cdot ...


1

$$\large\begin{align} \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i &=\sum_{\begin{matrix}j\ +\ k\ =\ n-2\\ 0\;\le\; j,\ k\;\le\; n-2\end{matrix}}2^j+2^k\\\\ &=2\sum_{r=0}^{n-2}2^r\\ &=\sum_{r=1}^{n-1}2^r\\ &=\sum_{r=1}^{n-1}2^{r+1}-2^r\\ &=2^n-2\qquad\text{by telescoping}\quad \blacksquare \end{align}$$


1

First notice that for any $m$, $\sum_{i=0}^{m-1} 2^i = 2^m-1$. To see this (and really this is the geometric series proof applied to your situation), let $$S=\sum_{i=0}^{m-1} 2^i=1+2+4+8+\cdots+2^{m-1}.$$ Then \begin{eqnarray*} 2S&=&2+4+8+\cdots+2^{m-1}+2^m\\ &=& (-1+1)+2+4+\cdots+2^{m-1}+2^m\\&=& -1+(1+2+4+\cdots+2^{m-1})+2^m\\ ...


1

If you know the product theorem for exponential generating functions, the result is quite understandable. I will slightly paraphrase the version presented in Miklós Bóna, Introduction to Enumerative Combinatorics: Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on ...


1

Starting with $N$ zero bits and performing $F$ flips. Let's look at a single bit. There are $(N-1)^{F-k}\binom{N}{k}$ ways that our bit can be flipped $k$ times. There are $N^F$ ways the random choices can go, so define $p_k$: $$p_k = \frac{(N-1)^{F-k}}{N^F}\binom{N}{k}$$ The generating function $G(x)$ for the number of flips is: $$G(x) = \sum_k p_kx^k ...


1

Whatever the answer is, it's definitely asymptotically much less than $n/2$. For example, suppose you build a string of a single 0, followed by 2 1's, followed by 3 0's, followed by 4 1's, etc. Then the maximal palindrome substring length will be $O(\sqrt{n})$. So the answer is definitely less than or equal to $c \sqrt{n}$ for some universal constant $c$.



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