ت.11 · التكوينات الضعيفة، ثوابت الحلقات وتتبع المخططات الانسيابية

تحضير GRE للطلاب الجامعيين. أهداف محلية ضمن نطاق ETS المراجَع؛ هذا تعليم أصلي، وليس اختباراً رسمياً أو تنبئاً بالدرجات.

الشروط المسبقة: معاملات ذات الحدين، المتممات، وتتبع التخصيص.

• عد التوزيعات غير المميزة مع قيود غير سالبة أو موجبة
• تتبع مخطط انسيابي بترتيب العبارات مع سلوك إعادة التعيين الصحيح
• استخدام ثابت الحلقة ومقياس التقدم لتبرير خوارزمية

التكوين الضعيف: توزيع مرتب لمجموع كلي إلى أجزاء أعداد صحيحة غير سالبة.

ثابت الحلقة: خاصية محفوظة قبل وبعد كل تكرار للحلقة.

عدد الحلول الصحيحة غير السالبة لـ x₁+⋯+x_k=n هو C(n+k−1,k−1)، من أجل n≥0 و k≥1. مثّل n نجمة متطابقة مقسّمة على k صناديق مُسمّاة باستخدام k−1 خطافاً؛ الخطافات المتجاورة والخطافات الطرفية تسمح بدخول صفري. الصناديق مميزة، والأشياء غير مميزة. لو كانت الرموز المميزة، لتمت assigning كل رمز بشكل مستقل، مما يعطي k^n قبل القيود الأخرى. حدد النموذج بناءً على تمثيل الأشياء والمستقبلين، وليس بناءً على معامل ثنائي الحد الذي يبدو مألوفًا.

من أجل التوزيعات الموجبة x_i≥1، ضع z_i=x_i−1؛ المجموع المتبقي هو n−k، مما يعطي C(n−1,k−1) عندما يكون n≥k. يتم التعامل مع الحدود الدنيا الأكثر عمومية x_i≥a_i بطرح كل a_i. وجود صفر واحد على الأقل هو متمم أن تكون كل المدخلات موجبة: اطرح C(n−1,k−1) من المجموع غير السالب. الحالات المتداخلة مثل صندوقين فارغين بالضبط تتطلب عدداً مختلفاً؛ طرح حالة الصندوق الفارغ لكل منها بشكل مستقل يؤدي إلى حساب مزدوج لتقاطعاتها.

تتبع مخطط انسيابي عبارة تنفيذ واحدة تلو الأخرى، وتسجيل المتغيرات في جدول. اميز بين التخصيص واختبار المساواة الرياضية؛ الجانب الأيمن للتخصيص يستخدم القيمة القديمة قبل الاستبدال. سجل أي فرع سيتم تنفيذه بعد ذلك وأي متغيرات يتم إعادة تعيينها. قد يعيد مرشح حلقة خارجية جديدة تعيين مجموع داخلي دون إعادة تعيين المرشح نفسه. لعملية تجمع 1,3,5,… إلى S من الصفر، بعد m إضافة يصبح S=m² والمضاف التالي هو 2m+1.

ثابت الحلقة صحيح قبل وبعد كل تكرار. ينطبق ثابت مجموع المربعات في البداية عند m=0 ويحافظ عليه لأن m²+(2m+1)=(m+1)². لا يثبت الثابت وحده الانتهائية. لاختبار ما إذا كان عدد صحيح N≥0 مربعاً بإضافة الأعداد الفردية حتى S≥N، فإن S ينمو بلا حدود؛ وبالمقابل تزداد m وتصل حتماً إلى حد مثل N. عند الخروج، تعني المساواة أنه مربع، وتعني تجاوز الحد أنه ليس مربعاً. يجب أن تكون القيمة المطبوعة متاحة في مسار تنفيذ فعلي؛ لا يكفي نمط رقمي معقول وحده كمتتبع.

وزّع 11 رموز متطابقة بين 4 صناديق مسماة. عدد التخصيصات غير السالبة هو C(14,3)=364؛ عدد التخصيصات الموجبة تماماً هو C(10,3)=120. لذلك 244 تخصيصات تحتوي على صندوق فارغ واحد على الأقل. باختبار مجموع فردي مع N=10، يتقدم S 0,1,4,9,16؛ يتجاوز ويرفض 10. بالنسبة لـ N=9 يخرج عند S=9 بعد ثلاث إضافات. الإضافات التالية هي 1,3,5,7,9؛ أعمدة المجموع والإضافة التالية يجب ألا يتم الخلط بينهما.

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

عد الحلول غير السالبة لـ $a+b+c=8$ مع $a\ge2$. كم منها يحتوي أيضاً على $b,c\ge1$؟ كم من المجموعة الأولى لديه واحد على الأقل من b,c يساوي صفراً؟

حل نموذجي

ضع $u=a-2$. ثم $u+b+c=6$ له $\binom82=28$ حلول غير سالبة. يتطلب b,c موجبين وطرح واحد من كل منهما مجموعاً قدره أربعة في ثلاثة متغيرات غير سالبة، يُحسب بواسطة $\binom62=15$. عدد المتمم هو $28-15=13$. مباشرةً b=0 يعطي سبعة، c=0 يعطي سبعة، وكلاهما صفر محسوب مرتين، مما يعطي $7+7-1=13$.

تتبع هذه الخوارزمية من أجل N=15 و N=16: ابدأ بـ S=0، k=1؛ طالما S<N، نفذ S=S+k، ثم k=k+2؛ أبلغ عما إذا كان S=N. نصّ على ثابت، وبرر الانتهائية للعدد الصحيح $N\ge0$.

تحقق بعد المحاولة

بعد m تكراراً، $S=m^2$ و $k=2m+1$. أزواج المتتبع (S,k) هي $(0,1),(1,3),(4,5),(9,7),(16,9)$. وبالتالي 15 يُرفض بسبب تجاوز الحد و16 يُقبل. يتحقق الثابت في البداية ويحافظ عليه لأن $m^2+(2m+1)=(m+1)^2$. ينمو المجموع بلا حدود، لذا يصل في النهاية إلى N أو يتجاوزها؛ على سبيل المثال، m=N كافية عندما يكون N موجباً. بالنسبة لـ N=0، تُستثنى الحلقة وتتحقق المساواة. لا يثبت الثابت وحده الانتهائية.