From: Giorgos Pallas (gpall(@)hal.csd.auth.gr)
Date: Τετ 17 Απρ 2002 - 00:17:31 EEST

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]

Σαν πληροφορικός και εγώ επιχείρησα μια άλλης φιλοσοφίας προσέγγιση (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++;

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);

Η μέθοδος είναι απλή, παίρνω με τη σειρά όλα τα πιθανά αθροίσματα (απο 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++;

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++;

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]);

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

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

GP

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

• Next message: Skouteris Dimitris: "Re: Ippotes kai Paliatsoi"
• Previous message: Skouteris Dimitris: "Ippotes kai Paliatsoi"
• Maybe in reply to: Θεόδωρος Γαβράς: "Re: Re: Ari0moi (H LUSH)"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
• Mail actions: [ respond to this message ] [ mail a new topic ]