هل هناك خوارزمية فعالة لتحديد الاحتمالية عددا صحيحا تم اختياره عشوائيا غير قابل للقسمة من قبل أي عدد صحيح من بعض المجموعة؟

Question

إعطاء مجموعة من 10 أعداد صحيحة $ a= a_1، a_1، a_2، cdots a_ {10} $ ، هل هناك خوارزمية فعالة يمكن أن تخبرني بما هو الاحتمالعدد صحيح تم اختياره عشوائيا بين $ 1 $ and 10 دولارات ^ {10} $ هو غير قابل للقسمة من قبل أي عضو في هذه المجموعة.

أفهم أن مبدأ الاستبعاد للإدماج يمكن استخدامه لحل هذه المشكلة ولكن لا يمكنني معرفة كيفية تطبيقه بحيث يعمل بكفاءة.

ملاحظة : عندما أقول "كفاءة"، أقصد وقت متعدد الحدود، لكنني لست متأكدا تماما ما هو مؤهل كوقت متعدد الحدود هو هذه الحالة كما تم إصلاح كلا المتغيرين.

Answer 1

دع $ \ mathbf x $ يكون رقم عشوائي في النطاق $ 1، \ Ldots، n $ ، ودع $ e_i $ تشير إلى الحدث الذي $ \ mathbf x $ قابل للقسمة بواسطة $ A_I $ . أنت مهتم باحتمال عدم وجود أي من الأحداث $ e_1، \ Ldots، E_M $ يحدث (في قضيتك، $ م= 10 دولار ). باستخدام مبدأ الاستبعاد الإدراج، هذا يقلل من حساب احتمالية أحميات الأحداث في النموذج $ e_ {i_1} \ land \ cdots \ land {i_k} $ ، هذا هو، $ \ mathbf x $ قابل للقسمة بواسطة جميع $ a_ {i_1}، \ Ldots، a_ {i_k} $ . منذ $ \ mathbf x $ قابل للقسمة بواسطة مجموعة من الأرقام IFF فهي قابلة للقسمة من قبل LCM، تكفي لتحديد الاحتمالية التي $ \ mathbf x $ قابلة للقسمة بواسطة $ $ .

بين $ 1، \ Ldots، N $ ، والأرقام القابلة للقسمة حسب $ $ $ هي $$ A، 2A، 3A، \ Ldots، \ lloroor n / a \ rfloor a، $ في المجموع $ \ lfloor n / a \ rfloor $ الأرقام. ومن هنا هو احتمال أن $ \ mathbf x $ قابلة للقسمة بواسطة $ $ هو بالضبط $$ \ frac {\ lloor n / a \ rfloor} {n}.