קומבינטוריקה

[blueeye]

קומבינטוריקה

היו והתחלתי ללמוד קומבינטוריקה עלתה לי השאלה הבאה : יש לנו קבוצה של 3,000,000 מספרים 0 עד 3 מיליון יש לנו אפשרות לבחור 10,000 מספרים מתוכם במידה ושתי בחירות זהות הן מתבטלות (המודל הוא כמובן למי שמכיר המכרז MAX PRICE) כלומר במידה ומישהו בחר במספר 2.5 מיליון ועוד אחד בחר במספר זה הבחירה מבוטלת ולא תקפה מה הסיכוי שאני אבחר מספר שלא ייבחר ע"י מישהו אחר ? האם אפשר בכלל לחשב את זה ? מה הסיכוי שלי לבחור את המספר הגבוה ביותר ו ללא שאף אחד אחר בחר גם כן את המספר הזה תודה רועי

 

[איגור קרסיק]

אז ככה

מעולם לא למדתי הסתברות, אבל בכול זאת אנסה לענות לך [שכן קומביהטוריקה אני יודע]. ראשית, מספר האפשרויות לבחור מספרים ללא הגבלה הוא:

(3*10^6+1)^10,000​

. מספר הדרכים לבחור מספרים כך שאתה תבחר מספר שאף אחד אחר לא יבחר אותו: לך יש 3 מיליון ו-1 אפשרויות לבחור מספר ולשאר יש 3 מליון בחזקת 999 לבחור מספר. סה"כ זה המכפלה של 2 המספרים. נראה שהסיכוי שאתה תבחר מספר כך ש... הוא היחס בין הדרכים שאף אחד לא יבחר את המספר שלך לסה"כ. יצא לי שזה מספר שמאוד קרוב ל-1. בקירוב: 0.999667055. משום שלכולם יש סיכוי שווה לבחור את המספר הגדול ביותר, לך יש 1 חלקי 10000 לבחור את המספר הגבוהה ביותר. נראה לי שסיכוי לחיתוך המאורעות הוא מכפלת ביכוי כל מאורע. במקרה זה יצא לי מספר קטן מאוד! אם כבר בהסץברות עסקינן... האם מישהו מוכן להגדיר לי את המושג: הסתברות שמאורע מסוים יתרחש...

 

[Fingertip]

אין כזה דבר...

או, ליתר דיוק, תורת ההסתברות המודרנית בכלל לא עוסקת בזה... אסביר מעט למה התכוונתי: עורכים ניסוי כלשהו כך שכל התוצאות האפשריות שלו הן מתוך הקבוצה S. לקבוצה S קוראים "מרחב המדגם". כעת, לכל תת קבוצה של S נקרא מאורע. הגישה הישנה להגדרת הסתברות הייתה כזו: נניח ששמבצעים את הניסוי אינסוף פעמים. נסמן ב-pi את מספר הפעמים שבהם התרחש המאורע E ב-i הניסויים הראשונים. (כלומר, את מספר הפעמים שבהן תוצאת הניסוי הייתה אבר ב-E) אז הגבול:

lim pn/n n->infinity​

נקרא ההסתברות של המאורע E. אתה כמובן שואל את עצמך, מאיפה אנחנו יודעים שהגבול הזה קיים? וגם, למה לנו שהגבול הזה יישאר אותו הדבר עבור כל סדרת ניסויים שיתבצעו? בכל מקרה, אם אני לא טועה, האקסיומה היא שהגבול הזה קיים. זו כמובן הנחה רצינית ביותר. תורת ההסתברות המודרנית נוקטת בגישה שונה. היא אינה מצפה למצוא את ההסתברות של מאורע מסויים. אבל, היא אומרת כזה דבר. נניח שמצאנו פונקציית הסתברות, אז מה היא מקיימת? מוצאים 3 תכונות בסיסיות, ואז אומרים שהפונקציה P שמקיימת:

P(S) = 1 P(E) is in [0,1] P(E1UE2UE3U...)=P(E1)+P(E2)+...​

כאשר המאורעות הללו זרים. כעת, מוכיחים כל מיני דברים על פונקציית הסתברות כלשהי. אם אתה אכן רוצה לחשב את ההסתברות, אז אתה צריך לפרט כל מיני הנחות שלך. למשל, אם מרחב המדגם סופי, ואתה מניח שלכל נקודה במרחב המדגם יש הסתברות שווה להתקבל, אז לפי אקסיומה 3 ואקסיומה 1 מקבלים שההסתברות של כל נקודה במרחב היא:

