13
$\begingroup$

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers.

It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c \mathbb{N})$ is a finite set, but it seems difficult to determine a formula for its maximum (the Frobenius number). This is the famous 'coin problem'.

I am asking about a related problem. Consider now the set of vectors $$(1,1,1) \mathbb{N} \setminus \sum (a,b,c) \mathbb{N},$$ where the sum ranges over all six permutations of $(a,b,c)$. Is it necessarily the case that, for relatively prime $a,b,c$, there is a maximum constant integral vector in this set? If so, what can we say about the maximum?

I suspet this may be connected (via a clever argument) with the ordinary postage stamp problem, but a quick 10-minute effort on my part failed.

edit: (here come the hypotheses!) $a+b+c$ must be odd

If this answer turns out to be negative, or the question turns out to be hard, let's make it easier by increasing the number of coordinates: $(1,\dots,1) \mathbb{N} \setminus \sum \mathbf{v} \mathbb{N}$, where the sum is over all $\mathbf{v}$ with one entry of each of $a$, $b$, $c$, and the rest $0$. Does this modification of the problem start to approach the ordinary coin problem for $a,b,c$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Its infinite. Use a geometric picture, and imagine a,a+1, a+2 as your tuple. $\endgroup$
    – The Masked Avenger
    Commented Mar 14, 2014 at 21:11
  • 1
    $\begingroup$ I made a mistake and replaced the line with the whole space N^3. I believe the answer is yes because you can form enough distinct target vectors in your set. I will see if I can provide a proof. $\endgroup$
    – The Masked Avenger
    Commented Mar 14, 2014 at 21:29
  • $\begingroup$ This is what I initially thought (enough target vectors), but actually I think you were right the first time. I just tried $a = 1$, $b = 2$, $c = 3$ and noticed a parity argument rules out odd constant vectors. There may be a hypothesis which makes the (first) problem interesting again. $\endgroup$
    – Peter Dukes
    Commented Mar 14, 2014 at 21:39
  • $\begingroup$ Interesting. I think there is a proof when b+c is not a multiple of a. Characterizing the tuples that "fill the line" would also be interesting. $\endgroup$
    – The Masked Avenger
    Commented Mar 14, 2014 at 21:43
  • $\begingroup$ I think something like a=b+c mod p for some prime p may lead to holes, and otherwise not. In any case, I'm glad to have inspired some progress. $\endgroup$
    – The Masked Avenger
    Commented Mar 14, 2014 at 21:51

1 Answer 1

Reset to default
2
$\begingroup$

I guess the answer should be that $(a,b,c)$ fills the line if and only if there is an integral combination of its permutations equaling $(1,1,1)$. We want the elementary divisors of a certain $3 \times 6$ matrix. Working out explicit conditions should be do-able. I wonder if there is a slick argument.

There is also a neat connection with semi-magic squares, I think.

When allowing longer vectors which are permutations of $(a,b,c,0,\dots,0)$, it feels like their Frobenius number is the truth, but again with some extra necessary divisibility conditions.

(Sorry if my question was elementary.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ It seems to me that you get all but finitely many elements iff the subgroup generated by the intersection of your two monoids is the whole line. I am not sure you can generate a subgroup before intersecting. Anyway this is polynomial time decidable. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 15, 2014 at 16:01
  • 4
    $\begingroup$ The sum of entries of any representable vector is divisible by $a+b+c$, so $a+b+c\mid 3$, which, under the condition $a,b,c>0$, means $a=b=c=1$. $\endgroup$
    – fedja
    Commented Jun 14, 2014 at 14:43
  • 1
    $\begingroup$ I am embarrassed to have missed this! So no nontrivial triple of positive integers fills the line by combinations of its permutations, correct? Maybe the problem is interesting if we relax to $a,b,c \in \mathbb{Z}$. $\endgroup$
    – Peter Dukes
    Commented Jun 14, 2014 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .