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

$\endgroup$
  • $\begingroup$ Its infinite. Use a geometric picture, and imagine a,a+1, a+2 as your tuple. $\endgroup$ – The Masked Avenger Mar 14 '14 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 Mar 14 '14 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 Mar 14 '14 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 Mar 14 '14 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 Mar 14 '14 at 21:51
1
$\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.)

$\endgroup$
  • $\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 Mar 15 '14 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 Jun 14 '14 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 Jun 14 '14 at 17:12

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.