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

[Demetres]

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

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

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

[dement]

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

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

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

Για θεωρούμε το άθροισμα και κάνουμε την ερώτηση "Υπάρχει ο ;".

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

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

[Demetres]

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