1/|S|​

(מרחב מדגם כזה נקרה סימטרי) ולכן, אם אתה אומר לנו שמרחב המדגם סימטרי, אז בהכרח מצאנו את פונקציית ההסתברות, ומתקיים:

P(E)=|E|/|S|​

כמובן שאלו רק אינטרפרטציות שלך לפונקציית ההסתברות. מבחינת תורת ההסתברות, אין הגדרה חד משמעית להסתברות של מאורע. בכל מקרה, הוכיחו שאם P היא פונקציית הסתברות, אז הגבול שהוזכר מקודם קיים בהסתברות 1... מקווה שעזרתי. אהד.

 

[Oscar16]

אז ככה

אני וידידי, חובבי מכוניות מושבעים, ראינו שאפשר לקנות פורש בוקסטר חדשה בכ30 אלף ש"ח (אני מבין שזה לכד גם את העיניים שלך). מה רבה הייתה שמחתנו, והתיישבנו לחשוב איך אפשר להביא אותה בזכייה. ישבנו וחשבנו, חישבנו וחשבנו, והגענו למסקנה: אין שום דרך בה אתה יכול להבטיח את זכייתך. יש פה אך ורק את אלמנט המזל... אתה לא יכול אפילו להסתכל על זה בהיבט פסיכולוגי, כי אתה לא יכול להעמיד את עצמך כ"חכם מעל כולם", כי כולם עושים ככה, ולא הגעת לשום מקום. בשביל לזכות אתה צריך לאתר את אותם "חורים", המקומות בהם אף אחד לא הציע הצעה, ואתה יכול להשתלט עם החור ולזכות בפורש. אין דרך מתמטית לחשב איפה החורים. הדבר היחיד שאתה יכול לדעת, זה שיש 10000 משתתפים. לכן, סביר להניח ש100 השקלים הראשונים כולם יהיו תפוסים (ה רק אם כל אחד יציע הצעה שונה). מכאן, אתה יכול לקנות את כל ה5000 מספרים הראשונים, ואז בטוח שתזכה. אבל זה יעלה לך יותר מלקנות בוקסטר בחנות. לכן, הצעתי שלי אליך היא לעשות את מה שאנחנו רצינו לעשות: חישבנו בגימטריה את המלה פורש, בוקסטר, צהוב, בעברית ובאנגלית, גם ספרנו את מספר הבליטות שעל קוביית נייר טואלט והצלבנו את זה עם המלה "טישיו" בגימטריה, עשינו ממוצעים ובסוף הגענו למספר, x.yz. אנחנו, דרך אגב, בסופו של דבר ויתרנו כי הבנו שאין לנו סיכוי לזכות בפורש במחיר החלומי. סיכום: ללכת לקנות פורש קררה טורבו במקום בוקסטר מסריחה

בהצלחה!

 

[pallidfool]

כמובן שאין דרך להבטיח את הזכיה.

תמיד יכול לבוא מישהו שעלה על השיטה כמוך ובחר אותו מספר, והתוצאות לכן בהכרח יהיו סמטריות לגביכם. העניין הוא בהגדלת הסיכויים. דווקא ברור שקיימת בחירה (או בחירות) שיתנו תוצאה מקסימלית. קיים מספר סופי של אפשרויות, וכיוון שלכל אחד מיוחס מספר (הסיכוי לזכות) בהכרח קיים מקסימום. התוצאה טיפה יותר משמעותית מזה, כיוון שברור גם שלא כל הסיכויים לכל הבחירות שווים (הסיכוי לזכות כשבוחרים 0 הוא 0, למשל).

 

[pallidfool]

לא קומבינטוריקה ולא הסתברות

זו שאלה לתורת המשחקים. לא למדתי אותה, ולכן לא אוכל לענות. בכל מקרה, אני כן יכול להגיד שדרושה לך הנחה לגבי האינטיליגנציה של המשתתפים האחרים. האם הם בוחרים באקראיות? קשה לי להאמין שקירוב זה יניב תוצאות טובות. אולי הם אינטיליגנטים כמוך? אז אני מאמין שתקבל שהפעולה הטובה ביותר תניב לך סיכוי שווה עם האחרים. אני מניח שפתרון רציני של השאלה ידרוש מודל שיחזה בקירוב טוב בחירות של אחרים (למשל: חצי אחוז יבחרו במספר הגדול ביותר - אחוז וחמישית ב-2999999, וכו´).