مرجع
آخر الزيارات

مبرهنة إيردوس-سيكريس

300 كلمة•0 مشاهدة•🗒️ منذ 5 أيام
باختصار: في الرياضيات، تنص مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول ، يوجد لها متتالية جزئية متزايدة بطول أو متتالية جزئية متناقصة بطول . في هذه المقالة 4 أقسام: «مثال»، «3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2» و«مبدأ برج الحمام» وغيرها.
المحتويات
  1. مثال
  2. 3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2
  3. مبدأ برج الحمام
  4. برهان
مبرهنة إيردوس-سيكريس

تعريفًا بالموضوع، في الرياضيات، تنص مبرهنة إيردوس-سيكريس على أنه في كل متتالية مكونة من أعداد حقيقية بطول ، يوجد لها متتالية جزئية متزايدة بطول أو متتالية جزئية متناقصة بطول . هذه المبرهنة هي مبرهنة مثالية في نظرية رمزي، التي تبحث الانتظام وسط الفوضى. وفيما يلي تفاصيل أوسع عن ذلك.

وفي هذا الصدد، تمت برهنة المبرهنة على يد بول إيردوس وجورج سيكريس في مقال لهما سنة 1935.

مثال

  • 1,2,3 متتالية جزئية متزايدة مكونة من كل الأعداد
  • 1,3,2 يملك متتالية جزئية متناقصة 3,2
  • 2,1,3 يملك متتالية جزئية متناقصة 2,1
  • 2,3,1 يملك متتاليتين متناقصين 2,1 و 3,1

كذلك، لـ r = 1 و s = 2، تخبرنا الصيغة بأنه لأي تبديل من 3 أعداد يوجد متتالية جزئية متزايدة بطون 3 أو متتالية جزئية متناقصة بطول 2. ننظر إلى جميع التبديلات من الأعداد 1,2,3:

3,1,2 يملك متتاليتين متناقصين 3,1 و 3,2

3,2,1 متتالية جزئية متناقصة مكونة من كل الأعداد

مبدأ برج الحمام

  • كل عددين في المتتالية مميزين بزوج مختلف:
  • إذا كان i < j و ni < nj إذن ai < aj
  • إذا كان i < j و ni > nj إذن bi < bj

ومن جهة أخرى، إذا كانت معطاه متتالية بطول rs + 1، نميز كل عدد ni في المتتالية بالزوج (ai,bi)، بحيث أن ai هو طول أطول متتالية متزايدة تنتهي بـ ni و bi هو طول أطول ممتالية متناقصة تنتهي بـ ,ni.

  • انظر كذلك
  • مبرهنة رمزي
  • مراجع

من جانب آخر، ولكن هنالك rs علامة مميّزة بحيث أن ai على الأكثر r و bi على الأكثر s، ولذلك بحسب مبدأ برج الحمام يجب أن تكون قيمة i بحيث ai أو bi خارج المجال. إذا كانت ai خارج المجال إذن ni هي جزء من متتالية متزايدة بطول 1 + r على الأقل، وإذا كانت bi خارج المجال إذن ni هي جزء من متتالية متناقصة بطول 1 + s على الأقل.

برهان

إضافةً إلى ذلك، يمكن برهنة مبرهنة إيردوس-سيكريس بالعديد من الطرق; عاين ستة براهين مختلفة لمبرهنة إيردوس-سيكريس، بما في ذلك البرهان التالي.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.