In a village, there are $n$ people who each has an ID number from 1 to $n$. Each person is either completely honest or a total liar. One day, a detective came to visit and interviewed them. This is what they told him:

If a person had an ID number $x$ where $x$ is even, he said:

"The person whose ID number is $x/2$ is honest"

If a person had an ID number $x$ where $x$ is odd and greater than one, he said:

"The person whose ID number is $(x-1)/2$ is a liar"

Person with ID number of 1 did not say anything.

If $L$ is the number of liars and $H$ is the number of honest villagers, find all possible values of $L-H$

## Sunday, June 26, 2011

## Tuesday, June 21, 2011

### Inequality

If $x_1,\dots,x_n$ are real numbers such that $0 \leq x_i \leq 1 \forall i$, and satisfies $x_1 + \dots + x_n = m+r$ where $m$ is an integer and $0 \leq r < 1$, show that:

$$(1+x_1)(1+x_2)\dots(1+x_n) \geq (1+r)2^m$$

Determine the conditions under which equality is achieved.

Solution

For each $i$ such that $x_i = 0$ or $x_i = 1$, we can safely eliminate them from the problem without changing neither the condition nor the inequality. So without loss of generality, we can assume that $0 < x_i < 1$ for all $i$.

Now, we prove by induction on $n$. It is trivial for $n=1$. For $n=2$, we have two cases:

1. The simple case, $x_1 + x_2 = r < 1$ then the inequality also holds trivially

2. The overflowing case, where $1 < x_1 + x_2 = 1 + r$, then:

$$(1-x_1)(1-x_2) \geq 0$$

$$\iff 1+x_1x_2 \geq x_1+x_2 = 1+r$$

$$\iff 1+x_1+x_2+x_1x_2 \geq 2+2r$$

$$\iff (1+x_1)(1+x_2) \geq 2(1+r)$$

Now, for a larger value of $n$, suppose that the inequality is established for $n-1$, and suppose that $x_1 + \dots + x_{n-1} = m + r$. Again we have two cases,

1. The simple case, if $x_n + r < 1$ then $x_1 + \dots + x_n = m+ (r+x_n) < m+1$

$$(1+x_1)\dots(1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m \geq (1+r+x_n)2^m$$

which follows from the simple case for $n=2$ above.

2. The overflowing case, if $1 < x_n + r = 1 + r_2$ then $x_1 + \dots + x_n = (m+1) + r_2$

$$(1+x_1) \dots (1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m$$

$$ \geq (1+r_2)2^{m+1}$$

which is similar to the overflowing case from $n=2$ above.

The equality cases can be determined as follows:

If all $x_i$s are zeros or ones, then the equality follows trivially. We assert then at most one of the $x_i$s are strictly between zero and one. Because if there are two of them, then both the simple case and the overflowing case in $n=2$ will never reach equality. The inductive step in the proof also depends on these two cases.

$$(1+x_1)(1+x_2)\dots(1+x_n) \geq (1+r)2^m$$

Determine the conditions under which equality is achieved.

Solution

For each $i$ such that $x_i = 0$ or $x_i = 1$, we can safely eliminate them from the problem without changing neither the condition nor the inequality. So without loss of generality, we can assume that $0 < x_i < 1$ for all $i$.

Now, we prove by induction on $n$. It is trivial for $n=1$. For $n=2$, we have two cases:

1. The simple case, $x_1 + x_2 = r < 1$ then the inequality also holds trivially

2. The overflowing case, where $1 < x_1 + x_2 = 1 + r$, then:

$$(1-x_1)(1-x_2) \geq 0$$

$$\iff 1+x_1x_2 \geq x_1+x_2 = 1+r$$

$$\iff 1+x_1+x_2+x_1x_2 \geq 2+2r$$

$$\iff (1+x_1)(1+x_2) \geq 2(1+r)$$

Now, for a larger value of $n$, suppose that the inequality is established for $n-1$, and suppose that $x_1 + \dots + x_{n-1} = m + r$. Again we have two cases,

1. The simple case, if $x_n + r < 1$ then $x_1 + \dots + x_n = m+ (r+x_n) < m+1$

$$(1+x_1)\dots(1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m \geq (1+r+x_n)2^m$$

which follows from the simple case for $n=2$ above.

2. The overflowing case, if $1 < x_n + r = 1 + r_2$ then $x_1 + \dots + x_n = (m+1) + r_2$

$$(1+x_1) \dots (1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m$$

$$ \geq (1+r_2)2^{m+1}$$

which is similar to the overflowing case from $n=2$ above.

The equality cases can be determined as follows:

If all $x_i$s are zeros or ones, then the equality follows trivially. We assert then at most one of the $x_i$s are strictly between zero and one. Because if there are two of them, then both the simple case and the overflowing case in $n=2$ will never reach equality. The inductive step in the proof also depends on these two cases.

Labels:
convex,
induction,
Inequality,
majorization

## Sunday, June 12, 2011

### Supersum

For a natural number $n$, the supersum of $n$ is defined as the sum of possible combinations that we can obtain by deleting digits of $n$, calculated as modulo 9. For example, the supersum of 1234 is:

No deletions: 1234 +

Deleting 1 digit: 123 + 134 + 234 + 124

Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +

Deleting 3 digits: 1 + 2 + 3 + 4

$ = 8 \mod 9$

If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.

No deletions: 1234 +

Deleting 1 digit: 123 + 134 + 234 + 124

Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +

Deleting 3 digits: 1 + 2 + 3 + 4

$ = 8 \mod 9$

If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.

Labels:
digit,
modulo,
Number Theory,
subset,
supersum

Subscribe to:
Posts (Atom)