Skip to main content
added 28 characters in body
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

Here are two partial negative claims.

Remark: Claim 1 is inspired by the relation $54\not\geq 48$ suggested in the comments. However, it does not prove that relation, although it proves, say, $486\not\geq 480$. (It also does not prove $2^n\not\geq 2^n-2$, which is shown in Claim 2.)

Claim 1. Assume that $b$ is divisible by some prime power $p^{2k-1}$ such that $p^k>a-b$. THenThen $a\not\geq b$.

Proof. Start with $b$ zeroes and $c=a-b$ ones. Notice thatathat a simultaneous shift of all quantities by the same number does not affect anything. So we modify the process by shifting, after each operation, the quantities so that the averaged quantities turn into zeroes. We will also multiply the numbers, after each operation, by the same number so that they become integers coprime in total.

In other words, the modified process is as follows. We choose $b$ cups with total amount of $S$. We replace all those ampountsamounts by zeroes, and subtract $S/b$ from all other $c$ quantities. After that we multiply everything by the common denominator (and, maybe, reduce the common factor --- but it will be always coprime with $p$).

We claim that, after each operation, there will always be exactly $c$ nonzero numbers not divisible by $p$, and all those $c$ numbers are congruent $\mod p^k$. This immediately implies the result. In the beginning this holds.

Let $x$ be the common resuidue of nonzero numbers $\mod p^k$, and suppose we took $y$ of them into the averaged group. Then $p\nmid x$ and $p^k\nmid y$, so $S\equiv xy\not\equiv 0\pmod {p^k}$, and hence the irreducible form of $S/b$ has denominator divisible by $p^k$. Thus, allafter the operation, all $c$ potentially nonzero numbners after the subtraction of $S/b$numbers will havebe indeed nonzero and their denominators will be divisible by $p^k$, although their differences will be integers. Then, after the multiplication by the common denominator (and reduction by the common factor coprime with $p$) they will have a desired form. This completes the proof.

Claim 2. $2^n\not\geq 2^n-2$ for $n\geq 3$.

Proof. We use the first step of the above modification, but omit reducing the factor. We will show that a situation with all zeroes except for two equal numbers cannot be averaged. Indirectly, the position before all-zeroes should be $(1,-1,0,\dots,0)$ (multiply by a constant if necessary). We may assume that, in the process, we did not get a situation with two equal nonzero numbers.

The step of the direct process looks like $$ (x,y,0,0,\dots,0)\mapsto (y-x/b,-x/b,0,\dots,0), $$ as if we took both $x$ and $y$ to be averaged, we would get two equal nonzero numbers. Revert the process; the step in the reverse process looks like $$ (x,y,0,\dots,0)\mapsto (-bx,y-x,0,\dots,0). $$ So, say, the first step in the reverse process is, up to the sign change, $$ (-1,1,0,\dots,0)\mapsto (b,2,0,\dots,0). $$ We claim that we always get two integers exactly one of which is divisible by $b$, so they will always be distinct. Indeed, if $b$ divides exactly one of $x$ and $y$, then $b\mid -bx$ but $b\nmid y-x$. The proof is complete.

Here are two partial negative claims.

Remark: Claim 1 is inspired by the relation $54\not\geq 48$ suggested in the comments. However, it does not prove that relation, although it proves, say, $486\not\geq 480$. (It also does not prove $2^n\not\geq 2^n-2$, which is shown in Claim 2.)

Claim 1. Assume that $b$ is divisible by some prime power $p^{2k-1}$ such that $p^k>a-b$. THen $a\not\geq b$.

Proof. Start with $b$ zeroes and $c=a-b$ ones. Notice thata simultaneous shift of all quantities by the same number does not affect anything. So we modify the process by shifting, after each operation, the quantities so that the averaged quantities turn into zeroes. We will also multiply the numbers, after each operation, by the same number so that they become integers coprime in total.

In other words, the modified process is as follows. We choose $b$ cups with total amount of $S$. We replace all those ampounts by zeroes, and subtract $S/b$ from all other $c$ quantities. After that we multiply everything by the common denominator (and, maybe, reduce the common factor --- but it will be always coprime with $p$).

We claim that, after each operation, there will always be exactly $c$ nonzero numbers not divisible by $p$, and all those $c$ numbers are congruent $\mod p^k$. This immediately implies the result. In the beginning this holds.

Let $x$ be the common resuidue of nonzero numbers $\mod p^k$, and suppose we took $y$ of them into the averaged group. Then $p\nmid x$ and $p^k\nmid y$, so $S\equiv xy\not\equiv 0\pmod {p^k}$, and hence the irreducible form of $S/b$ has denominator divisible by $p^k$. Thus, all the $c$ nonzero numbners after the subtraction of $S/b$ will have denominators divisible by $p^k$, although their differences will be integers. Then, after the multiplication by the common denominator (and reduction by the common factor coprime with $p$) they will have a desired form. This completes the proof.

Claim 2. $2^n\not\geq 2^n-2$ for $n\geq 3$.

Proof. We use the first step of the above modification, but omit reducing the factor. We will show that a situation with all zeroes except for two equal numbers cannot be averaged. Indirectly, the position before all-zeroes should be $(1,-1,0,\dots,0)$ (multiply by a constant if necessary). We may assume that, in the process, we did not get a situation with two equal nonzero numbers.

The step of the direct process looks like $$ (x,y,0,0,\dots,0)\mapsto (y-x/b,-x/b,0,\dots,0), $$ as if we took both $x$ and $y$ to be averaged, we would get two equal nonzero numbers. Revert the process; the step in the reverse process looks like $$ (x,y,0,\dots,0)\mapsto (-bx,y-x,0,\dots,0). $$ So, say, the first step in the reverse process is, up to the sign change, $$ (-1,1,0,\dots,0)\mapsto (b,2,0,\dots,0). $$ We claim that we always get two integers exactly one of which is divisible by $b$, so they will always be distinct. Indeed, if $b$ divides exactly one of $x$ and $y$, then $b\mid -bx$ but $b\nmid y-x$. The proof is complete.

Here are two partial negative claims.

Remark: Claim 1 is inspired by the relation $54\not\geq 48$ suggested in the comments. However, it does not prove that relation, although it proves, say, $486\not\geq 480$. (It also does not prove $2^n\not\geq 2^n-2$, which is shown in Claim 2.)

Claim 1. Assume that $b$ is divisible by some prime power $p^{2k-1}$ such that $p^k>a-b$. Then $a\not\geq b$.

Proof. Start with $b$ zeroes and $c=a-b$ ones. Notice that a simultaneous shift of all quantities by the same number does not affect anything. So we modify the process by shifting, after each operation, the quantities so that the averaged quantities turn into zeroes. We will also multiply the numbers, after each operation, by the same number so that they become integers coprime in total.

In other words, the modified process is as follows. We choose $b$ cups with total amount of $S$. We replace all those amounts by zeroes, and subtract $S/b$ from all other $c$ quantities. After that we multiply everything by the common denominator (and, maybe, reduce the common factor --- but it will be always coprime with $p$).

We claim that, after each operation, there will always be exactly $c$ nonzero numbers not divisible by $p$, and all those $c$ numbers are congruent $\mod p^k$. This immediately implies the result. In the beginning this holds.

Let $x$ be the common resuidue of nonzero numbers $\mod p^k$, and suppose we took $y$ of them into the averaged group. Then $p\nmid x$ and $p^k\nmid y$, so $S\equiv xy\not\equiv 0\pmod {p^k}$, and hence the irreducible form of $S/b$ has denominator divisible by $p^k$. Thus, after the operation, all $c$ potentially nonzero numbers will be indeed nonzero and their denominators will be divisible by $p^k$, although their differences will be integers. Then, after the multiplication by the common denominator (and reduction by the common factor coprime with $p$) they will have a desired form. This completes the proof.

Claim 2. $2^n\not\geq 2^n-2$ for $n\geq 3$.

