p τμήματα q ατόμων σε r συνεδρίες

[gbaloglou]

[Προέκυψε από πραγματικό πρόβλημα, δεν είμαι σίγουρος για τον φάκελο, δεν έχω λύση.]

Ψυχολόγος έχει ασθενείς. Σε κάθε συνεδρία θέλει να έχει τμήματα με ασθενείς στο καθένα, και συνεχή εναλλαγή ασθενών στο κάθε τμήμα. Ποιος είναι ο ελάχιστος αριθμός συνεδριών που απαιτείται ώστε δύο οποιοιδήποτε από τους ασθενείς να έχουν συναντηθεί σε μία τουλάχιστον συνεδρία; Εναλλακτικά, αν είναι δεδομένος ο αριθμός των συνεδριών, ποιος είναι ο ελάχιστος δυνατός αριθμός των 'απόντων ζευγών';

[Στο πραγματικό πρόβλημα είχαμε ασθενείς που συναντώνται, σε κάθε συνεδρία, σε τμήματα των ατόμων. Με δεδομένη μία πρώτη συνεδρία, με τμήματα {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, έπρεπε να σχεδιασθούν άλλες τρεις. (, , ) Είχε τεθεί ο επιπλέον περιορισμός να μη συνυπάρξουν σε συνεδρία ούτε ο #1 με τον #9 ούτε ο #2 με τον #10. (Τέτοιου τύπου περιορισμοί ας αγνοηθούν στην γενική περίπτωση που εκθέτω παραπάνω.) Σε μια πρώτη απόπειρα πρότεινα τις συνεδρίες {1, 5, 11, 12}, {2, 4, 6, 9}, {3, 7, 8, 10} -- {1, 6, 7, 10}, {2, 5, 8, 11}, {3, 4, 9, 12} -- {1, 7, 8, 10}, {2, 4, 11, 12}, {3, 5, 6, 9}, με 'απόντα ζεύγη' τα (1,9), (2, 7), (2, 10), (3, 11), (4, 5), (4, 7), (4, 8), (4, 10), (5, 10), (6, 11), (6,12), (7, 9), (7, 11), (7, 12), (8, 9), (8, 12) -- φαίνονται πολλά, αλλά δεν είναι!]

[gbaloglou]

[Προέκυψε από πραγματικό πρόβλημα, δεν είμαι σίγουρος για τον φάκελο, δεν έχω λύση.]

Ψυχολόγος έχει ασθενείς. Σε κάθε συνεδρία θέλει να έχει τμήματα με ασθενείς στο καθένα, και συνεχή εναλλαγή ασθενών στο κάθε τμήμα. Ποιος είναι ο ελάχιστος αριθμός συνεδριών που απαιτείται ώστε δύο οποιοιδήποτε από τους ασθενείς να έχουν συναντηθεί σε μία τουλάχιστον συνεδρία; Εναλλακτικά, αν είναι δεδομένος ο αριθμός των συνεδριών, ποιος είναι ο ελάχιστος δυνατός αριθμός των 'απόντων ζευγών';

[Στο πραγματικό πρόβλημα είχαμε ασθενείς που συναντώνται, σε κάθε συνεδρία, σε τμήματα των ατόμων. Με δεδομένη μία πρώτη συνεδρία, με τμήματα {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, έπρεπε να σχεδιασθούν άλλες τρεις. (, , ) Είχε τεθεί ο επιπλέον περιορισμός να μη συνυπάρξουν σε συνεδρία ούτε ο #1 με τον #9 ούτε ο #2 με τον #10. (Τέτοιου τύπου περιορισμοί ας αγνοηθούν στην γενική περίπτωση που εκθέτω παραπάνω.) Σε μια πρώτη απόπειρα πρότεινα τις συνεδρίες {1, 5, 11, 12}, {2, 4, 6, 9}, {3, 7, 8, 10} -- {1, 6, 7, 10}, {2, 5, 8, 11}, {3, 4, 9, 12} -- {1, 7, 8, 10}, {2, 4, 11, 12}, {3, 5, 6, 9}, με 'απόντα ζεύγη' τα (1,9), (2, 7), (2, 10), (3, 11), (4, 5), (4, 7), (4, 8), (4, 10), (5, 10), (6, 11), (6,12), (7, 9), (7, 11), (7, 12), (8, 9), (8, 12) -- φαίνονται πολλά, αλλά δεν είναι!]

Λίγο καλύτερα (13 απόντα ζεύγη αντί 16): συνεδρίες {(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12)} -- {(1, 5, 9, 12), (2, 6, 7, 11), (3, 4, 8, 10)} -- {(1, 6, 8, 10), (2, 5, 11, 12), (3, 4, 7, 9)} -- {(3, 5, 7, 12), (4, 6, 9, 10), (1, 2, 8, 11)}, απόντα ζεύγη (1, 7), (2, 9), (2, 10), (3, 6), (3, 11), (4, 5), (4, 11), (4, 12), (5, 10), (6, 12), (7, 10), (8, 9), (8, 12).