שרשור יום ג' 3.8

[tomash19888]

שאלון 053005

והספר הוא של מריאן רוזנפלד ואדית כהן. שמו הוא "מאגר שאלות במתמטיקה ברמת 5 יחידות לימוד"

 

[duvdevanim]

גם לי יש את הספר הזה.

ולדעתי- הוא ברמה גבוהה מידי בשביל שאלון 05.

 

[הזחל הכחול]

שרשור יום ג' 3.8

 

[הזחל הכחול]

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

שלום, קיבלתי את השאלה הבאה... כיצד תסדר בלוח 6X6 6 צריחים שונים כך שלא יאיימו זה על זה וכיצד עם יש 2 זהים אדומים ו-4 זהים כחולים... (אני מניח שהכוונה היא שזהים לא מאיימים אחד על השני)... אז ככה, את הסעיף הראשון אני חושב שפתרתי... לצריח הראשון יש 36 אפשרויות לשני 25 וכ'... והתשובה היא: 36X25X16X9X4X1 אין לי מושג איך לגשת לסעיף ב'... אודה על כל עזרה.

 

[Damnthiscow]

לדעתי הפתרון קצת אחר

פתרון לסעיף א': ברור שצריך לשים צריח בכל טור. אז נשחק עם הסדר של הטורים, כלומר: דמיין שאתה מסדר אותם באלכסון- עכשיו תתחיל להחליף טורים, כל החלפת טור עדיין טובה לנו, כמה אפשריות יש לסדר 6 טורים בשורה? : סך כל האפשרויות הם 6! או בעברית 6 עצרת. ברעיון שלך אתה סופר אפשרויות יותר מפעם אחת כי הצריחים זהים.

 

[yuvalmadar]

לדעתי הוא דווקא צדק

כיוון שאתה לא צריך לבחור רק את הטור של הצריח אלא גם את המיקום שלו באותו טור. בנוגע לחלק השני, אתה בעצם סופר במקור כמה פעמים את הסידורים השונים של הארבעה הזהים (כלומר, יש 4! אפשרויות במקום אפשרות אחת - צריך לחלק ב4!), ולפי אותו הגיון יש להחשיב את כל הסידורים של השניים הזהים (2! אפשרויות) כסידור אחד. לכן, יש לחלק את התוצאה שיצאה לך בסעיף הראשון ב4! וב 2!, כלומר ב- 1*2*1*2*3*4=48

 

[הזחל הכחול]

תודה

 

[הזחל הכחול]

רגע רגע, לא הבנתי

כאשר יש צריחים זהים, ז"א הם יכולים להיות במקומות שצריח שונה לא יכול להיות (תחום החסימה של הצריח הדומה)... מכאן שצריכות להיות יותר אפשרויות ולא פחות... בדקתי את זה עבור 3X3 כאשר כל הצריחים שונים כמו קודם: 9X4X1 = 36 כאשר נניח יש שניים זהים(נאמר אדומים ואחד כחול), יתכנו מסי מצבים: 1. להכנסת האדום הראשון 9 אפשרויות כעת, אם האדום השני נכנס באותו תחום של האדום הראשון יש 4 אפשרויות כאלה אזי לצריח הכחול יש 2 אפשרויות - סה"כ 9X4X2 = 72 אם האדום השני, נכנס בתחום שלא מאיים על האדום הראשון, ויש גם 4 אפשרויות כאלה וכעת לכחול יש אפשרות 1 - סה"כ 9X4X1=36 סה"כ האפשרויות במקרה זה: 108 2. כעת, במידה והכחול הוא הראשון אזי יש לו 9 אפשרויות לאדום הראשון יש 4 אפשרויות ולאדום השני יש 3 אפשרויות סה"כ 9X4X3 = 108 אפשרויות סה"כ 216 אפשרויות ================= קודם כל תודה למי שקרא את כל זה, עכשיו איך לעזאזל אני מסביר את זה הגיונית וקצר ועוד עבור לוח 6X6 (עם 4 אדומים ו-2 כחולים) תודה מראש.....

 

[דפנה ר]

כן אבל כפית סדר לכן צריך לחלק ב n!

