Кіріспе
Математикалық мәселе
Математикада монета мәселесі (сондай-ақ Фробеньюс монета мәселесі немесе Фробеньюс проблемасы деп аталады, математик Фердинанд Фробеньюс есімімен) – белгілі бір номиналдардағы монеталарды ғана қолдана отырып алуға болмайтын ең үлкен ақша сомасын анықтауға қойылатын математикалық мәселе. Мысалы, 3 және 5 бірлік номиналындағы монеталарды ғана қолдана отырып алуға болмайтын ең үлкен сома 7 бірлікке тең. Берілген монеталар жиыны үшін бұл мәселенің шешімі жиынның Фробеньюс саны деп аталады. Фробеньюс саны монеталар жиыны өзара жай сан болған жағдайда ғана бар. Егер тек екі түрлі монета номиналы болса, Фробеньюс саны үшін нақты формула бар: . Егер монета номиналының саны үш немесе одан көп болса, нақты формула белгілі емес. Дегенмен, кез келген белгілі бір монета номиналының саны үшін, монета номиналының логарифмдеріне байланысты полиномиал уақытта Фробеньюс санын есептеуге арналған алгоритм бар. Монета номиналының санына байланысты полиномиал уақытта жұмыс істейтін алгоритм белгілі емес, ал жалпы мәселе, онда монета номиналының саны кез келгенге жете алады, NP-қиын болып табылады.
Кіші n үшін Фробен сандары
Монета мәселесінің жабық түрдегі шешімі тек n = 1 немесе 2 болғанда ғана бар. n > 2 үшін жабық түрдегі шешім белгілі емес. Сильвестр бұл жағдайда бейнеленбейтін (оң) бүтін сандардың жалпы саны бар екенін де көрсетті. Скупиен осы ұсыныста теңдеудің тағы бір түрін келтіреді: Егер және болса, онда әрбір үшін теріс емес бүтін сандардың бір ғана жұбы бар және ол және . Формула келесідей дәлелденеді. Егер біз санын құрастыруды қаласақ, онда барлық бүтін сандар үшін өзара ажыратылған модульдер болады, сондықтан кез келген бүтін сан осы қалдықтардың біріне модуль бойынша сәйкес келуі керек; атап айтқанда, үшін бірегей мән және бірегей бүтін сан , осындай болады. Қайта реттесек, бізде теріс емес бүтін сан болады, сондықтан шындығында, себебі. Бүтін сандардың жартысы теріс емес бүтін сандардың сызықтық комбинациясы ретінде бейнеленеді екенін көрсету үшін, ең алдымен, егер бүтін сан бейнеленсе, онда бейнеленбейді екенін көрсетеміз, мұнда. Содан кейін керісінше де дұрыс екенін көрсетеміз: егер бейнеленбесе, онда бейнеленеді. Мұны көрсету үшін, фактіні пайдаланамыз, ол бізге жазуға мүмкіндік береді. Коэффициенттерді қосымша көбейту арқылы өзгертіп, қажет болса, біз деп есептей аламыз (шындығында, бұл теңдеуді және теңсіздіктерді қанағаттандыратын бірегей болады). Сол сияқты, біз қанағаттандыратын аламыз және енді біз бұл теңдеулерді қосып, жаза аламыз, ол бізді береді. Бұл сан оң, себебі. Шындығында, теңдеудің сол жағы санға бөлінеді және , сондықтан бөлінуі керек. Бірақ , сондықтан , сондықтан. Бұл мәндіге қойып, екі жақтанды шығарып аламыз. Содан біз аламыз. Бұл біздің немесе біреуінің теріс екенін білдіреді. Егер теріс болса, онда , яғни , бұл бейнеленеді; егер теріс болса, онда бейнеленеді. Осылайша, кез келген теріс емес бүтін сан үшін біз дәл біреуінің немесе бейнеленетінін білеміз (олар ерекше, өйткені сандар өзара жай болғандықтан, тақ болуы керек). Бұл берілген диапазон ішіндегі сандардың жартысы бейнеленетінін көрсетеді; диапазон ішінде сандар болғандықтан, бұл қажетті нәтижені береді.
The formula is proved as follows. Suppose we wish to construct the number Since , all of the integers for are mutually distinct modulo Thus any integer must be congruent modulo to one of these residues; in particular, taking there is a unique value of and a unique integer , such that Rearranging, we have a nonnegative integer so that Indeed, because
To show that exactly half of the integers are representable as non negative integer linear combinations, one first shows that if the integer is representable, then is not representable, where
One then shows that the converse is true as well: if is not representable, then is representable. To show this, use the fact that , which allows us to write Reducing and re arranging the coefficients by adding multiples of as necessary, we can assume (in fact, this is the unique such satisfying the equation and inequalities). Similarly we take satisfying and Now we can add these equations to write which, using yields The integer is positive, because In fact, since the left hand side of is divisible by , and , we must have that is divisible by Yet , so , so that Substituting this into and subtracting from both sides yields So This implies that , which means that exactly one of or is negative. If is negative, then , which means that is representable; the case when is negative entails that is representable. Thus for any non negative integer , we know that exactly one of or is representable (and these are distinct, because must be odd as the integers are relatively prime). This shows that half of the integers in the given range are representable; since there are integers in the range , this gives the desired result.
Арифметикалық реті
Арифметикалық тізбектегі бүтін сандар жиынтығының Фробеньес саны үшін қарапайым формула бар. Егер a, d, w бүтін сандары берілсе және ең үлкен ортақ бөлгіші (gcd(a, d)) = 1 болса:
Жоғарыдағы жағдай осы формуланың ерекше жағдайы ретінде түсіндірілуі мүмкін. Егер , болса, біз арифметикалық тізбектің кез келген кіші жиынтығын алып тастай аламыз және Фробеньес санының формуласы өзгермейді.
Басқа мысалдар
Регбиде ұпайдың төрт түрі бар: айыппұл соққысы (3 ұпай), құлау соққысы (3 ұпай), сынақ (5 ұпай) және айырбасталған сынақ (7 ұпай). Бұл түрлерді қоса алғанда, 1, 2 немесе 4 ұпайдан басқа кез келген ұпай жиынтығына қол жеткізуге болады. Жетілік регбиде барлық төрт түрдегі ұпайларға рұқсат берілгенімен, айыппұл соққысына жасалатын тырысулар сирек, ал құлау соққылары дерлік кездеспейді. Бұл командалардың ұпайлары көбінесе сынақтардың (5 ұпай) және айырбасталған сынақтардың (7 ұпай) еселігінен тұрады дегенді білдіреді. 5 және 7 ұпайдың еселігінен жасалмайтын және демек жетілікте кездеспейтін келесі ұпайлар: 3, 6, 8, 9, 11, 13, 16, 18 және 23 (1, 2 және 4 ұпайдан басқа). Мысалы, 2014 жылғы 15 Серия әлем чемпионатының ешбір ойынында осы ұпайлар тіркелмеген. Сол сияқты, американдық футболда команданың дәл бір ұпай жинауының жалғыз жолы – қарсыластың командасы тачдауннан кейін айырбастауға тырысқанда қауіпсіздік тағайындалса (бұл жағдайда ол 6 ұпайға тең). Қалыпты ойын кезінде қауіпсіздік үшін 2 ұпай, ал алаңнан гол үшін 3 ұпай беріледі, сондықтан 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 және 7–1 емес, қалған барлық ұпайлар мүмкін.
Шеллсорт уақыт күрделілігі
Shellsort алгоритмі – уақыт күрделілігі қазіргі таңда ашық мәселе болып табылатын сұрыптау алгоритмі. Ең нашар жағдайдағы күрделіліктің жоғарғы шегі берілген оң бүтін сандар тізбегінің Фробеньес саны арқылы көрсетіледі.
Ең аз тірі салмақ проблемасы
Петри желілері таратылған есептеудегі мәселелерді модельдеуге пайдалы. Нақты Петри желілерінің, атап айтқанда консервативті салмақты тізбектер үшін, белгілі бір салмақта қандай "күйлер" немесе "маркировкалар" "тірі" болатынын білу қажет. Ең төменгі тірі салмақты анықтау мәселесі Фробень проблемасына баламалы.
Көптаманың кеңейтілген үлесіндегі терминдер
Бірөлшелі полиномды белгілі бір дәрежеге көтергенде, полиномның көрсеткіштерін бүтін сандар жиыны ретінде қарастыруға болады. Ашылған полином кейбір көрсеткіштер үшін Фробеніус санынан жоғары дәрежелерді қамтиды (егер ЕБҚ=1 болса), мысалы, жиынтық {6, 7} болса, оның Фробеніус саны 29-ға тең, сондықтан мәнінің ешқандай мәні үшін көрсеткішті мүше пайда болмайды, бірақ мәнінің кейбір мәні 29-дан жоғары кез келген дәрежелі мүшелерді береді. Егер көрсеткіштердің ЕБҚ 1-ге тең болмаса, онда белгілі бір мәннен жоғары дәрежелер тек ЕБҚ-ның еселігі болған жағдайда ғана пайда болады, мысалы, жағдайында 24, 27 дәрежелері мәнінің кейбір мәндері үшін пайда болады, бірақ 3-ке еселі емес 24-тен жоғары мәндер (сондай-ақ кіші мәндер, 1, 8, 10, 14, 16, 17, 19, 23) пайда болмайды.