רנרפש - חידה !

[clocker]

רנרפש - חידה !

יש לי קבוצה S של n איברים, המכילה את המספרים מ1 עד עד n. אני מעוניין לבחור k תת קבוצות של S, שאף אחת מהן לא מוכלת באף אחת אחרת דוגמא: עבור n=4, מצאתי 4 קבוצות (k=4)

S={1,2,3,4} {1,2},{1,3},{4,1},{4,3,2}​

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

 

[עריסטו]

נראה לי שפתרתי

אני חושב שניתן להניח ללא הגבלת כלליות שכל k תת הקבוצות הן בעלות אותה עוצמה (כי אם זה לא כך ובגדולה מביניהן יש x איברים ניתן להוסיף איברים לכל אחת מהקבוצות כל שבכולן יהיו x איברים, ויש מספיק אפשרויות לבחירת האיברים הנוספים כך שכל הקבוצות המתקבלות יהיו שונות). לכל הפתרון הוא המקסימום של n מעל m, כלומר הפתרון הוא n מעל רצפה של n/2. בתקווה שלא כתבתי שטויות

 

[עריסטו]

כל=כך, לכל=לכך

 

[clocker]

../images/Emo127.gif נכון מאוד

למשפט הזה בקומבינטוריקה קוראים משפט שפרנר, כותרת החידה היתה הפתרון בהיפוך אותיות. והשם הפורמלי של "אוסף קבוצות שאין אף קבוצה שמוכלת באף אחרת" הוא אנטי-שרשרת. רק תשים לב שהפתרון n מעל n/2, לא משנה אם תעגל את n/2 מעלה או מטה, התשובה תהיה זהה בגלל הסימטריה של המקדם הבינומי.

 

[ןן גיל ןן]

דווקא נראה לי שיש בעיה בהוכחה.

החלק שבו אתה אומר שניתן להניח בה"כ שכל הקבוצות הם בעלות אותה עוצמה לא מנומק היטב, לדעתי. כי אם למשל בקבוצה הגדולה שביניהן יש n-1 איברים אז אי אפשר להוסיף איברים לכל אחת מהקבוצות כך שבכולן יהיו n-1 איברים וכל הקבוצות המתקבלות יהיו שונות. אסטרטגיה אחרת להוכיח ש- k הוא חסם עליון על מספר הקבוצות האפשרי ללא הכלות הוא לכסות את אוסף התת-קבוצות של {2,1,..n} על ידי k שרשראות (שרשרת הוא אוסף תת קבוצות כך שעבור כל שתי קבוצות באוסף, אחת מהן מכילה את השניה). וכך, אם יש k+1 תת קבוצות אז שתיים מהן חייבות להיות באותה השרשרת (ע"פ עיקרון שובך היונים) ולכן מוכלות זו בזו.

 

[עריסטו]

התכוונתי שניתן להניח שבקבוצה הגדולה

יש לא יותר מ - n/2 איברים, שהרי אם זה לא כך ניתן לקחת במקום כל קבוצה את המשלים שלה. אם זה כך אין את הבעיה שכתבת.

 

[ןן גיל ןן]

הבעיה עדיין קימת

שכן ייתכן מצב שבו ישנן גם קבוצות בנות פחות מ- n/2 איברים וגם קבוצות בנות יותר מ- n/2 איברים. ובמצב זה לקיחת המשלים של כל הקבוצות לא תעזור. כמו כן, גם אם כל הקבוצות בנות פחות מ- n/2 איברים, עדיין יש לתאר את הדרך שבה משלימים כל קבוצה לקבוצה גדולה יותר, ולהוכיח שבאמת יתקבלו קבוצות שונות.