והפתרון הוא עבור לוח nxn n! עבור החלק הראשון של השאלה

ובאופן דומה החלק השני

 

[דפנה ר]

אופס הצריחים שונים ../images/Emo10.gif ביטול!

 

[מוקטן]

שים לב,

ציינתי בשאלה שהצריחים שונים זה מזה...

 

[db6]

אני זקוק לעזרה במשהו שאני לא מבין..

יש לי את הנוסחה הבאה באיזשהו ספר:

e*d=1(mod(p-1)*(q-1))​

עכשיו, ידועים לי הערכים של המשתנים, אבל זה פשוט לא עובד. הערכים: p=17 q=11 e=7 דרך המשוואה אמורים לגלות את הערך של d, שהוא 23. איך? בכל אופן, במשפט מתחת למשוואה כתוב: "הסקת הערך של d איננה עניין פשוט, אבל טכניקה המכונה האלגוריתם של אוקלידס מאפשרת למצוא את d במהירות ובקלות" למי מיכם יש מושג מה זה אומר, ואיך אני יכול להגיע לערך של d כמו שצריך? אני פשוט צריך לדעת, כדי להשתמש במשוואה גם לp,q ו e אחרים... תודה לכולכם. db6

 

[rainbow16]

הנה

יוצא

7*d=1mod(160)​

