Τρίτη 29 Μαρτίου 2016

Ένα τουλάχιστον

Γράφουμε τα στοιχεία του συνόλου S = {1, 2, 3, ... ,100} σε ένα πίνακα τύπου 10x10 ως εξής:
1   2   3 • • • 10 
11 12 13 • • • 20
..............
91 92 93 • • • 100
Αν με οποιονδήποτε τρόπο απαλείψουμε 10 στοιχεία του πίνακα, να αποδείξετε ότι οι 90 αριθμοί που απομένουν περιέχουν ένα τουλάχιστον σύνολο 10 διαδοχικών όρων αριθμητικής προόδου.
Μαθηματική Ολυμπιάδα Ρουμανίας 2009
 Διασκεδαστικά Μαθηματικά    www.eisatopon.blogspot.com     

2 σχόλια:

  1. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

    ΑπάντησηΔιαγραφή
  2. Κάθε γραμμή και κάθε στήλη του πίνακα αποτελείται από 10 όρους αριθμητικής προόδου. Επομένως, στην περίπτωση που ανάμεσα στους 10 απαλειφόμενους αριθμούς υπάρχουν δύο τουλάχιστον που ανήκουν στην ίδια γραμμή ή την ίδια
    στήλη, θα υπάρχει οπωσδήποτε γραμμή ή στήλη χωρίς κανέναν απαλειφόμενο, άρα και σύνολο με 10 όρους αριθμητικής προόδου.
    Για να μη συμβεί αυτό, θα πρέπει κάθε γραμμή και κάθε στήλη να περιέχει ένα ακριβώς απαλειφόμενο στοιχείο.
    Διατάσσουμε τους απαλειφόμενοες αριθμούς σε αύξουσα σειρά Α1<Α2<...<Α10.
    Αν δύο διαδοχικοί στη διάταξη απαλειφόμενοι έχουν διαφορά μεγαλύτερη του 10, τότε ανάμεσά τους θα υπάρχουν τουλάχιστον 10 διαδοχικοί ακέραιοι που αποτελούν επίσης όρους αριθμητικής προόδου. Αν υπάρχουν δύο διαδοχικοί στη διάταξη με διαφορά ακριβώς 10, τότε αυτοί θα ανήκουν στην ίδια στήλη, πράγμα που αποκλείσαμε ήδη. Επομένως η μέγιστη διαφορά ανάμεσα σε δύο διαδοχικούς στη διάταξη απαλειφόμενους είναι 9.
    Σε αυτή την περίπτωση, αν υπάρχει διαφορά δύο διαδοχικών στη διάταξη απαλειφόμενων 8 ή μικρότερη, τότε ο μέγιστος απαλειφόμενος δεν μπορεί να είναι μεγαλύτερος από 10+9*9-1=90, οπότε η τελευταία γραμμή δεν περιέχει απαλειφόμενο στοιχείο, πράγμα που έχουμε αποκλείσει.
    Η μόνη περίπτωση που απομένει είναι αυτή στην οποία όλες οι διαφορές μεταξύ διαδοχικών στη διάταξη απαλειφόμενων είναι ακριβώς ίσες με 9.
    Τότε στη μεν περίπτωση που ο μικρότερος απαλειφόμενος είναι μικρότερος του 10, ο μεγαλύτερος είναι το πολύ ο 9+9*9=90, οπότε απομένει ολόκληρη η τελευταία γραμμή χωρίς απαλειφόμενο στοιχείο, πράγμα που αποκλείσαμε, ενώ στην περίπτωση που ο μικρότερος απαλειφόμενος είναι ο 10, το σύνολο των απαλειφόμενων είναι το {10,19,28,37,46,55,64,73,82,91}. Στην περίπτωση αυτή ένα σύνολο με 10 όρους αριθμητικής προόδου είναι το {9,18,27,36,45,54,63,72,81,90}.
    Επομένως, σε κάθε περίπτωση ισχύει το αποδεικτέο.

    ΑπάντησηΔιαγραφή