Một số ví dụ liên quan tới vấn đề Frobenius

NguySn Thi H^ng Nhung vo Dig Tap chi KHOA HOC & C6N G NGH E 169(09) 233-237

SOME EXAMPLES RELATED TO FROBENIUS PROBLE M

Nguyen Thi Hong Nhung, Nguyen Thi Dung

Thai Nguyen University of Agriculture and Forestry

SUMMARY

Let ni,712,... ,nd € Z be positive integers and H" = (711,712,. -. ,nd) be the

numerical .semigroup generated by {ni,n2,..-,nd}. In this paper, we give

somes examples which are related to Frobenius problem, such as the sym￾metric, pseudo-symmetric and almost symmetric semigroup.

Key 'words: Frobenius number, Pseudo-Probenius number, Almost Frobe￾nius number, Symmetric semigroup, Pseudo-symmetric semigroup, Almost

symmetric semigroup.

1. INTRODUCTION

For d > 0, let ni,n2,...,nd be positive

integers, the Frobenius problem asks what

is the largest integer N for which the equa￾tion nixi + n2X2 •{•...+ UdXd = N has no

positive integers {xi,X2,-.. ,Xd} solution.

If gcd{ni,n2,...,nd) = 1, then the largest

integer N called the Frobenius number is

well defined. This problem is also known

as the Frobenius Coin Problem since the

Frobenius number of a set {ni,n2, ••. ,71^}

can be seen as the largest money amount

that cannot be obtained using only coins

of given denominations {ni,n2,. •• ,nd}. If

Ul = 6,712 9 and 713 = 20, then the

list of number A^ for which the equation

611-1-9x2+20x3 = A^ has no positive integer

solution is called the non McNugget num￾bers. Mc Donald sells chicken McNugget

in boxes of 6,9 and 20, so the non Mc￾Nugget numbers are the numbers of Mc￾Nuggets that you cannot get buying any

number of boxes.

Applications of the Frobenius problem

occur in number theory, automata theory,

sorting algorithm, etc. The problem of com￾puting the Frobenius number is • opened

since the end of 19th Century, for d = 2 the

formula of computing the FVobenius num￾ber for two positive integer numbers (a, 6)

IS ab-a-b and given by Sylvester in 1882.

For d = 3 a formula using Euclide's algo￾rithm for gcd was given in [7] and for d > 4,

there is not any algorithm with polynomial

time to compute the Frobenius number.

Recently, Frobenius problem has been

studied by algebraic point of view, combi￾natoric algebra, etc such as the symmetry,

pseudo-symmetry and almost symmetry of

numerical sermigroups. In this paper, based

on the results of [3], [4], [5], [6] we give some

examples related to Frobenius number.

2. SOME EXAMPLES

2.1. Frobenius number. Let ni,7i2,... ,71^

be positive integers and the numerical semi￾group H = {ciTll -h 02712 + . . . + CdUd I

0 ^ Ci € Z) be minimally generated by

{7ii,7t2,.-.,nd}.

Now we recall some definitions and basic

facts about fVobenius number and numeri￾cal sermigroup ([1], [2]),

Definition 2.1. (i) The FVobenius -number,

denoted by F{H), is the biggest integer not

belonging to H.

(ii) We say that an integer x is a pseudo￾Probenius number if x ^ iJ and x-\-h e H,

for alike H\ {0}. We denote by PF(H)

the set of pseudo-Frobenius numbers of H

PF{H) = {x^H\x + heH,\/0^heH}

= {xiH\x-\-n^eH,'^i = l,...,d}.