Πέμπτη, 24 Νοεμβρίου 2016

Χαλασμένα αντίγραφα

Ενας μαθητής έλυσε όλα τα προβλήματα ενός μαθηματικού περιοδικού. Πριν ταχυδρομήσει τις απαντήσεις του στους συντάκτες της στήλης, τις έδωσε σε δύο φίλους του για να τις αντιγράψουν.
Την επόμενη ημέρα, οι δύο μαθητές αντέγραψαν τις λύσεις με σκοπό να τις ταχυδρομήσουν και αυτοί στο περιοδικό ως δικές τους. Ευτυχώς ή δυστυχώς, ο καθένας τους έκανε κάποια (διαφορετικά) λάθη αντιγραφής.
Πριν ταχυδρομήσουν τις αντιγραμμένες λύσεις, οι δύο μαθητές έδωσαν και αυτοί τις απαντήσεις σε τέσσερις άλλους μαθητές (ο καθένας σε δύο φίλους του). 
Την επόμενη ημέρα, αυτοί οι τέσσερις μαθητές επανέλαβαν τη διαδικασία, και ούτω καθεξής. Κάθε νέο αντίγραφο διατηρούσε τα παλιά λάθη και ίσως είχε και μερικά καινούργια. Γνωρίζουμε ότι μια μέρα κάθε νέο αντίγραφο θα περιέχει τουλάχιστον δέκα λάθη. 
Αποδείξτε ότι κάποια μέρα θα γίνουν, συνολικά, τουλάχιστον έντεκα καινούργια λάθη στα αντίγραφα. 

2 σχόλια:

  1. Αν οι 2 αντιγραφείς της 1ης γεννιάς έκαναν χ1 και χ2 λάθη αντιστοίχως, τότε το μέσο πλήθος λαθών ανά αντίγραφο της 1ης γεννιάς είναι (χ1+χ2)/2.
    Αν οι 4 αντιγραφείς της 2ης γενιάς έκαναν χ11, χ12, χ21, χ22 νέα λάθη αντιστοίχως, τότε των μέσο πλήθος παλιών και νέων λαθών ανά αντίγραφο της 2ης γεννιάς είναι:
    [(χ1+χ11)+(χ1+χ12)+(χ2+χ21)+(χ2+χ22)]/4 = (χ1+χ2)/2 + (χ11+χ12+χ21+χ22)/4. Επαναλαμβάνοντας το ανάλογο και για τις επόμενες γεννιές, εύκολα διαπιστώνουμε ότι το μέσο πλήθος παλιών και νέων λαθών των αντιγράφων κάθε τρέχουσας γεννιάς είναι ίσο με το μέσο πλήθος λαθών των αντιγράφων της αμέσως προηγούμενης γενιάς συν το μέσο πλήθος των νέων λαθών της τρέχουσας γενιάς.
    Έστω ότι καμία μέρα δεν έγιναν συνολικά 11 ή περισσότερα λάθη. Τότε τα 2 αντίγραφα της 1ης γεννιάς θα περιέχουν το πολύ 10/2=5 λάθη κ.μ.ό. το καθένα, τα 4 αντίγραφα της 2ης γεννιάς το πολύ 5+10/4=7,5 λάθη κ.μ.ό. το καθένα, τα 8 αντίγραφα της 3ης γεννιάς το πολύ 7,5+10/8=8,75 λάθη κ.μ.ό το καθένα κ.ο.κ. Συνεπώς, σε πεπερασμένο αριθμό γεννεών αντιγραφής, το μέσο πλήθος λαθών ανά αντίγραφο της οποιασδήποτε γεννιάς είναι αυστηρά μικρότερο από 5/(1-1/2)=10 (το άθροισμα απείρων όρων φθίνουσας γ.π. με πρώτο όρο το 5 και λόγο 1/2).
    Αφού όμως υπάρχει γεννιά που κάθε αντίγραφό της περιέχει τουλάχιστον 10 λάθη, ο  μέσος όρος λαθών ανά αντίγραφο αυτής της γεννιάς δεν μπορεί να είναι μικρότερος από 10. Αντίφαση, επομένως υπήρξε μέρα που έγιναν τουλάχιστον 11 λάθη συνολικά.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Ή διαφορετικά
      Έστω Λ1, Λ2, ..., Λν οι συνολικοί αριθμοί νέων λαθών κάθε γενιάς αντιγράφων. Δεδομένου ότι η γενιά ν περιλαμβάνει συνολικά 2^ν αντίγραφα, οι συνολικές εμφανίσεις λαθών στα αντίγραφά της θα είναι:
      Σ = 2^ν/2*Λ1 + 2^ν/4*Λ2 + 2^ν/8*Λ3 + .... + Λν
      (Κάθε λάθος της 1ης γενιάς εμφανίζεται στο 1/2 των τελικών αντιγράφων, κάθε λάθος της 2ης γενιάς στο 1/4, ..., κάθε λάθος της τελευταίας γενιάς σε 1 αντίγραφο)
      Αν δεν υπάρχουν 11 ή περισσότερα νέα λάθη σε καμία μέρα, δηλαδή αν έχουμε Λν ≤ 10 για κάθε γενιά ν, τότε θα πρέπει:
      Σ ≤ 2^ν/2*10 + 2^ν/4*10 + 2^ν/8*10 + .... + 10 =
      10*(2^ν/2+2^ν/4+2^ν/8+...+1) = 10*(2^ν-1) =>
      Σ< 10*2^ν για κάθε ν
      Γνωρίζουμε όμως ότι υπάρχει γενιά ν που όλα της τα αντίγραφα περιέχουν 10 τουλάχιστον λάθη το καθένα, οπότε οι συνολικές εμφανίσεις λαθών στα αντίγραφά της είναι Σ ≥ 10*2^ν.
      Άτοπο, οπότε υπήρξε μέρα που έγιναν 11 τουλάχιστον νέα λάθη.

      Διαγραφή