7
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ This paper contains some work on the general variant of this problem. Using the paper's notation, this question asks for a calculation of $g_1(999,1000,1001)$. $\endgroup$ – 2012rcampion Sep 15 '15 at 18:41
7
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I believe that you are off by 1 (not 1 coin). $\endgroup$ – Joel Rondeau Sep 15 '15 at 19:05
  • $\begingroup$ @JoelRondeau Thanks, The question asks for largest amount, I was thinking largest number of coins. $\endgroup$ – Rohcana Sep 15 '15 at 19:16
  • $\begingroup$ Yeah, I meant in the other direction. I think you can do 499 999-coins plus 1 1000-coin. Would have posted it myself but you proved my original answer wrong, so I wasn't going to steal from your answer. $\endgroup$ – Joel Rondeau Sep 15 '15 at 19:19
  • $\begingroup$ @JoelRondeau Thanks again, feel free to post your own answer as well, maybe will learn something from it. $\endgroup$ – Rohcana Sep 15 '15 at 19:30
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.