DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Frobenius' Problem

Francesc Aguiló, Alícia Miralles

Abstract


Given k natural numbers {a1,...,ak}⊂ℕ with 1≤a1<a2<..<ak and gcd(a1,...,ak)=1, let be R(a1,...,ak)={λ1a1+⋯+λkak| λi∈ℕ, i=1÷ k} and R(a1,...,ak)=ℕ \ R(a1,...,ak). It is easy to see that |R(a1,...,ak)|<∞. The Frobenius Problem related to the set {a1,...,ak} consists on the computation of f(a1,...,ak)=maxR(a1,...,ak), also called the Frobenius number, and the cardinal |R(a1,...,ak)|. The solution of the Frobenius Problem is the explicit computation of the set R(a1,...,ak). In some cases it is known a sharp upper bound for the Frobenius number. When k=3 this bound is known to be F(N)=max0<a<b<N, gcd(a,b,N)=1f(a,b,N)= [begin cases]
2(⌊N/2⌋-1)2-1 if N≡0 (2),
2⌊N/2⌋(⌊N/2⌋-1)-1 if N≡1 (2).
[end cases] This bound is given in [Dixmier1990]. In this work we give a geometrical proof of this bound which allows us to give the solution of the Frobenius problem for all the sets {α,β,N} such that f(α,β,N)=F(N).

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional