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

Ιανουαρίου 8, 2009

Ανασχηματισμός και οικονομία

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 5:51 μμ

kathimerini

Μετά από ένα πρόσφατο ανασχηματισμό της κυβέρνησης ο νέος υπουργός Οικονομίας είναι αποφασισμένος να πατάξει τη γραφειοκρατία και να απλοποιήσει όσο μπορεί τη φορολογική νομοθεσία. Η πρώτη ιδέα που του έρχεται στο μυαλό είναι να επιτρέψει σε κάθε επιχείρηση να στρογγυλεύει τα διάφορα ποσά που καταγράφει στα έξοδά της στο επίπεδο του 1 ευρώ.

Έτσι, αν μια επιχείρηση έχει τα εξής έξοδα (πραγματικοί αριθμοί)

x_1, x_2, \ldots, x_N \in {\mathbf R}

της επιτρέπει να εγγράψει στη φορολογική της δήλωση (αλλά όχι στα βιβλία όπου πρέπει να φαίνονται τα πραγματικά ποσά) τα ποσά

y_1, y_2, \ldots, y_N \in {\mathbf Z}

όπου για κάθε j ο ακέραιος y_j είναι είτε το στρογγύλεμα του x_j προς τα κάτω είτε προς τα πάνω (με άλλα λόγια {y_j = \lfloor{x_j}\rfloor} ή {y_j = \lceil{x_j}\rceil}).

Το ποια από τις δύο στρογγυλεύσεις για το κάθε ποσό θα κάνει η επιχείρηση είναι επιλογή δικιά της.

Μετά από παρεμβάσεις όμως πιο παλαιών υπηρεσιακών παραγόντων του υπουργείου στη νέα αυτή διάταξη του υπουργού προστέθηκε η εξής απαίτηση:

Για κάθε {1 \le a < b \le N} πρέπει η επιχείρηση να φροντίσει ώστε να ισχύει

\displaystyle {\left| \sum_{j=a}^b x_j - \sum_{j=a}^b y_j\right| \le 1}.

Το ίδιο βράδυ που ανακοινώθηκε η νέα διάταξη τα δελτία ειδήσεων είναι διχασμένα: άλλα λένε ότι η νέα διάταξη δε μπορεί να εφαρμοστεί επειδή αυτό που ζητάει δε γίνεται πάντα και άλλα ότι αυτό πάντα μπορεί να γίνει.

Εσείς τι λέτε;

Advertisements

