Άθροισμα υποσυνόλων αριθμών σε πίνακα

Συντονιστές: Demetres, socrates, silouan

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

Άθροισμα υποσυνόλων αριθμών σε πίνακα

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Μάιος 11, 2017 11:19 am

Έστω ακέραιος t και θετικός ακέραιος n. Στον πίνακα είναι γραμμένοι n διακεκριμένοι ακέραιοι. Ο Βασίλης βρίσκεται σε άλλη αίθουσα χωρίς να βλέπει τον πίνακα και θέλει να μάθει αν υπάρχει υποσύνολο από αυτούς τους αριθμούς με άθροισμα ίσο με t. Ο Αντρέας βλέπει τους αριθμούς στον πίνακα και αρχικά λέει στον Βασίλη το άθροισμα όλων των αριθμών. Από εκεί και έπειτα ο Βασίλης μπορεί σε κάθε κίνηση να λέει μία από τις εξής προτάσεις:
(α) Υπάρχει στον πίνακα γραμμένος ο αριθμός k;
(β) Αν υπάρχει στον πίνακα ο αριθμός k τότε σβήσε τον.
(γ) Αν δεν υπάρχει στον πίνακα ο αριθμός k τότε γράψε τον.
(δ) Μπορούν να χωριστούν οι αριθμοί του πίνακα σε δύο υποσύνολα με ίσο άθροισμα στοιχείων.
Ανάλογα με την πρόταση ο Αντρέας απαντάει αληθώς ή κάνει ότι του ζήτησε ο Βασίλης.

Να δειχθεί ότι σε λιγότερο από 3n κινήσεις, ο Βασίλης μπορεί να ανακαλύψει αν υπήρχαν αρχικά αριθμοί γραμμένοι στον πίνακα με άθροισμα t.

Σημείωση: Εννοείται ότι το άθροισμα των αριθμών ενός κενού συνόλου ισούται με 0.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Άθροισμα υποσυνόλων αριθμών σε πίνακα

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Μάιος 11, 2017 3:15 pm

Θα χρησιμοποιήσουμε επαγωγή στο n.

Για n=1 αρκεί η ερώτηση "Υπάρχει ο n;" και έτσι ισχύει αφού 1 < 3.

Έστω ότι ισχύει για n=k.

Για n=k+1 θεωρούμε το άθροισμα s και κάνουμε την ερώτηση "Υπάρχει ο s - 2t;".

Αν δεν υπάρχει τότε λέμε "Γράψε τον s-2t" και ρωτάμε "Είναι διχοτομήσιμο το σύνολο;" Αν το σύνολο είναι διχοτομήσιμο, τότε τα δύο μέρη έχουν το καθένα άθροισμα s-t. Αφαιρώντας το s-2t από το σύνολο που το περιέχει, έχουμε σύνολο με άθροισμα t και η απάντηση είναι θετική. Αντίστροφα, αν υπάρχει εξ αρχής υποσύνολο με άθροισμα t, τότε το υπόλοιπο έχει άθροισμα s-t και προσθέτοντας το στοιχείο s-2t παίρνουμε διχοτομήσιμο σύνολο. Οπότε αν, μετά την προσθήκη του s-2t, το σύνολο δεν είναι διχοτομήσιμο η απάντηση είναι αρνητική. (Τρεις κινήσεις).

Αν υπάρχει ο s-2t τότε λέμε "Σβήσε τον s-2t". Το σύνολο που μένει έχει άθροισμα 2t. Ρωτάμε "Είναι διχοτομήσιμο;" Αν ναι, τότε κάθε ένα από τα μέρη θα έχει άθροισμα t και η απάντηση είναι θετική. Αν όχι, τότε υπάρχει ακόμα η περίπτωση να σχηματιζόταν σύνολο αθροίσματος t που περιέχει το s-2t που διαγράψαμε. Αν είναι έτσι, το καινούριο σύνολο θα περιέχει υποσύνολο αθροίσματος t - (s - 2t) = 3t - s και, μετά από τρεις κινήσεις, μειώνουμε το n κατά 1 και εφαρμόζουμε την επαγωγική υπόθεση (με s' = 2t και t' = 3t - s). Έτσι ολοκληρώνεται η επαγωγή.


Δημήτρης Σκουτέρης

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

Re: Άθροισμα υποσυνόλων αριθμών σε πίνακα

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Μάιος 11, 2017 3:34 pm

Πολύ ωραία. Την πήρα από εδώ. (Η απάντηση που δόθηκε ξεκινά όπως του Δημήτρη αλλά είναι λανθασμένη.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης