Parity Situation?

Probability Level 3

$\large x = a + b + c + d + e + f + abcdef$

In the expression above, $a$ , $b$ , $c$ , $d$ , $e$ , and $f$ have values $1$ or $-1$ . How many distinct values can $x$ take?

The answer is 4.

2 solutions

Kexin Zheng
May 26, 2016

We can make a table to list out all the possible combinations:

Prasun Biswas
May 27, 2016

First, note that since the expression $x$ is symmetric in terms of $a,b,c,d,e,f$ and we have $a,b,c,d,e,f\in\{-1,1\}$ , the number of distinct values $x$ can take can be evaluated by just considering how many of $a,b,c,d,e,f$ are $-1$ in $x$ .

Now, denote by $x_k$ the value of $x$ if $k$ elements out of $a,b,c,d,e,f$ be $-1$ . Then, $x_k=k(-1)+(6-k)(1)+(-1)^k=6-2k+(-1)^k$

Now, if $k$ is even, say $k=2m$ , then we have $x_{2m}=7-4m$ where $m\geq 0$

If $k$ is odd, say $k=2m-1$ , then $x_{2m-1}=7-4m$ . So, we have $x_{2m}=x_{2m-1}$ where $m\geq 1$

Furthermore, $x_{2m}\lt x_{2(m+1)}$ and $x_{2m+1}\lt x_{2(m+1)+1}$ when $m\geq 0$ .

So, we conclude that $\{x_k\}$ is a non-increasing sequence with $x_0\lt x_1=x_2\lt x_3=x_4\lt x_5=x_6$ , so there are $4$ distinct values in $\{x_k\}$ and since $x$ takes values from $\{x_k\}$ , there are $4$ distinct values $x$ can take.

A bit more general result:

If $x=a_1+a_2+\ldots+a_n+a_1a_2\cdots a_n$ where $a_i\in\{1,-1\}~\forall~1\leq i\leq n$ , then $x$ can take $\displaystyle\left\lceil\frac n2\right\rceil+1$ distinct values and the set of these distinct values is $\displaystyle\left\{n+1-4i\mid 0\leq i\leq\left\lceil\frac n2\right\rceil\right\}$ .

Moderator note:

Thanks for generalizing the result!

[N/2] +1 when N is even.....in case of n=11 it is not possible

Ankur Sharma - 5 years ago

Are you sure about that? Do note that $\lceil\cdot\rceil$ denotes the ceiling function , not the floor function . So, we have $\lceil 11/2\rceil=6$ and not $5$ which the floor function gives.

For $n=11$ , we see that $\lceil\frac{11}2\rceil+1=\lceil 5.5\rceil+1=6+1=7$ and indeed $x$ takes $7$ distinct values, namely from the set $\{12,8,4,0,-4,-8,-12\}$ .

For verification, here's a little Python script I wrote just now that checks by brute force the number of distinct values $x$ takes.

from itertools import product
from functools import reduce
def prod(i):
    return reduce(lambda x,y:x*y, i)
def test(n):
    myset=set()
    for i in product([1,-1],repeat=n):
        myset|={sum(i)+prod(i)}
    print("Number of distinct values is",len(myset),"and the set is",myset)

test(int(input("Enter the value of n = ")))

Here's the output:

Enter the value of n = 11
Number of distinct values is 7 and the set is {0, -4, 4, -12, 8, 12, -8}

Indeed, this matches with the generalized result in my solution.

Prasun Biswas - 5 years ago

okk got it...i was taking it floor function

Ankur Sharma - 5 years ago

Parity Situation?

The answer is 4.

2 solutions

Moderator note:

0 pending reports