כדי ש7d יהיה גם 1, הוא צריך להיות שווה או 1 או 161 או 321 (כלומר, כפולה של 160 [0,160,320 וכו'] ועוד 1). כל מה שאתה צריך למצוא עכשיו, זה מספר d כך ש7d יהיה שווה אחד מהמספרים הללו. נבדוק: 0*7=0 לא טוב 1*7=7 לא טוב ... 23*7=161 וזה כן טוב! (זה כפולה של 160, ועוד 1) לכן d=23.

 

[1ca1]

לא נכון

לא בודקים אחד אחד אני יביא לך מספרים כמו 2 בחזקת 100 מוד 5000 תתחיל לבדוק את כל המחלקים? דרך אגב אפשר להגיד שהספר המדובר הוא סודות ההצפנה, זה לא משהו סודי... צריך להשתמש באלגוריתם אוקלידס דבר ראשון נתחיל עם כמה עובדות בסיסיות מתורת המספרים אם

gcd(a,b)=d אז קיימים u,v שלמים ככה שמתקיים au+bv=d​

עובדה שנייה

gcd(a,b)=1 <=> a,b זרים​

כלומר הgcd של מספרים זרים (relativity primes) הוא 1... לכן בשילוב שני העובדות נקבל

אם a,b זרים au+bv=1 עכשיו נעשה mod a ונקבל כי bv=1 ולכן b^-1=v mod a לכן אנחנו צריכים לפתור את הבעיה eu+dv=1 עכשיו נשתמש באלגוריתם של אוקלידס למציאת ה gcd אני ידגים את אלגוריתם אוקלידס ככה יהיה יותר מובן, אני יקח 2 מספרים זרים (שזה מה שדרוש בשיטת ההצפנה RSA) וגם יחסית קטנים שיהיה קל להבין וגם לעקוב אחרי ההצבה לאחור שבעזרתה מגלים את u,v אז ניקח את gcd(7,9) דבר ראשון נחלק את 9 ב 7 בשלמים כלומר 9=1*7+2 עכשיו נחלק את 7 ב 2 7=3*2+1 ועכשיו נחלק את ב1 ונקבל 2=1+1 => gcd(7,9)=1 לכן המספרים זרים כנדרש עכשיו נתחיל במשוואה 1=2-1 ונציב לאחור מהשורה הלפני אחרונה מקבלים 1=7-3*2 ואז 1=2-7+3*2=4*2-7 כעת מהשורה לפני 2=9-7 ולכן 1=4*9-4*7-7=4*9-5*7 ולכן u=4 v=-5 ועכשיו mod 9 נקבל 1mod9=4*(mod9-5*7mod9=-5*7mod9 ולכן 1mod9=-5*7=4*7 זה פחות או יותר העניין מאחורי פיצוח RSA רק שכמובן שמה מדובר על מספרים הרבה הרבה הרבה יותר גדולים (רק היום באלגברה מופשטת בתרגיל פתרתי על הלוח משהו דומה gcd(661,177) משהו כזה , זה דיי ארוך בסביבות 10 שורות עד שמסיימים את כל ההצבה האחורנית , מסכנים שאר הסטודנטים עם כתב כמו שלי )​

 

[rainbow16]

אני אישית לא הבנתי כלום...

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

 

[1ca1]

צודק

נקרא לשיטה שלך "לא מומלצת" דבר שני מה לא הבנת? יש 2 עובדות בסיסיות מתורת המספרים בשילוב עם אלגוריתם אוקלידס (שהוא עוזר למציאת הu,v הנדרשים שמה, וגם מוצא gcd ובקיצור אלגוריתם קצת ומצויין) האלגוריתם אומר ככה

לקבלת gcd של a,b נניח בה"כ a>b אז נחלק את a ב b a=qb+r 0<=r<b אם r=0 אז סיימנו אחרת נחלק את b ב r b=tr+s 0<=s<r אם s=0 אז גמרנו וכך להמשיך עד ש השארית a=q*b+r אז השארית היא r ואז המחלק המשותף המקסימלי הוא b לדוגמא ניקח 2 מספרים לא זרים gcd(24,36) 36=1*24+12 24=2*12 => gcd(24,35)=12 אח"כ בתהליך של הצבה אחורנית ניתן לקבל את u,v וכך גם את ההופכיים​

 

[db6]

מי אמר שסוד?

סתם לא חשבתי שזה יעניין אותכם.... אז ככה... דבר ראשון (סלחו לי על הבורות) מה זה gcd?. עכשיו. אני מנסה לבנות תוכנה להצפנת rsa, סתם כנסיון, לא משהו יותר מדי גדול. בכל אופן, כאמור, אני צריך שהתוכנה תוכל לחשב את d, ולכן אני אשמח מאוד אם תוכל לתת לי נוסחה מדויקת שעל פיה מחשב יכול לעבוד, כי לא הצלחתי להפוך את מה שנתת לנוסחא סגורה. ד"א, אם אתה יכול לצורך העניין להשתמש באותם נעלמים כמו בנוסחא המקורית(p,q,e)אני אשמח מאוד. תודה בכל אופן! db6

 

[IsraeliSecretToilets]

זאת לא נוסחה סגורה..

 

[1ca1]

gcd=greatest common divisor

כלומר מחלק משותף גדול ביותר (מקסימלי) = ממג"ב... הרעיון הוא כזה ניקח 2 מספרים

למשל 144 ו 168 נמצא את הפירוק הראשוני שלהם (שהוא יחיד עד כדי סדר הכפלה) ואז קל לראות את הממג"ב 144=12^2=(3*2^2)^2=2^4*3^2 168=2*84=2^2*42=2^3*21=2^3*3*7 ואז נעבור במחלקים המשותפים וניקח את החזקות המינמליות 2^3*3=24 ואכן 24*6=144 24*7=168 ו 6,7 זרים (מספרים זרים הם מספרים שהגיסידי שלהם הוא 1, כלומר חסרי מחלקים משותפים אם אני לא טועה סינג תירגמו אותו ל"ראשוניים יחסית" משהו כזה בספר) נוסחא סגורה? הייתי הולך על משהו ברקורסיה בסגנון )אני אכתוב בסגנון של פסקל כי בה בטוח אני יודע שיש div=מנה=q mod=שארית=r כאשר a=qb+r ואז נניח a>b אחרת תהפוך ביניהם r<-a mod b כל עוד (b mod r)!=0 בצע: a<-b b<-r r<-a mod b סיים וזהו r=gcd(a,b) אם תרצה להשיג את u,v אולי כדאי לעשות רקורסיה משהו סגנון gcd(a,b) r<-a mod b if (b mod r)!=0 then gcd(b,r); return r; ואז אפשר למשל לשנות קצת דברים ולקבל הצבה לאחור (מאחר שהרקורסיה תצא לתוך חלון אחד "מעליה" אחרי שהיא יצאה ואולי זה דווקא יכול לעזור להצבה לאחור​

 

[db6]

אוקי...

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