2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

Συντονιστές: cretanman, ΔΗΜΗΤΡΗΣ ΙΩΑΝΝΟΥ, socrates

Datis-Kalali
Δημοσιεύσεις: 110
Εγγραφή: Δευ Δεκ 12, 2016 5:33 pm
Τοποθεσία: Λευκωσία

2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#1

Μη αναγνωσμένη δημοσίευση από Datis-Kalali » Κυρ Σεπ 03, 2017 5:51 pm

1)Έχουμε n+1 θέσεις A_1,A_2,...,A_n και O (n\ge 3) με πεπεράσμενο πλήθο κάρτες. Σε κάθε βήμα μπορούμε να κάνουμε ένα απο τα εξής βήματα:
i. Αν στην θέση A_i έχουμε τουλάχιστον 3 κάρτες, τότε μπορούμε να πάρουμε 3 κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις A_{i+1} , A_{i-1} και O. (Θεωρούμε A_0=A_n και A_{n+1}=A_1)
ii. Αν στην θέση O έχουμε τουλάχιστον n κάρτες, τότε μπορούμε να πάρουμε n κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της n θέσεις A_1 , A_2,..., A_n.
Να δείξετε ότι αν έχουμε τουλάχιστον n^2+3n+1 κάρτες συνολίκα, τότε μέτα απο ένα πεπερασμένο πλήθο βήματων, μπορούμε να να έχουμε τουλάχιστον n+1 σε κάθε θέση.
(Πήγη: Περσική ιστοσελίδα μαθηματικών)
2)Να βρείτε όλοι οι τετραψηφίο αριθμοί \overline{abcd}, έτσι ώστε:
\overline{abcd}=(\overline{ac}+1)(\overline{bd}+1)
(Πήγη: Ολυμπιάδα Czech 2000)



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7946
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Σεπ 05, 2017 11:35 am

Datis-Kalali έγραψε:1)Έχουμε n+1 θέσεις A_1,A_2,...,A_n και O (n\ge 3) με πεπεράσμενο πλήθο κάρτες. Σε κάθε βήμα μπορούμε να κάνουμε ένα απο τα εξής βήματα:
i. Αν στην θέση A_i έχουμε τουλάχιστον 3 κάρτες, τότε μπορούμε να πάρουμε 3 κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της θέσεις A_{i+1} , A_{i-1} και O. (Θεωρούμε A_0=A_n και A_{n+1}=A_1)
ii. Αν στην θέση O έχουμε τουλάχιστον n κάρτες, τότε μπορούμε να πάρουμε n κάτρες απο αυτή την θέση και να προσθέτουμε μία κάρτα σε κάθε απο της n θέσεις A_1 , A_2,..., A_n.
Να δείξετε ότι αν έχουμε τουλάχιστον n^2+3n+1 κάρτες συνολίκα, τότε μέτα απο ένα πεπερασμένο πλήθο βήματων, μπορούμε να να έχουμε τουλάχιστον n+1 σε κάθε θέση.
(Πήγη: Περσική ιστοσελίδα μαθηματικών)
Αρχικά επαναλαμβάνουμε το βήμα (i) για όσα περισσότερα βήματα μπορούμε. Αυτή η διαδικασία θα τελειώσει επειδή το άθροισμα των καρτών στα A_1,\ldots,A_n μειώνεται κάθε φορά που εκτελούμε το βήμα (i).

Μπορούμε λοιπόν να καταλήξουμε σε μια κατάσταση όπου σε κάθε θέση A_i θα έχουμε από 0 μέχρι 2 κάρτες. Τώρα επαναλαμβάνουμε το βήμα (ii) μέχρις ούτω να συμβεί ένα από τα πιο κάτω
(α) Σε κάθε θέση A_i υπάρχουν τουλάχιστον n+1 κάρτες.
(β) Δεν μπορούμε πλέον να επαναλάβουμε το βήμα (ii) επειδή δεν υπάρχουν αρκετές κάρτες στην θέση O.

Ισχυρίζομαι ότι αυτό που θα συμβεί είναι το (α), πιθανώς ταυτόχρονα με το (β). Πράγματι αν δεν συμβεί το (α), τότε θα υπάρχει k \leqslant n ώστε σε κάθε θέση A_i να έχω από k μέχρι k+2 κάρτες, ενώ στην θέση O να έχω το πολύ n-1 κάρτες. Τότε όμως συνολικά θα είχα το πολύ

\displaystyle{ n(k+2) + n-1 \leqslant n(n+2) + n-1 = n^2+3n-1}

κάρτες, άτοπο.

Είμαι τώρα σε μια κατάσταση όπου
(Α) Κάθε θέση A_i έχει από n+1 έως n+3 κάρτες.
(Β) Υπάρχει τουλάχιστον μια θέση A_i με ακριβώς n+1 κάρτες.

