Προβλήματα Μαθηματικών

Μαΐου 24, 2009

Μηλιές και πορτοκαλιές

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 10:52 πμ

Δύο αδέρφια κληρονομούν ένα κτήμα που έχει μέσα 2ν μηλιές και 2μ πορτοκαλιές. Μπορούν να το χωρίσουν με μια ευθεία έτσι ώστε ο καθένας να πάρει ακριβώς ν μηλιές και μ πορτοκαλιές;

Advertisements

6 Σχόλια »

  1. Νομίζω ότι πρέπει να υποθέσεις ότι δεν υπάρχουν τρία δέντρα στην ίδια ευθεία και να θεωρήσεις τα δένδρα σα σημεία (αλλοιώς αν όλα τα δέντρα είναι πχ σε μία ευθεία δεν υπάρχει λύση)

    Μου αρέσει!

    Σχόλιο από perastikos1 — Ιουνίου 19, 2009 @ 8:10 μμ

  2. Ναι, υπάρχει αυτό το πρόβλημα με τη διατύπωση που έδωσα. Ευχαριστώ που το επισημαίνεις. Η σωστή διατύπωση είναι «… ώστε καθένα από τα δύο αδέρφια να έχει τουλάχιστον ν μηλιές και ν πορτοκαλιές στην πλευρά του, μετρώντας και τα δέντρα που βρίσκονται πάνω στο σύνορο».

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Ιουνίου 20, 2009 @ 12:30 πμ

  3. Για να έχει καθένα από τα 2 αδέρφια τουλάχιστον ν μηλιές και ν πορτοκαλιές στη μεριά του,
    δεν θα πρέπει να ισχύει ότι μ >= ν ? Διότι αν μ < ν δεν μπορεί να γίνει κάτι τέτοιο.

    Μου αρέσει!

    Σχόλιο από aaennarion — Σεπτεμβρίου 23, 2009 @ 9:30 μμ

  4. Συγγνώμη, τυπογραφικό λάθος. Εννοούσα ν μηλιές και μ πορτοκαλιές.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Σεπτεμβρίου 23, 2009 @ 10:31 μμ

  5. Ναι,μπορούν! Aρκεί να έχουν ένα σάντουιτς με χαμ (ή έστω με μορταδέλα) γιατί ναι μεν ο αλγόριθμος τρέχει πλέον σε γραμμικό χρόνο,αλλά άμα το χωράφι δεν είναι convex …η γαιωδεσιακή γραμμή απαιτεί λογαριθμικό χρόνο εύρεσης,και θα πεινάσουν. 🙂
    http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/DanielleMacNevin/algorithm-pg3.html (με ωραία περιγραφή του αλγορίθμου λύσης)

    Μου αρέσει!

    Σχόλιο από Rizopoulos Georgios — Νοέμβριος 17, 2013 @ 11:08 μμ

  6. Πολύ ωραία. Το πρόβλημα αυτό είναι μια ειδική περίπτωση του «ham sandwich theorem», που χοντρικά λέει ότι μπορείς να χωρίσεις στα δύο d σύνολα στις d διαστάσεις με ένα (d-1)-διάστατο υπερεπίπεδο. Αν για d=3, τα 3 σύνολα είναι φέτα ψωμί, ζαμπόν, και άλλη μια φέτα ψωμί το θεώρημα λέει ότι μπορείς να τα χωρίσεις όλα σε δύο ίσα μέρη με μια μαχαιρία. Ευχαριστούμε και για τον αλγόριθμο ΓΡ όταν τα σύνολα αυτά είναι πεπερασμένα σημεία, όπως στην εκφώνηση τπυ προβλήματος!

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Νοέμβριος 18, 2013 @ 12:08 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: