Non-Pythagorean coins (Part 2)

Question

To make payments, the Non-Pythagoreans use coins in three denominations of 999, 1000, and 1001 Oboloi.

• Some amounts of Oboloi do not allow any representation by these three denominations (for example 1002).

• Other amounts of Oboloi do allow two or more different representations by these three denominations (for example 2000 allows 1000*2 and 999*1+1001*1).

• Some amounts of Oboloi have a unique representation by these three denominations (for example 2997 only allows the representation 2997=999*3)

What is the largest integer amount of Oboloi that has a unique representation by these three types of coins?

Comment 1: valid representations use non-negative numbers of coins

Comment 2: Pythagorean coins

Comment 3: Non-Pythagorean coins (Part 1)

Answer 1

I think it is-

$499\times 999 + 1000 = 499501$

The following facts hold-

• There can be at most one 1000-coin. Otherwise we replace 2 1000-coins with (999+1001)

• There can be exactly one type of coin from 999 and 1001, otherwise we replace two of them with 2 1000-coins.

• There can be at most 500, 999-coins. Other wise we can replace 501, 999-coins with 499, 1001-coins and one 1000 coin.

• There can be at most 499, 1001-coins. Other wise we can replace 500, 1001-coins with 500, 999-coins and one 1000 coin.

Checking the top few possibilities:

• 500, 999-coins and a 1000: can be replaced with 500, 1001-coins
• 499, 1001-coins and a 1000: can be replaced with 501, 999-coins
• 499, 999-coins and a 1000: Unique

Uniqueness Proof

Since $(499*999+1000)/1001=499501/1001=499.002>499$
We need exactly 500 coins (since even 499 1001-coins falls short).

Looking at it mod 1000, we are summing 500 numbers from the set $\{-1, 0, 1\}$ to $501$. So, all of them must be $-1\ (999)$ except one $0\ (1000)$.

Answer 2

Consider the following equivalent representations:

$$ \begin{align} 1000 + 1000 &= 999 + 1001 \\ 499 \times 1001 + 1000 &= 501 \times 999 \\ 500 \times 999 + 1000 &= 500\times 1001 \end{align} $$

The first shows that a unique representation can have no more than one $1000$, and cannot contain both $999$ and $1001$.

The second shows that a unique representation must have $500$ or fewer $999$s, and $498$ or fewer $1001$s if it contains a $1000$.

Similarly, the third shows that a unique representation must have $499$ or fewer $1001$s, and $499$ or fewer $999$s if it contains a $1000$.

Thus we have four possible maximal unique representations:

$$ \begin{align} 500 \times 999 &= 499\ 500 \\ 1000 + 499 \times 999 &= 499\ 501 \\ 499 \times 1001 &= 499\ 499 \\ 1000 + 498 \times 1001 &= 499\ 498 \end{align} $$

Thus the largest uniquely representable value is $499\ 501$.

Answer 3

Some conditions for a representation $999d_1 + 1000d_2 + 1001d_3 = N$ not to be unique.

• If $d_2 \ge 2$, then $(d_1+1, d_2-2, d_3+1)$ is also a valid representation of $N$. For $N$ to have a unique representation, we must have $d_2 = 0$ or $1$.

• If both $d_1 \ge 1$ and $d_2 \ge 1$, then $(d_1-1, d_2+2, d_3-1)$ is a valid representation of $N$, so at least one of $d_1$ and $d_3$ equals $0$.

• If $501 \le d_1 \le 999$, then--assuming that $d_3=0$ because otherwise we already showed that there would be another representation--$(0, d_2 + 2d_1 - 1000, 1000-d_1)$ is a valid representation of $N$.

• If $d_1 = 500$ and $d_2 = 1$, then--assuming that $d_3 = 0$ again--$(0, 1, 500)$ is another valid representation.

• If $500 \le d_3 \le 999$, then $(1000-d_3, d_2 + 2d_3-999, 0)$ is a valid representation of $N$.

• If $d_3 = 499$ and $d_2 = 1$, then--assuming that $d_3 = 0$ again--$(501, 0, 0)$ is another valid representation.

• If either $d_1$ or $d_3$ exceed $999$, then we can subtract $1000$ from them and add $999$ or $1001$ to $d_2$, respectively, for another valid representation of $N$.

So what is the largest number we can construct that satisfies these requirements? For $d_2 = 1$, there are two possibilities, $d_3 = 498$ or $d_1 = 499$. For $d_2 = 0$, there are $d_3 = 499$ and $d_1 = 500$. These are $499498$, $499501$, and $499499$, $499500$, respectively.

If $499501$ is indeed uniquely representable (I claim that it is), then it is the largest.

Note that $N \equiv d_3 - d_1 \pmod{1000}$ from the equation at the top.

If there is another representation, then $d_1 + d_3 \le d_1 + d_2 + d_3 = \frac{N-d_3+d_1}{1000} < 499 - \frac{d_3-d_1}{1000}$. The largest $d_1$ can be is clearly $499$, and the largest $d_3$ can be is $498$. Because of this, to achieve $d_3 - d_1 \equiv 499 \pmod{1000}$, we would need $d_3 - d_1 = -499$. If $d_3 > 0$, then $d_1 > 499$ which is impossible.

Thus the answer is $499\cdot 999 + 1000 = \boxed{499501}$.