Βρίσκω τώρα, αν υπάρχει, ακολουθία θέσεων A_i,A_{i+1},\ldots,A_{i+k} ώστε
(1) Στα A_i,A_{i+k} υπάρχουν από n+3 κάρτες.
(2) Στα A_{i+1},\ldotsA_{i+k-1} υπάρχουν από τουλάχιστον n+2 κάρτες.
(3) Δεν υπάρχουν n+3 κάρτες ούτε στο A_{i-1} ούτε στο A_{i+k+1}.

Τότε εκτελώ το βήμα (i) διαδοχικά στις θέσεις A_i,A_{i+1},\ldots,A_{i+k}. Τότε στις θέσεις A_i,A_{i+k} θα μειωθεί το πλήθος των καρτών κατά 2, στις θέσεις A_{i+1},\ldots,A_{i+k-1} θα μειωθεί το πλήθος των καρτών κατά 1, και στις θέσεις A_{i-1},A_{i+k+1} θα αυξηθεί το πλήθος των καρτών κατά 1. Άρα πάλι θα είμαστε σε μια κατάσταση όπου τα (Α) και (Β) ισχύουν. [Πρέπει να ελέγξουμε τι συμβαίνει αν A_{i-1} = A_{i+k+1} διότι τότε το πλήθος των καρτών σε αυτήν την θέση θα αυξηθεί κατά 2. Αλλά σε αυτήν την περίπτωση αυτή η θέση θα είχε αρχικά n+1 κάρτες λόγω του (Β).

Επειδή όποτε εκτελώ το πιο πάνω, το πλήθος των καρτών στις θέσεις A_1,\ldots,A_n μειώνεται, εν τέλει θα καταλήξω σε μια κατάσταση όπου ισχύουν τα (Α) και (Β) αλλά δεν υπάρχει ακολουθία θέσεων A_i,A_{i+1},\ldots,A_{i+k} ώστε να ισχύουν τα (1),(2),(3).

Αυτό σημαίνει ότι το πλήθος των θέσεων με n+1 κάρτες είναι μεγαλύτερο ή ίσο από το πλήθος των θέσεων με n+3 κάρτες. Αυτό ισχύει διότι κάθε φορά που έχω μια θέση με n+3 κάρτες, η αμέσως επόμενη θέση που δεν έχει n+2 κάρτες θα πρέπει να έχει n+1 κάρτες. (Χρησιμοποιούμε επίσης ότι υπάρχει τουλάχιστον μια θέση με n+1 κάρτες.)

Άρα το συνολικό πλήθος καρτών στις θέσεις A_1,\ldots,A_n είναι το πολύ n(n+2) = n^2+2n. Αλλά τότε στην θέση O υπάρχουν τουλάχιστον n+1 κάρτες. Άρα το ζητούμενο αποδείχθηκε.


ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ
Δημοσιεύσεις: 33
Εγγραφή: Τετ Μάιος 03, 2017 12:37 am

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#3

Μη αναγνωσμένη δημοσίευση από ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ » Τρί Σεπ 12, 2017 11:13 pm

Όσο για το 2 θέμα, δεν γνωρίζω πως να γράψω την λύση μου σε μορφή latex.Μηπώς μπορεί κάποιος να με βοηθήσει σχετικά με το να βρω κάπου οδηγίες :roll: .Ευχαριστώ


Άβαταρ μέλους
Γιάννης Μπόρμπας
Δημοσιεύσεις: 212
Εγγραφή: Τρί Δεκ 13, 2016 10:41 pm
Τοποθεσία: Χανιά

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#4

Μη αναγνωσμένη δημοσίευση από Γιάννης Μπόρμπας » Τετ Σεπ 13, 2017 2:19 pm

Γεια σου Ανδρέα, αυτό το λινκ θα σε βοηθήσει:
Latex


Γιάννης Μπορμπαντωνάκης
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7946
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Σεπ 13, 2017 3:07 pm

Υπάρχουν επίσης κάποιες λίγο πιο εισαγωγικές οδηγίες εδώ.

Η κύρια διαφορά είναι ότι ο σύνδεσμος του Γιάννη δίνει οδηγίες για γράψιμο σε \LaTeX στον υπολογιστή σου που είναι κάπως πιο δύσκολο στο ξεκίνημα. Από εκείνον τον σύνδεσμο αγνόησε οτιδήποτε μιλάει για packages και \usepackage. Πολλά από αυτά τα «πακέτα» είναι ήδη φορτωμένα στο :logo: και δεν χρειάζεται να δηλωθούν περαιτέρω όπως όταν γράφουμε στον υπολογιστή μας.


ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ
Δημοσιεύσεις: 33
Εγγραφή: Τετ Μάιος 03, 2017 12:37 am

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#6

Μη αναγνωσμένη δημοσίευση από ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ » Τετ Σεπ 13, 2017 4:43 pm

Ευχαριστώ πολύ Γιάννη και κύριε Δημήτρη :D


Άβαταρ μέλους
grigkost
Διαχειριστής
Δημοσιεύσεις: 2696
Εγγραφή: Πέμ Δεκ 18, 2008 12:54 pm
Τοποθεσία: Ιωάννινα

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#7

Μη αναγνωσμένη δημοσίευση από grigkost » Τετ Σεπ 13, 2017 5:35 pm

ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ έγραψε:
Τρί Σεπ 12, 2017 11:13 pm
Όσο για το 2 θέμα, δεν γνωρίζω πως να γράψω την λύση μου σε μορφή latex. Μηπώς μπορεί κάποιος να με βοηθήσει σχετικά με το να βρω κάπου οδηγίες ...
Εκτός των συνδέσμων που ανέφεραν ο Δημήτρης και ο Γιάννης, ένας εύκολος τρόπος για να έχουμε τον κώδικα \rm\LaTeX που θέλουμε είναι με την χρήση του EqEditor. Αυτός εμφανίζεται (σε ξεχωριστό παράθυρο) όταν πατάμε το κουμπί EqEditor που βρίσκεται στην μπάρα του παραθύρου δημοσίευσης.
  • Χρησιμοποιώντας τα κατάλληλα κουμπιά του EqEditor στο ορθογώνιο πλαίσιό του εμφανίζεται ο κώδικας \rm\LaTeX ενώ από κάτω εμφανίζεται ο μαθηματικός τύπος που αντιστοιχεί στον κώδικα.
  • Όταν γράψουμε τον μαθηματικό τύπο που θέλουμε, αντιγράφουμε τον κώδικα από το ορθογώνιο πλαίσιο και το επικολλούμε στο παράθυρο της δημοσίευσή μας βάζοντάς τον ανάμεσα σε δυο δολλάρια (ή τον επικολλούμε, τον "επιλέγουμε" με το ποντίκι και πατάμε το κουμπί tex).


{\color{dred}\Gamma\!\rho\,{\rm{H}}\gamma\varnothing\varrho{\mathscr{H}}\varsigma \ {\mathbb{K}}\,\Omega\sum{\rm{t}}{\mathscr{A}}\,{\mathbb{K}}\!\odot\varsigma
ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ
Δημοσιεύσεις: 33
Εγγραφή: Τετ Μάιος 03, 2017 12:37 am

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#8

Μη αναγνωσμένη δημοσίευση από ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ » Πέμ Σεπ 14, 2017 12:42 am

Αρχικά,έχουμε : 1000\alpha+100\beta+10\gamma +\delta=\left ( 10\alpha +\gamma +1 \right )\cdot \left ( 10\beta +\delta+1)       
\Leftrightarrow                          
 
10\alpha \cdot \left [ 99-\left ( 10\beta +\delta \right ) \right ]+10\beta \cdot (9-\gamma )+\gamma\cdot \left ( 9-\delta \right )= 1

Το οποίο είναι Αδύνατο.Άρα δεν υπάρχει τετραψηφίος που να ικανοποιεί την συγκεκριμένη σχέση.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7946
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: 2 ασκήσεις για διαγωνισμούς- Συνδυαστική και θεωρία αριθμών

#9

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Σεπ 14, 2017 9:09 am

ΑΝΔΡΕΑΣ ΛΑΜΠΡΟΥ έγραψε:
Πέμ Σεπ 14, 2017 12:42 am
Αρχικά,έχουμε : 1000\alpha+100\beta+10\gamma +\delta=\left ( 10\alpha +\gamma +1 \right )\cdot \left ( 10\beta +\delta+1)       
\Leftrightarrow                          
 
10\alpha \cdot \left [ 99-\left ( 10\beta +\delta \right ) \right ]+10\beta \cdot (9-\gamma )+\gamma\cdot \left ( 9-\delta \right )= 1

Το οποίο είναι Αδύνατο.Άρα δεν υπάρχει τετραψηφίος που να ικανοποιεί την συγκεκριμένη σχέση.
Σωστά. Ας γράψουμε όμως περισσότερες λεπτομέρειες για να το δουν και οι υπόλοιποι.

Το

\displaystyle  10\alpha\left [ 99-\left ( 10\beta +\delta \right ) \right ]+10\beta (9-\gamma )

είναι πολλαπλάσιο του 10 και μη αρνητικό. Το \gamma\left ( 9-\delta \right ) είναι μη αρνητικό.

Άρα αναγκαστικά πρέπει

\displaystyle  10\alpha\left [ 99-\left ( 10\beta +\delta \right ) \right ]+10\beta (9-\gamma ) = 0

και

\displaystyle \gamma\left ( 9-\delta \right ) = 1

Από αυτά είναι τώρα εύκολο να καταλήξουμε στα \gamma=1,\delta=8 από την δεύτερη ισότητα, και μετά \alpha=0,\beta=0 από την πρώτη.

Άρα η μόνη επιλογή είναι ο αριθμός 0018. Το κατά πόσο είναι επιτρεπτή ή όχι εξαρτάται και από την εκφώνηση. Εφόσον μιλάει για τετραψήφιους, κανονικά πρέπει να την απορρίψουμε.


Απάντηση

Επιστροφή σε “Θέματα διαγωνισμών (ΕΜΕ, BMO, JBMO, IMO, Kangaroo κλπ)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: nikos_el και 3 επισκέπτες