Gönderen Konu: Farklı bir Frobenius Problemi  (Okunma sayısı 274 defa)

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.503
  • Karma: +15/-0
Farklı bir Frobenius Problemi
« : Kasım 28, 2025, 02:19:35 ös »
Klasik Frobenius problemi şu şekildedir: $a$ ve $b$ aralarında asal pozitif tamsayılar olsunlar. $n$ ve $m$ negatif olmayan tamsayılar olmak üzere $an+bm$'ye $a$ ve $b$'nin lineer kombinasyonu diyelim (normalde lineer kombinasyonda katsayılar negatif olabilir ama burada farklı tanımladık). $a$ ve $b$'nin lineer kombinasyonu olarak yazılamayan en büyük pozitif tamsayı $ab-a-b$'dir. Bu sayıya $a$ ve $b$'nin Frobenius sayısı denir.

Problem: $a$ ve $b$ aralarında asal pozitif tamsayılar olmak üzere, $a$ ve $b$'nin $k$ farklı lineer kombinasyonu olarak yazılamayan en büyük pozitif tamsayıya $k.$ Frobenius sayısı diyelim. $k.$ Frobenius sayısını $a$ ve $b$ cinsinden hesaplayınız. (Örneğin, $19$ sayısı $3\cdot 3+5\cdot 2$ olarak yazılabilir ve bu onun tek yazılışıdır fakat $26$ sayısı $3\cdot 2+5\cdot 4$ ve $3\cdot 7+5\cdot 1$ olmak üzere $2$ farklı şekilde yazılabilir.)
« Son Düzenleme: Kasım 28, 2025, 02:23:01 ös Gönderen: Metin Can Aydemir »
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 1.503
  • Karma: +15/-0
Ynt: Farklı bir Frobenius Problemi
« Yanıtla #1 : Kasım 30, 2025, 11:10:18 ös »
Öncelikle $1$. Frobenius sayısının gerçekten $ab-a-b$ olduğunu gösterelim. $S:=\langle a,b\rangle=\{an+bm: n,m\in\mathbb{Z}_{\geq 0}\}$ olarak tanımlansın ve $$\operatorname{Ap}(S,a)=\{s\in S: s-a\not\in S\}$$ olarak tanımlansın (Bu kümeye Apéry kümesi deniyor). $S$'nin elemanlarını $n$ moduna göre gruplayalım. Yeterince büyük her sayı $S$ kümesinin elemanı olacağından hiçbir küme boş küme değildir ($c>ab$ olan her tamsayı için $c\in S$'dir. Bu basit ve bilinen bir özelliktir ama en sonda bunu da ekleyeceğim.)

Kümelerin en küçük elemanlarını $s(i)$ ile gösterelim ($s(0)=0$). $n\in S$ olduğundan elemanlar $s(i)+at$ formatında olacaktır. Kümeler $$S_0=\{s(0),s(0)+a,s(0)+2a,\dots\},$$ $$S_1=\{s(1),s(1)+a,s(1)+2a,\dots\},$$ $$\vdots$$ $$S_{a-1}=\{s(a-1),s(a-1)+a,s(a-1)+2a,\dots\}$$ şeklindedir. Bu kümelerden de anlaşılacağı üzere $s-a\not\in S$ olan tüm elemanlar sadece $s(i)$ elemanlarıdır. Yani $\operatorname{Ap}(S,a)=\{0,s(1),s(2),\dots,s(a-1)\}$ formatındadır. Bu sayıların da aslında $\{0,b,2b,\dots,b(a-1)\}$ olduğunu görmek zor değildir.

$F(S)+a$ ($F(S):=$Frobenius sayısı) sayısı, tanım gereği $S$'nin elemanı olacağından $F(S)+a\in \operatorname{Ap}(S,a)=\{0,b,2b,\dots,b(a-1)\}$ olacaktır. $F(S)\not\in S$ en büyük tamsayı olduğundan $F(S)+a=b(a-1)$, yani $F(S)=ab-a-b$ olmalıdır.

Şimdi $k.$ Frobenius sayısını hesaplayalım. $c\geq F(S)+1$ olan her sayı için $c=an+bm$ olacak şekilde $n,m\geq 0$ olduğundan $c+(k-1)ab$ sayısını $$a(n+(k-1)b)+bm=a(n+(k-2)b)+b(m+a)=\cdots=an+b(m+(k-1)a)$$ olarak $k$ farklı şekilde yazabileceğimizden dolayı $(k-1)F(S)+1=kab-a-b+1$ sayısından büyük veya eşit tüm sayılar en az $k$ farklı şekilde yazılabilir. Şimdi ise $kab-a-b$'nin yazılamayacağını gösterelim. $kab-a-b=an+bm$'nin bir çözümü $(n,m)=(kb-1,-1)$'dir. Tüm çözümler, $$\dots,(kb-1,-1),((k-1)b-1,a-1),((k-2)b-1,2a-1),\dots,(b-1,(k-1)a-1),(-1,ka-1),\dots,$$ olduğundan $n$ ve $m$'nin pozitif oldukları durumlar arada kalan $k-1$ tanedir. Yani $kab-a-b$ sayısı $k$ farklı şekilde yazılamaz ama bu sayıdan büyük hepsi yazılabilir. $k.$ Frobenius sayısı $kab-a-b$'dir.

İspatta kullandığımız lemma: Eğer $c>ab$ ise $c=an+bm$ olacak şekilde $n,m\geq 0$ tamsayıları vardır.

İspat: Bezout teoreminden, $an_0+bm_0=1$ olacak şekilde $n_0$ ve $m_0$ tamsayıları vardır. Her $t$ tamsayısı için $a(n_0c+bt)+b(m_0c-at)=c$'dir. Eğer $\frac{m_0c}{a}\geq t\geq -\frac{n_0c}{b}$ olacak şekilde bir $t$ varsa $n:=n_0c+bt$ ve $m:=m_0c-at$ seçebiliriz. $t$'nin sınırları arasındaki uzaklık $\frac{c(an_0+bm_0)}{ab}=\frac{c}{ab}>1$ olduğundan bu aralıkta bir tamsayı kesinlikle vardır.
« Son Düzenleme: Aralık 01, 2025, 08:28:24 öö Gönderen: Metin Can Aydemir »
Gerçek hikayeler aslında söylenmeyenlerdir.

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal