Joric and social egalitarianism

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Joric and social egalitarianism

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Romanian TST 5 2007, Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Valentin Vornicu

7301 posts

Valentin Vornicu

#1 h Jun 7, 2007, 7:44 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

The world-renowned Marxist theorist Joric is obsessed with both mathematics and social egalitarianism. Therefore, for any decimal representation of a positive integer $n$ , he tries to partition its digits into two groups, such that the difference between the sums of the digits in each group be as small as possible. Joric calls this difference the defect of the number $n$ . Determine the average value of the defect (over all positive integers), that is, if we denote by $\delta(n)$ the defect of $n$ , compute $\lim_{n \rightarrow \infty}\frac{\sum_{k = 1}^{n}\delta(k)}{n}.$
Iurie Boreico

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nima Ahmadi Pour

160 posts

Nima Ahmadi Pour

#2 h Jun 7, 2007, 1:39 PM • 2 Y

Y by Adventure10, Mango247

It is easy to observe that $\delta(n)$ is always less than $10$ . If you partition the digits in two groups with difference of sums $\delta(n)$ and $\delta(n)\geq 10$ then move one of the digits from the group with bigger sum to the other group. Hence $\delta(n)$ is bounded by $10$ .
I claim that the average is $\frac{1}{2}$ . It can be seen that this number is bigger than or equal to $\frac{1}{2}$ , because if the sum of the digits of $n$ is odd then $\delta(n)\geq 1$ , and the probability of having an odd digital sum is $\frac{1}{2}$ .
One can also see that the probability of a number to have at least $10$ digits of $1$ , is $1$ (Really easy to show). Now the average of $\delta(n)$ over all numbers will be equal to the average over the special numbers I mentioned (The ones having at least ten digits of $1$ )
For each of these numbers like $n$ , just remove the first ten digits of $1$ to obtain $m$ . Then we know that $\delta(m)<10$ . Now using the extra $1$ digits we have at hand we can distribute them among the two groups we have for $\delta(m)$ to decrease the difference between sums to either $0$ or $1$ . If the sum of digits of $m$ is odd we can reduce $\delta(m)$ to $1$ and in the other case to $0$ . One can again easily observe that the probability of $m$ having an odd digital sum is $\frac{1}{2}$ . So for half of the numbers (with respect to probability) we have $\delta(n)=0$ and for another half (disjoint from the last half) we have $\delta(n)\leq 1$ . So the average we are trying to find is less than or equal to $\frac{1}{2}$ and hence my claim is proved.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#3 h Jun 11, 2015, 4:22 PM • 1 Y

Y by Adventure10

I find

$\displaystyle\lim_{N \rightarrow \infty}\displaystyle\frac{\displaystyle\sum_{k = 1}^{10^N}\delta(k)}{10^N}$ .

Notice that $\forall k$ , $\delta(k) \le 9$ , since if it is more than $9$ , and the digits of $k$ are partitioned into $X \cup Y$ , then we can let $X' = X \setminus \{a\}, Y'=Y \setminus \{a\}$ for any $a \in X$ , and the defect will be smaller.

Notice that, out of the $10^N$ numbers from $1$ to $10^N$ , at most $9\cdot 9^{N}$ of them don't have all the digits. For these numbers, I use the bound $\delta(k) \le 9$ .

For any number $k$ that does have all the digits, I prove $\delta(k) \le 1$ , by contradiction, assuming $\delta(k) \ge 2$ . Let $X \cup Y$ be an optimal partition, with $\sum X - \sum Y = \delta(k) \ge 2$ .

If $1 \in X$ , then we can put 1 in $Y$ instead of $X$ , thus decreasing the defect by $1$ . Since the defect was at least 2, I have strictly decreased the defect, contradiction. But since $1$ appears in $k$ , then $1 \in Y$ . If $2 \in X$ , I can interchange 1 and 2 in $X$ and $Y$ , and the defect will decrease by 1, contradiction. But since $2$ appears in $k$ , then $2 \in Y$ . I can continue and I will get that $1,2,...,9$ don't appear in $X$ but they do appear in $Y$ . From this, I get that $\sum X=0, \sum Y >0$ , and thus $\delta(k) = \sum X - \sum Y$ is impossible! Thus I have proven $\delta(k) \le 1$ .

Also, if the sum of digits of $k$ is odd, then clearly $\delta(k)=1$ and if it is even, then $\delta(k)=0$ , by parity. Notice that half of the numbers satisfy the first condition and half satisfy the second condition. Therefore,

$\displaystyle\frac{\displaystyle\sum_{k = 1}^{10^N}\delta(k)}{10^N} \le \left( \displaystyle\frac{1}{10^N} \right) \cdot \left( 9*(9^{N}) + 0*\frac{10^N-9^N}{2}+1*\frac{10^N-9^N}{2} \right)$ ,

and, since $\delta(k) \ge 1$ if the sum of digits of $k$ is odd, which occurs for half of the numbers,

$\displaystyle\frac{\displaystyle\sum_{k = 1}^{10^N}\delta(k)}{10^N} \ge \left( \displaystyle\frac{1}{10^N} \right) \cdot \left(1*\frac{10^N}{2} \right)$ ,

both of which tend to $1/2$ , so we're done.

This post has been edited 2 times. Last edited by JuanOrtiz, Jun 11, 2015, 4:23 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a