Proof. We use the first step of the above modification, but omit reducing the factor. We will show that a situation with all zeroes except for two equal numbers cannot be averaged. Indirectly, the position before all-zeroes should be $(1,-1,0,\dots,0)$ (multiply by a constant if necessary). We may assume that, in the process, we did not get a situation with two equal nonzero numbers.

The step of the direct process looks like $$ (x,y,0,0,\dots,0)\mapsto (y-x/b,-x/b,0,\dots,0), $$ as if we took both $x$ and $y$ to be averaged, we would get two equal nonzero numbers. Revert the process; the step in the reverse process looks like $$ (x,y,0,\dots,0)\mapsto (-bx,y-x,0,\dots,0). $$ So, say, the first step in the reverse process is, up to the sign change, $$ (-1,1,0,\dots,0)\mapsto (b,2,0,\dots,0). $$ We claim that we always get two integers exactly one of which is divisible by $b$, so they will always be distinct. Indeed, if $b$ divides exactly one of $x$ and $y$, then $b\mid -bx$ but $b\nmid y-x$. The proof is complete.

Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

Here are two partial negative claims.

Remark: Claim 1 is inspired by the relation $54\not\geq 48$ suggested in the comments. However, it does not prove that relation, although it proves, say, $486\not\geq 480$. (It also does not prove $2^n\not\geq 2^n-2$, which is shown in Claim 2.)

Claim 1. Assume that $b$ is divisible by some prime power $p^{2k-1}$ such that $p^k>a-b$. THen $a\not\geq b$.

Proof. Start with $b$ zeroes and $c=a-b$ ones. Notice thata simultaneous shift of all quantities by the same number does not affect anything. So we modify the process by shifting, after each operation, the quantities so that the averaged quantities turn into zeroes. We will also multiply the numbers, after each operation, by the same number so that they become integers coprime in total.

In other words, the modified process is as follows. We choose $b$ cups with total amount of $S$. We replace all those ampounts by zeroes, and subtract $S/b$ from all other $c$ quantities. After that we multiply everything by the common denominator (and, maybe, reduce the common factor --- but it will be always coprime with $p$).

We claim that, after each operation, there will always be exactly $c$ nonzero numbers not divisible by $p$, and all those $c$ numbers are congruent $\mod p^k$. This immediately implies the result. In the beginning this holds.

Let $x$ be the common resuidue of nonzero numbers $\mod p^k$, and suppose we took $y$ of them into the averaged group. Then $p\nmid x$ and $p^k\nmid y$, so $S\equiv xy\not\equiv 0\pmod {p^k}$, and hence the irreducible form of $S/b$ has denominator divisible by $p^k$. Thus, all the $c$ nonzero numbners after the subtraction of $S/b$ will have denominators divisible by $p^k$, although their differences will be integers. Then, after the multiplication by the common denominator (and reduction by the common factor coprime with $p$) they will have a desired form. This completes the proof.

Claim 2. $2^n\not\geq 2^n-2$ for $n\geq 3$.

Proof. We use the first step of the above modification, but omit reducing the factor. We will show that a situation with all zeroes except for two equal numbers cannot be averaged. Indirectly, the position before all-zeroes should be $(1,-1,0,\dots,0)$ (multiply by a constant if necessary). We may assume that, in the process, we did not get a situation with two equal nonzero numbers.

The step of the direct process looks like $$ (x,y,0,0,\dots,0)\mapsto (y-x/b,-x/b,0,\dots,0), $$ as if we took both $x$ and $y$ to be averaged, we would get two equal nonzero numbers. Revert the process; the step in the reverse process looks like $$ (x,y,0,\dots,0)\mapsto (-bx,y-x,0,\dots,0). $$ So, say, the first step in the reverse process is, up to the sign change, $$ (-1,1,0,\dots,0)\mapsto (b,2,0,\dots,0). $$ We claim that we always get two integers exactly one of which is divisible by $b$, so they will always be distinct. Indeed, if $b$ divides exactly one of $x$ and $y$, then $b\mid -bx$ but $b\nmid y-x$. The proof is complete.