Ένας πλούσιος αγρότης είχε $30$ παιδιά (!), $15$ από την πρώτη του σύζυγο που είχε πεθάνει και $15$ από την δεύτερη συζυγό του. Η τωρινή του σύζυγος ανυποµονούσε να πάρει την περιουσία ο µεγαλύτερος γιος της, έτσι κάποια µέρα είπε στον άντρα της ότι αυτός µεγαλώνει και ότι ϑα πρέπει να ορίσει τον κληρονόµο του. Του πρότεινε λοιπόν να ϐάλουν όλα τα παιδιά σε έναν κύκλο και να εξαιρούν από την περιουσία κάθε $10$ο, έτσι ώστε αυτό που ϑα έµενε τελευταίο να έπαιρνε την περιουσία. Η πρόταση αυτή ϕάνηκε λογική. ΄Οµως καθώς η διαδικασία της επιλογής προχωρούσε ο αγρότης µε µεγάλη του έκπληξη παρατήρησε ότι τα πρώτα $14$ παιδιά που εξαιρέθηκαν ήταν από τον πρώτο του γάµο και ότι το επόµενο ϑα ήταν το τελευταίο παιδί από τον πρώτο του γάµο. ΄Ετσι πρότεινε από αυτό το παιδί και πέρα να αλλάξουν τη ϕορά µε την οποία µετρούσαν. Η γυναίκα του σκέφτηκε ότι το ποσοστό ήταν $15$ προς $1$, µε εύνοια προς τα δικά της παιδιά, και δέχτηκε. Ποιος έγινε τελικά ο κληρονόµος του αγρότη;
W.W.R. Ball and H.S.M. Coxeter, Mathematical Recreations Essays
Ναι, τελικά ο κληρονόμος είναι το τελευταίο παιδί από τον πρώτο γάμο:-) Mάλλον ο αγρότης λεγόταν Ιώσηπος..
ΑπάντησηΔιαγραφήΑρχικά αποκλείονται κατα σειρά τα παιδιά:
10,20,30,11,22,3,15,27,9,24,7,23,8,26 Αυτές είναι και οι θέσεις που κατείχαν (σε σειρά από το 1 έως το 30) τα 14 πρώτα παιδιά από τον πρώτο γάμο.
Αν συνεχιστεί η "εξολόθρευση" στο ίδιο μοτίβο (ανά 10) το επόμενο είναι το υπ.αρ. 14 (και 15ο υπό εξολόθρευση). Με την αλλαγή όμως το παιδί αυτό γίνεται 1ο στη νέα σειρά των 16 (1,2,..,16) εναπομεινάντων παιδιών και η νέα "εξολόθρευση" πάει(ανά 10) ως εξής: 10,4,15,11,7,5,3,6,9,14,8,2,13,16,12,1 .To 1 λοιπόν (το παλιό 14 και 15ο στην αρχική σειρά) μένει τελευταίο και κερδίζει την κληρονομιά.
Κλασικός αλγόριθμος Josephus :)
ΑπάντησηΔιαγραφή