دليل دراسي · 3 مختبرات تفاعلية · نحو 12 دقيقة

مجموعة ورق لعب مخلوطة تكاد تكون حتمًا بترتيب لم يحمله أحد قط.

هناك 52! طريقة لترتيب مجموعة ورق اللعب: عدد من 68 خانة، أكثر بكثير من عدد الثواني منذ الانفجار العظيم. تتعامل الرياضيات المتقطعة مع أشياء تُعدّ واحدًا واحدًا: الترتيبات، والشبكات، والعبارات الصحيحة أو الخاطئة. إنها الرياضيات التي تعمل عليها الحواسيب فعلًا.

ما أسرع نمو المضروبات
5!120طرق لاصطفاف 5 أشخاص
10!3,628,800طرق لترتيب 10 كتب
13!6,227,020,800أكثر من سكان الأرض
20!2.43 × 10^18أكثر من حبات الرمل على كل الشواطئ (تقديرًا)
52!8.07 × 10^67ترتيبات مجموعة ورق اللعب

ما الرياضيات المتقطعة؟

تدرس الرياضيات المتقطعة بنى مكوّنة من قطع منفصلة قابلة للعدّ لا من كميات متصلة: الأعداد الصحيحة، والمجموعات، والعبارات المنطقية، والبيانات (شبكات من نقاط وروابط)، وطرق عدّ الترتيبات.

يسأل التفاضل والتكامل كيف تتغير الأشياء بسلاسة؛ أما الرياضيات المتقطعة فتسأل: كم، وأيّها، وهل هذا ممكن أصلًا. وهي أساس الخوارزميات والتشفير وقواعد البيانات وتوجيه الشبكات وكل برهان على صحة برنامج.

نظرية البياناتشبكات من نقاط وروابط: الخرائط، والشبكات الاجتماعية، والويب.
التوافقياتعدّ الترتيبات والاختيارات.
المنطقالاستدلال بالصواب والخطأ، أساس الدوائر والبراهين.
نظرية الأعدادالأعداد الأولية والبواقي: رياضيات التشفير.
المختبر 1 · نظرية البيانات

اعبر كل جسر مرة واحدة بالضبط

انقر كتلة أرضية للبدء، ثم انقر الجسور لعبورها. لا يمكنك إعادة استخدام جسر. عام 1736 أثبت أويلر متى يكون ذلك ممكنًا: يوجد مسار فقط إذا كانت صفر أو اثنتان من الكتل الأرضية تلامس عددًا فرديًا من الجسور.

Nالدرجة 3Sالدرجة 3Iالدرجة 5Eالدرجة 3
0 / 7جسور عُبرت
4كتل أرضية بدرجة فردية
مساركانقر كتلة أرضية للبدء
في هذه الخريطة 4 كتل أرضية بعدد فردي من الجسور. قاعدة أويلر تقول إن هذا كثير جدًا. جرّب على أي حال!
المختبر 2 · العدّ

هل يهم الترتيب؟ هذا يغيّر كل شيء

اختر k عناصر من n. إن كان الترتيب مهمًا (منصة تتويج، رمز سري) فهذا تبديل. وإن لم يكن (يد ورق، لجنة) فهو توافيق: اقسم على الـk! ترتيبًا لكل مجموعة.

ذهب وفضة وبرونز من 8 عدّائين: 336 منصة، لكن 56 مجموعة مختلفة فقط من ثلاثة فائزين.
الترتيب مهم · nPk336n! / (n − k)!
مثلًا اختيار 3 من A-D:ABCABDACBACDADBADCBACBAD…
الترتيب غير مهم · nCk56n! / (k! (n − k)!)
مثلًا اختيار 3 من A-D:ABCABDACDBCD…
مثلث باسكال، الصف 8 (nCk لكل k)
المختبر 3 · مبدأ أعشاش الحمام

حمام أكثر من الأعشاش يعني أن أحدًا يتشارك

ضع n + 1 عناصر في n صناديق فسيحصل صندوق واحد على الأقل على اثنين. يبدو ذلك بديهيًا، لكنه يثبت حقائق مدهشة. هنا يُفرز الناس حسب شهر الميلاد: أضف الشخص الثالث عشر فيصبح وجود شهر مشترك مضمونًا.

ينا
فبر
مار
أبر
ماي
يون
يول
أغس
سبت
أكت
نوف
ديس
أضف الناس واحدًا واحدًا. يقع كلٌّ منهم في شهر ميلاد عشوائي.

الأفكار الأساسية في لمحة

مسار أويلر0 أو 2 رؤوس بدرجة فرديةلازم لعبور كل حافة مرة واحدة.
مبرهنة المصافحةΣ deg(v) = 2 × الحواففعدد الرؤوس ذات الدرجة الفردية زوجي دائمًا.
التبديلاتnPk = n! / (n − k)!الترتيب مهم.
التوافيقnCk = n! / (k!(n − k)!)الترتيب غير مهم.
أعشاش الحمامn + 1 عناصر، n صناديق → صندوق يضم 2يضمن تصادمًا.
الاستلزامp → q ≡ ¬p ∨ qخاطئ فقط حين تكون p صحيحة وq خاطئة.
دي مورغان¬(p ∧ q) ≡ ¬p ∨ ¬qنفي «و» يعطي «أو».
الأشجارn رؤوس → n − 1 حافةمتصلة ولا دورات فيها.

من إقليدس إلى الإنترنت

نحو 300 ق.م.إقليدس.أثبت أن الأعداد الأولية لا نهائية، وقدّم خوارزمية القاسم المشترك الأكبر.
1654باسكال وفيرما.رسائل حول مسألة قمار أسست الاحتمالات والعدّ المنهجي.
1736جسور أويلر.يُعد برهانه عن كونيغسبرغ أول مبرهنة في نظرية البيانات.
1854الجبر البولياني.حوّل جورج بول المنطق إلى جبر؛ وبعد 80 عامًا استخدمه شانون لتصميم الدوائر.
1959خوارزمية ديكسترا.أقصر المسارات في بيان، وتُستخدم اليوم في الخرائط وتوجيه الشبكات.
1976مبرهنة الألوان الأربعة.أُثبتت بحاسوب فحص نحو 2,000 حالة.

قراءات إضافية

Discrete Mathematics and Its ApplicationsKenneth Rosen · الكتاب الجامعي المعياري
Mathematics for Computer ScienceLehman, Leighton & Meyer · نص مجاني من MIT
Concrete MathematicsGraham, Knuth & Patashnik · الكلاسيكي المتعمق
اختبر نفسك: 20 سؤالًا في الرياضيات المتقطعةدليل الخوارزميات

ألغاز مثل لغز أويلر استدلال خالص. قِس استدلالك.

يغطي اختبار الذكاء الكامل لدينا الاستدلال المنطقي والعددي واللفظي والمكاني: 60 سؤالًا، نحو 30 دقيقة.

خذ اختبار الذكاء الكامل