אין חידות חדשות, אפילו לא חידה לקראת התחרות ה – 3

עמוד

ברוכים הבאים לאתר תחרויות קודגורו! פורומים חידות אין חידות חדשות, אפילו לא חידה לקראת התחרות ה – 3

מוצגות 11 תגובות – 1 עד 11 (מתוך 11 סה״כ)
  • מאת
    תגובות
  • #77293
    המאוכזב
    משתתף

    וחבל שכך..

    #78904
    CodeGuru
    מנהל בפורום

    כותרת: חידה לקראת התחרות החדשה
    בflyer החדש שיופץ לקראת התחרות יש, כמו כל שנה, חידה חדשה.
    החידה בשנה הראשונה הייתה בשפת C, בשנה השניה בשפת PASCAL,
    והשנה היא ללא שפה מוגדרת.
    השאלה היא מה השארית של מכפלת 2000 המספרים הטבעיים הראשונים
    (1*2*3*4*5*….*2000) בחלוקה ל 2003?
    אתם מוזמנים לשלוח רעיונות, תוכניות שמנסות לפתור, רעיונות
    מתימטיים, או כל הארה אחרת על השאלה.
    בהצלחה.
    CodeGuru

    #78905
    Michael
    משתתף

    כותרת: re: solution
    I suppose that this one should do:

    int main(void)
    {
    clrscr();
    unsigned long res = 1;
    for(int i=1;i!=2001;i++){
    res*=i; res = res%2003;
    }
    cout << res << endl;
    return 0;
    }

    The output for this function is 1001

    BTW, it really takes a codeguru to write English in this forum,
    and I am not one….

    #78914

    כותרת: פתרון אפשרי
    אם נבדוק את שארית החלוקה של עצרת של מספרים זוגיים (נסמן ב – N)
    ב (N+3) כאשר N+3 ראשוני (ושלילי) נגלה כי השארית היא מחצית של N+2, לכן השארית במקרה זה תהיה 2/(2000+2)לכן 1001.

    #78915
    CodeGuru
    מנהל בפורום

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

    #78919
    אורן בקר
    משתתף

    כותרת: פתרון
    Let´s prove it for the general case of (p-3)! mod p, when p>=3 is prime.

    Zp is a field. Therefore each a#0 in Zp has a unique b in Zp such as that ab=1.
    Now, in Zp:
    (p-1)*(p-1)=p(p-1)-(p-1)=p(p-2)+1=1.
    (p-2)*[(p-1)/2]=(p(p-3)+2)/2=2/2=1.

    Therefore 1*…*(p-3) has a unique reciprocal for each factor except for (p-1)/2.
    That means that (p-3)!=1*…*(p-3)=(p-1)/2.

    Therefore (p-3)! mod p = (p-1)/2.

    Oren.

    p.s: For guys not familiar with the terms, search for some basic linear algebra text and for Euclid´s extended algorithm.

    #78920
    אורן בקר
    משתתף

    כותרת: הבהרה
    בקשר להוכחה שלי, שכחתי לציין שמכיוון שלפולינום x^2 לא ייכתנו יותר משני שורשים (p-1, 1 במקרה של Zp), כל גורם במכפלה מתבטל עם גורם *אחר*, חוץ מ – 1, שאותו כבר אפשר לראות כ"מבוטל", ו p-1)/2)שהוא התשובה הסופית (אחרת אפשר לחשוב שיש עוד מספרים שההופכי שלהם זה הם עצמם ולכן הם לא יתבטלו).

    #78921
    אורן בקר
    משתתף

    כותרת: תיקון
    הפולינום הוא כמובן x^2-1 ואני מקווה שלא עשיתי עוד שגיאות הדפסה / שגיאות רעיוניות.

    #78922
    CodeGuru
    מנהל בפורום

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

    #78923

    כותרת: תיקון לתיקון
    I have a minor correction to Oren´s proof (which I find very elegant). The fundamental theorem of algebra is formulated for C &times; C, and while I believe it can be somehow adjusted to field algebra, there´s a simpler way.

    Lemma: For every natural n, (x ^ 2) mod (p – 1) = 1 only if x mod p = 1 or x mod p = p – 1.

    Proof: Let´s persume x is not equal to either 1 or p – 1. Let´s make an equation:
    x ^ 2 = np + 1
    x ^ 2 – 1 = np
    (x + 1)(x – 1) = np

    One of the two numbers, x + 1 or x – 1 has to be devidable by p. Because of that, either x mod p = 1 or x mod p = p – 1. We´ve reached a contradiction, and that´s why x has to be either 1 or p – 1.

    Application of the lemma to multiplicative field over Zp: for every x´ belonging to the field, x´ * x´ = 1 only if x´ = 1 or x´ = p – 1.

    #78924

    כותרת: תיקון לתיקון של עצמי
    What I meant to say is that the fundamental theorem of algebra is formulated for <i>polynomials</i> whose coefficients are complex (belong to C). Moreover, I forgot to mention that n is natural and p is prime.

    This is what happens when one tries to be excessively fundamentalist in proofs written around 10 P.M. Hopefully this 11 P.M. fix will do. :-)

מוצגות 11 תגובות – 1 עד 11 (מתוך 11 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.