9 Σχόλια »

  1. Έστω ότι γίνεται
    και για κάθε j, xj=5,3
    τότε yj=6 ή yj=5

    Αν yj=6 τότε
    για b-a>1 δεν ισχύει

    Αν yj=5 τότε
    για b-a>3 δεν ισχύει

    Αν τώρα κάποια j επιλέγω yj 6 και για κάποια 5
    θα πρέπει για κάθε μ,λ φυσικούς
    μ(-0,7)+λ(0,3)=0
    γιατί αλλιώς για b-a>9 δεν ισχύει

    Μου αρέσει!

    Σχόλιο από oasomp — Μαρτίου 6, 2009 @ 5:50 μμ

  2. oasomp:

    Το \mu και το \lambda που γράφεις παραπάνω είναι εν γένει διαφορετικά για διαφορετικές τιμές των a, b.

    Επίσης για δεδομένες τιμές των a, b δε χρειάζεται να έχεις \mu(-0,7)+\lambda(0.3) = 0 αλλά η ποσότητα αυτή να είναι το πολύ 1 κατ’ απόλυτο τιμή.

    Ποιο είναι το συμπέρασμα λοιπόν;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 6, 2009 @ 6:18 μμ

  3. Λοιπόν άλαξα γνώμη !!!

    Γίνεται τελικά 😀

    Επειδή μπόρω να επιλέγω το y_j έτσι ώστε
    {x_j-y_ j {<} 0} ή {x_j-y_j {>} 0}

    και |x_j-y_j| {<}1 για κάθε j.

    Αν {x_j-y_j {<} 0} τότε επιλέγω {y_{j+1}} έτσι ώστε
    {x_{j+1}-y_{j+1} {>}0}.

    Αντίστοιχα για {x_j-y_j>0}

    Άρα επειδή για να βρεθώ από το (-1,0) στο {[1,\infty)}
    προσ8έτοντας σε οποιδήποτε στοιχείο του (-1,0)
    μια ποσότητα <1 είναι αδύνατον

    Συμπέρασμα γίνεται 😀

    Αλλά με τη φοροδιαφυγή που υπάρχει στην Ελλάδα
    αν συζυτούσαν κάτι τέτοιο στα κανάλια θα είχαν βρεί
    50 αποδείξεις σε μισή ώρα ότι δε γίνεται 😀

    Μου αρέσει!

    Σχόλιο από oasomp — Μαρτίου 7, 2009 @ 3:02 μμ

  4. oasomp:

    Είσαι στο σωστό δρόμο αλλά η λύση σου απέχει ακόμη από το να είναι πλήρης. Πώς συγκρίνεις τα αθροίσματα \sum_{j=a}^b x_j και \sum_{j=a}^b y_j μεταξύ τους;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Μαρτίου 7, 2009 @ 4:53 μμ

  5. Νομίζω πως ισχύει Σxj-Σyj=Σxj-yj

    Μου αρέσει!

    Σχόλιο από oasomp — Μαρτίου 7, 2009 @ 7:47 μμ

  6. Ένας επιχειρηματίας σκέφτεται ώς εξής:

    Θα αρχίσω να διαλέγω τα y_i ένα προς ένα ώστε να ικανοποιώ όλες τις συνθήκες που μου ζητάνε. Αν αυτό δεν πετύχει, σημαίνει πως δεν γίνεται άρα δεν θα με τιμωρήσουν.

    Δείξτε πως έστω και αν ο συλλογισμός του επιχειρηματία είναι λανθασμένος, ο αλγόριθμός του δουλεύει.

    Μου αρέσει!

    Σχόλιο από demetres — Μαρτίου 15, 2009 @ 2:29 μμ

  7. Η πολυπλοκότητα αυτής της άσκησης είναι ότι απαιτούμε η ανισότητα

    \left| \sum_{j=a}^b (x_j - y_j) \right| \le 1

    να ισχύει για κάθε a, b.

    Μήπως μπορούμε να την εξασφαλίσουμε αυτή την ανισότητα εξαλείφοντας τη μια από τις δύο παραμέτρους a, b, φράσσοντας δηλ. κατάλληλα τις ποσότητες

    \left| \sum_{j=1}^b (x_j - y_j) \right| για κάθε b;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 20, 2009 @ 7:05 μμ

  8. Έστω ότι έχουμε τα y_1,y_2,\ldots ,y_i για τα οποία ισχύει
    \left | \sum_{j=a}^b(x_j-y_j)\right|\le 1 για κάθε 1 \le a<b\le i.
    Θα αποδείξουμε ότι υπάρχει y_{i+1} τέτοιο ώστε να ισχύει
    \left | \sum_{j=a}^b(x_j-y_j)\right|\le 1 για κάθε 1 \le a<b\le i+1.
    Για να ισχύει το τελευταίο, αρκεί να ισχύει ότι
    \left | \sum_{j=k}^{i+1}(x_j-y_j)\right|\le 1 για κάθε k=1,2,\ldots ,i+1 ,
    το οποίο ισοδυναμεί με το
    -1-\sum_{j=k}^i(x_j-y_j)\le x_{i+1}-y_{i+1}\le 1-\sum_{j=k}^i(x_j-y_j) για κάθε k=1,2,\ldots ,i+1.
    Το τελευταίο ισχύει αν-ν
    -1-\min_k\left ( \sum_{j=k}^i(x_j-y_j)\right )\le x_{i+1}-y_{i+1}\le 1-\max_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) (1).
    Έστω ότι δεν υπάρχει y_{i+1} τέτοιο ώστε να ισχύει η (1), δηλαδή και για y_{i+1}=\lfloor{x_{i+1}\rfloor} και για y_{i+1}=\lceil{x_{i+1}\rceil} δεν ισχύει η (1). Προκύπτουν τότε τρεις περιπτώσεις:
    1) x_{i+1}-\lceil{x_{i+1}\rceil}>1-\max_k\left ( \sum_{j=k}^i(x_j-y_j)\right )\ge 0 \Rightarrow x_{i+1}>\lceil{x_{i+1}\rceil} (άτοπο),
    2) x_{i+1}-\lfloor{x_{i+1}\rfloor}<-1-\min_k\left ( \sum_{j=k}^i(x_j-y_j)\right )\le 0 \Rightarrow x_{i+1}<\lfloor{x_{i+1}\rfloor} (άτοπο),
    3) x_{i+1}-\lceil{x_{i+1}\rceil}<-1-\min_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) και 1-\max_k\left ( \sum_{j=k}^i(x_j-y_j)\right )<x_{i+1}-\lfloor{x_{i+1}\rfloor} \Rightarrow \max_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) > 1-(x_{i+1}-\lfloor{x_{i+1}\rfloor}) = -(x_{i+1}-\lceil{x_{i+1}\rceil}) > 1+\min_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) \Rightarrow \max_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) - \min_k\left ( \sum_{j=k}^i(x_j-y_j)\right ) > 1 \Rightarrow
    \Rightarrow \exists 1\le a<b\le i : \left | \sum_{j=a}^b(x_j-y_j)\right| > 1 (άτοπο).
    Συνεπώς επιλέγοντας στην αρχή τυχαία το y_1 μπορούμε στη συνέχεια διαδοχικά να βρούμε τα y_2,y_3,\ldots ,y_N ώστε να ισχύει το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από stedes — Σεπτεμβρίου 22, 2009 @ 4:33 πμ

  9. Μπράβο, πολύ σωστή και μεθοδική λύση.

    Υπάρχει κι άλλος ένας τρόπος να το λύσει κανείς, να εξασφαλίσει δηλ. με τις επιλογές του ότι τα αθροίσματα

    \sum_{j=1}^k (x_j-y_j), για όλα τα k=1,2,\ldots,N,

    είναι στο διάστημα [-1/2, 1/2]. Αν το πετύχουμε αυτό τότε τα αθροίσματα που μας ενδιαφέρουν είναι στο [-1,1] αφού είναι διαφορές των παραπάνω.

    Αν τώρα ισχύει η παραπάνω ανισότητα για κάποιο k και θέλουμε να την εξασφαλίσουμε και για το επόμενο επιλέγουμε το y_{k+1} με τέτοιο τρόπο ώστε ισχύει. Γιατί μπορούμε να το κάνουμε αυτό; Γιατί αν η επιλογή y_{k+1}=\lfloor{x_{k+1}}\rfloor δε δουλεύει τότε αναγκαστικά η άλλη επιλογή δουλεύει (ελέγξτε το).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 22, 2009 @ 8:45 πμ


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: