JotD / QotD Ελληνική Λίστα Κουίζ (QotD)


Θέμα: Re: Re: Ari0moi (H LUSH)



(nil): Giorgos Pallas (gpall(@)hal.csd.auth.gr)
Ημερομηνία: Wed 17 Apr 2002 - 00:17:31 EEST

Σαν πληροφορικός και εγώ επιχείρησα μια άλλης φιλοσοφίας προσέγγιση
(brute force), επιβεβαιώνοντας τη λύση του Δημήτρη. Με αυτή τη λύση
πάντως όποιος είχε αμφιβολίες θα σιγουρευτεί ότι όντως έτσι είναι.

Ξαναγράφω και το κουίζ μαζί με τη λύση, για να είναι ολοκληρωμένο στα
αρχεία της λίστας.

Έχουμε δυο ακέραιους αριθμούς, x, y για τους οποίους ισχύει 2 <= x,y <= 99.
Έστω Α το άθροισμά τους και G το γινόμενό τους.
Έστω και δυο φίλοι, ο ένας εκ των οποίων γνωρίζει μόνο το άθροισμα Α,
και ο άλλος μόνο το γινόμενο G.
Για ευκολία τους ονομάζουμε αντίστοιχα Α και G.
Ανάμεσά τους λαμβάνει χώρα ο εξής διάλογος.

G: Δεν ξέρω τους αριθμούς.
Α: Το ήξερα οτι δεν τους ξέρεις. Ούτε εγώ τους ξέρω.
G: Τώρα τους ξέρω!
A: Τώρα τους ξέρω και εγώ!!!

Ποιοί είναι οι δυο αριθμοί;
-------------------------------------------------------

Ιδού λοιπόν η λύση με αμιγώς υπολογιστική προσέγγιση:
(ευχαριστώ πολύ την κυβέρνηση των Ηνωμένων Πολιτειών και τον Δημήτρη
Σκούτερη που τον έπρηξα μέχρι να βρω ενα ζωύφιο που είχε τρυπώσει στο
πρόγραμμα)

G: Δεν τους ξέρω.
Άρα:
      1. το γινόμενο G μπορεί να δωθεί με παραπάνω απο ενα τρόπους, το
ονομάζουμε ασαφές
         (π.χ. 50 = 5χ10 = 2χ25)

Α: Το ήξερα οτι δεν τους ήξερες, ούτε εγώ τους ξέρω.
Άρα: (απο το πρώτο σκέλος της απάντησης)
      1. Ο Α έχει ενα τέτοιο άθροισμα του οποίου *όλες* οι λύσεις
αντιστοιχούν σε ασαφή γινόμενα. Αυτό, μετά απο *εξαντλητική* δοκιμή απο
τον υπολογιστή μπορεί να είναι ενα απο τα εξής: 11, 17, 23, 27, 29, 35,
37, 41, 47, 53.

Ιδού και το πρόγραμμα που έγραψα για το σκοπό αυτό:(μην ανησυχείτε, 20
γραμμούλες απλού κώδικα C)

#include <stdio.h>

int fuzzy(int x){
   int i,j,s=0;
   for(i=2;i < 100;i++)
    for(j=2;j < 100;j++)
     if (x == i*j) s++;
   return s > 2;
}

int main(){

   int sum,x,tmp;
   for(sum=4;sum <= 198;sum++){
     x=2;
     while ((tmp=fuzzy(x*(sum -x))) && (x = x+1) && (x+1 < sum));
     if (tmp) printf("Kalo Athroisma : %d\n",sum);
   }
  return 0;
}

Η μέθοδος είναι απλή, παίρνω με τη σειρά όλα τα πιθανά αθροίσματα (απο 4
μέχρι 198) και βρίσκω αν είναι ασαφή ϋΑ τα γινόμενα που παράγονται απο
όλους τους συνδυασμούς που δίνει το κάθε άθροισμα.
Για παράδειγμα: Έστω ελέγχω το άθροισμα 51.
Ελέγχω αν είναι ασαφή ϋΑ τα γινόμενα 2*49 κτλ, κτλ...

Συνοψίζοντας λοιπόν, τα "καλά αθροίσματα" είναι τα 11, 17, 23, 27, 29,
35, 37, 41, 47, 53.

G: Τώρα τους ξέρω!

