# Tag Info

Accepted

### Upper bound of of fib(n+2)

So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right? In this case, ...
• 1,097

### Upper bound of of fib(n+2)

Lee Gao's answer is excellent. Here is a different account. Consider the following automaton: This is an unambiguous finite automaton (UFA) without $\epsilon$ transitions: an NFA such that each word ...
• 278k

### Upper bound of of fib(n+2)

@Lee Gao's is too complex (I haven't even read the whole thing), here is a simplistic approach: Let f(n) be all desired strings out of which let a(n) be strings that end at a and b(n) be strings that ...
• 173
Accepted

### Finding the hidden treasure

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for ...
• 278k
Accepted

### How to find sets of polynomially bounded numbers whose subset sums are different?

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer ...
• 39k

### Find an upper bound for a Linear Recurrence

Finding a good analytic characterization of $n(N)$ is tricky. Let's first consider the relaxation where $N = \frac{n}{\log n}$ without the flooring restriction. Here's a somewhat nonintuitive ...
• 1,097