Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A weird pocket calculator has a numerical display (for digits 0-9) and only two buttons, inscripted $\boxed{D+}$ and $\boxed{D-}$. The first button doubles the displayed number and then adds 1. The second button doubles the displayed number and then subtracts 1. For example, if the display shows 6, then pressing $\boxed{D+}$ produces 13; if the display shows 6 and we press $\boxed{D-}$, we get 11.

Suppose that the initially displayed number is 1, and that we then perform exactly 22 button presses. How many different numbers that can possibly result from this?

share|improve this question
up vote 19 down vote accepted

4,194,304 (222) possible results

Why such a straightforward number?

Each press doubles the number of possible sequences and no two sequences can produce the same result.

Why not?

Each press redoubles the additive/subtractive effect of all previous presses, which have already been redoubled by any intervening presses. (The first press's effect has been doubled the most often.) After that, the new +1 or -1 will only make half the difference of the immediately preceding press. This is equivalent to a 22-digit binary number.

The exact final result, $V\!$, equals a 23-bit binary number built from the intermediate results $A$,$B$,...,$U$ of button presses $a$,$b$,...,$u$, followed by one last button press, $v$.

\begin{array}{lrrllll} \rm\llap{1st} ~press& a \;{=}\;{\pm}\!\: 1 & ~A ~~\rlap{=} ~& 2(1) + a & ~~\llap{=}~~~ \phantom{ 2( 2( } 2{+}a & ~~\llap{=}~~~ 2 + ~ a \\ \rm\llap{2st} ~press& b \;{=}\;{\pm}\!\: 1 & ~B ~~\rlap{=} ~&~ 2A ~ + b & ~~\llap{=}~~~ \phantom{ 2( } 2( 2{+}a )+b & ~~\llap{=}~~~ 4 + 2 a + ~ b \\ \rm\llap{3st} ~press& c \;{=}\;{\pm}\!\: 1 & ~C ~~\rlap{=} ~&~ 2B ~ + c & ~~\llap{=}~~~ 2( 2( 2{+}a )+b)+c & ~~\llap{=}~~~ 8 + 4 a + 2 b + c \\[-1ex] \quad\vdots \\[-1ex] \rm\llap{22nd}~press& v \;{=}\;{\pm}\!\: 1 & ~V ~~\rlap{=} ~&~ 2U ~ + v & ~~\llap{=}~~~ \rlap{ 2 ( \cdots 2 ( 2{+}a ) + \cdots ) + v } \\[1ex] & & \rlap{=} ~&~ \rlap{ 2^{22} + 2^{21} a + 2^{20} b + \cdots + 2^0 v } \\[1ex] & & \rlap{=} ~&~ \rlap{ 2^{22} \bigl( \frac12 {+} \frac a2 \bigr) + \, 2^{21} \bigl( \frac12 {+} \frac b2 \bigr) + \cdots + \, 2^1 \bigl( \frac12 {+} \frac v2 \bigr) + \, 2^0 ( 1 ) } \\[1ex] & & \rlap{=} ~&~ \rlap{ 23 \;\!\textrm{-bit binary number} ~\mathit{abcdefghijklmnopqrstuv} \!\: 1_{\!\:2} } \\[-.5ex] & & &~ \rlap{ \textrm{where the}~{-}\!\textrm{1s of}~ a,b,\dots,v ~\textrm{are replaced by 0}\!\:\textrm{s} } \end{array}

Each of the 4,194,304 ($2^{22}$) possible sequences of 22 button presses has a unique combination of values for $a$,$b$,$c$,...,$v$, which produces a unique value for $V\!$ and happens to cover all of the 4,194,304 odd numbers from 1 through 8,388,607 ($2^{23}{-}1$).

Sure enough, if every press were $\boxed{D-}$ then $V \! = 000\textrm{...}001_2 = 1$, the same as doubling the original 1 and diminishing that by 1 — producing no net change — 22 times. And if every press were $\boxed{D+}$ then $V \! = 11111111111111111111111_2$, which amounts to $2{\times}1111111111111111111111_2 + 1$, the same calculation as the 22nd and last repeated step of doubling an intermediate result and adding 1 before the next step.

share|improve this answer
2  
actually, if it was 1 and you press D- you will end up with 1 again. – Mhmd Feb 25 at 20:02
    
@Mhmd indeed +1 – Code Jockey Feb 25 at 20:05
1  
The answer now includes an exact calculation that demonstrates your observation that D- has no effect on 1, @Mhmd's, thank you – humn Feb 26 at 0:26

The answer is:

4194304

Uhm... As someone pointed out this question has a no computer tag that I did not originally see. Please ignore my answer, I'll just leave it here to avoid the same mistake to others

Solved by simulation (the tree has 2^23 nodes, can do):

Set<Integer> values(int depth, Set<Integer> state) {
    if (depth >= 22) return state;
    else {
        Set<Integer> dPlus = state.stream().map(i -> i * 2 + 1).collect(Collectors.toSet());
        Set<Integer> dMinus = state.stream().map(i -> i * 2 - 1).collect(Collectors.toSet());
        Set<Integer> nextPlus = values(depth+1, dPlus);
        Set<Integer> nextMinus = values(depth+1, dMinus);
        nextPlus.addAll(nextMinus);
        return nextPlus;
    }
}

void run(String[] args) {
    System.out.println(values(0, new HashSet<>(Arrays.asList(new Integer[]{1}))).size());
}
share|improve this answer
1  
see the no-computer tag? – manshu Feb 25 at 9:40
2  
@manshu whoops. My bad. I did not see it :/ – Diego Martinoia Feb 25 at 9:41
    
I was going to write a program, and I almost missed the "no-computer" tag myself. – imallett Feb 26 at 3:10

hmmn's answer is certainly correct, here is, I believe, a more formal approach.

A number, $x_0=1$, is displayed.

  • we may press $D-$ and produce $2x_0-1=1$, or
  • we may press $D+$ and produce $2x_0+1=3$.

These are both odd integers, and odd integers may always be expressed as $2a+1$ where $a$ is an integer.

Fairly obviously, as soon as we press $D+$ we escape from $1$ and may never not increase the number displayed.

Thus the only way to achieve a specific number with a specific quantity of button presses is to reach it with the final button press (e.g. $1$ only results from a sequence entirely of $D-$ and $3$ from a sequence of all $D-$ and a final $D+$).

If $x_n$ is $2a+1$ then $x_{n+1}$ is either

  • $2(2a+1)-1$, or
  • $2(2a+1)+1$.

Two different odd integers from which we may branch again, $D+$ producing the bigger of the two.

The biggest number we may achieve with $m$ presses would be

$$1 +\sum_{i=1}^{m}{2^i}=2^{m+1}-1$$ by only pressing $D+$.

Thus with $m$ presses we may yield $2^m$ odd integers between $1$ and $2^{m+1}-1$ inclusive.

There are exactly $\frac{2^{m+1}-1+1}{2}=\frac{2^{m+1}}{2}=2^m$ odd integers in this range, thus all such integers may be yielded.

Here $m = 22$ so we may produce any of the odd integers from $1$ through $2^{22+1}-1=8,388,607$

There are $2^{22}=4,194,304$ such numbers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.