Ο G, ακούγοντας τον A να λέει "το ξέρω οτι δεν τους ήξερες" και κάνοντας
τις προηγούμενες σκέψεις, δεν έχει παρά να λύσει 10 συστήματα δυο
εξισώσεων με δυο αγνώστους προκειμένου να βρεί τους δυο αριθμούς. Τα
δέκα αυτά συστήματα είναι (έστω x, y οι δυο ζητούμενοι αριθμοί):

  x + y = Α
  x * y = G
με Α = {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}

Όπου το G το ξέρει βέβαια, αφού είναι ο G ;-)
Αν όμως, πάνω απο ένα απο αυτά τα συστήματα είχε λύση αποδεκτή στα
πλαίσια του προβλήματος, ο G δεν θα έλεγε οτι ξέρει τους αριθμούς.
Προφανώς δεδομένου του G, *μόνο ενα* απο αυτά τα συστήματα έχει αποδεκτή
λύση, και έτσι βρήκε τους αριθμούς.
Για ευκολία ονομάζουμε τα γινόμενα εκείνα των οποίων μόνο μια λύση απο
όλες αντιστοιχεί σε καλό άθροισμα *σπάνια*.

A: Τώρα τους ξέρω και εγώ!

Ο Α όμως δεν γνωρίζει το G. Άρα η μόνη πληροφορία που διαθέτει είναι οτι
ακριβώς, μόνο ενα απο τα παραπάνω συστήματα έχει αποδεκτή λύση. Αν ο Α
προσπαθήσει να ελέγξει όλα τα ασαφή γινόμενα για να δει ποιά απο αυτά
οδηγούν σε 10 συστήματα εκ των οποίων μόνο 1 έχει λύση, θα βρεθεί προ
αμέτρητων γινομένων, άρα συμπέρασμα δεν βγάζει. Όμως ο Α ισχυρίζεται οτι
ξέρει τους αριθμούς, άρα πρέπει να έχει ενα τέτοιο άθροισμα, που μόνο
μια λύση του να αντιστοιχεί σε σπάνιο γινόμενο.

Το παρακάτω πρόγραμμα, ελέγχει και τα 10 καλά αθροίσματα, και εκτυπώνει
όσα απο αυτά βρεί να έχουν *ακριβώς μία* λύση που να αντιστοιχεί σε
σπάνιο γινόμενο.

#include <stdio.h>

int good_sums[]={11, 17, 23, 27, 29, 35, 37, 41, 47, 53};

int fuzzy(int x){
   int i,j,s=0;

   for(i=2;i < 100;i++)
    for(j=2;j < 100;j++)
     if (x == i*j) s++;
   return s > 2;
}

int is_it_a_good_sum(int sum){
   int i=0;
   while( (good_sums[i] != sum ) && (i++ < 10) );
   return i < 10;
}

int spanio(int G){
   int i,j,s=0;

   for(i=2;i <= 99;i++)
    for(j=2;j <= 99;j++)
      if (G == i*j)
        if (fuzzy(G))
          if (is_it_a_good_sum(i+j))
            s++;
   return s == 2;
}

int main(){

   int i,x,one;
   for(i=0;i < 10;i++){
     x=2;
     one=0;
     do{
       one += spanio(x*(good_sums[i]-x));
       x++;
     }while (x+1 < good_sums[i]);
     if (one == 2) printf("SUM = %d\n",good_sums[i]);
   }
   return 0;
}

Τρέχοντας το πρόγραμμα παίρνουμε:
SUM = 17
οπότε, το μοναδικό απο τα καλά αθροίσματα το οποίο έχει μόνο μια λύση
που να αντιστοιχεί σε σπάνιο γινόμενο είναι το 17. Απο εδώ και πέρα
είναι trivial να δούμε οτι αυτή η λύση είναι το 14 + 3 που αντιστοιχεί
στο σπάνιο γινόμενο 52.

Οι αριθμοί λοιπόν είναι το 3 και το 14.

GP

______________________________________________________________________

 Quiz of the Day ... Ελληνική Λίστα με σπαζοκεφαλιές ... και άλλα ...
 Πληροφορίες --> https://anekdota.duckdns.org/quiz_list.html
______________________________________________________________________


Γραφτείτε και εσείς στην Ελληνική Λίστα με σπαζοκεφαλιές (QotD) και στείλτε τα κουίζ σας!!!

Επιστροφή στον κεντρικό κατάλογο αυτού του αρχείου