If someone can help me with a full-detailed explanation, I would greatly appreci
ID: 2941744 • Letter: I
Question
If someone can help me with a full-detailed explanation, I would greatly appreciate it!!!A popular recreational puzzle hypothesis that you have nine pearls that are identical in appearance. Eight of these pearls have the same weight, but the ninth is either heavier or lighter-you do not know which. You have a balance scale, and are allowed three weighings to find the odd pearl. How do you proceed?
Now here is a bogus proof by induction that you can solve the problem in the first paragraph in three weighings not just for nine pearls but for any number of pearls. For convenience let us begin the induction with the case n=9 pearls. By the result of the first paragraph, we can handle that case. Now, inductively, suppose that we have an algorithm for handling n pearls. We use this hypothesis to treat (n+1) pearls. From the (n+1) pearls, remove one and put it in your pocket. There remains n pearls. Apply the n-pearl algorithm to these remaining pearls. If you find the odd pearl then you are done. If you do not find the odd pearl, then it is the one in your pocket. That completes the case (n+1) and the proof.
What is the flaw in the reasoning? [Remark from the book: If you are fiendishly clever, then you can actually handle 12 pearls in the original problem-with just three weighings. However this requires the consideration of 27 cases].
Explanation / Answer
If someone can help me with a full-detailed explanation, I would greatly appreciate it!!!
A popular recreational puzzle hypothesis that you have nine pearls that are identical in appearance. Eight of these pearls have the same weight, but the ninth is either heavier or lighter-you do not know which. You have a balance scale, and are allowed three weighings to find the odd pearl. How do you proceed?
Now here is a bogus proof by induction that you can solve the problem in the first paragraph in three weighings not just for nine pearls but for any number of pearls. For convenience let us begin the induction with the case n=9 pearls. By the result of the first paragraph, we can handle that case. Now, inductively, suppose that we have an algorithm for handling n pearls. We use this hypothesis to treat (n+1) pearls. From the (n+1) pearls, remove one and put it in your pocket. There remains n pearls. Apply the n-pearl algorithm to these remaining pearls. If you find the odd pearl then you are done. If you do not find the odd pearl, then it is the one in your pocket. That completes the case (n+1) and the proof.
What is the flaw in the reasoning? [Remark from the book: If you are fiendishly clever, then you can actually handle 12 pearls in the original problem-with just three weighings. However this requires the consideration of 27 cases].
I THINK YOU WANT THE FLAW IN THE PROOF GIVEN ABOVE...AND NOT THE SOLUTION FOR 12 PEARL PROBLEM OR FOR THAT MATTER EVEN FOR THE 9 PEARL PROBLEM...IF YOU WANT THAT PLEASE COME BACK..
NOW THE PROOF GIVEN ABOVE...
Now here is a bogus proof by induction that you can solve the problem in the first paragraph in three weighings not just for nine pearls but for any number of pearls......
For convenience let us begin the induction with the case n=9 pearls........OK..
By the result of the first paragraph, we can handle that case.........OK
Now, inductively, suppose that we have an algorithm for handling n pearls.......OK...
THAT IS THE ANSWER FOR N PEARLS IS SOME M WEIGHINGS ...IN CASE OF N=9 PEARLS ,
WE GOT M=3 WEIGHINGS...AS THE ANSWER....
We use this hypothesis to treat (n+1) pearls.......OK......
From the (n+1) pearls, remove one and put it in your pocket......OK........
THAT IS WE MADE IT IN TO 2 GROUPS .....GROUP 1 OF N PEARLS AND GROUP 2 OF 1 PEARL...
There remains n pearls.....OK....THAT IS TAKING GROUP 1 SAY
Apply the n-pearl algorithm to these remaining pearls.......OK ....WE NEED M WEIGHINGS TO DETERMINE
THE FAULTY PEARL IF THERE IS ONE.....THAT IS AFTER THESE M WEIGHINGS WE CONCLUDE GROUP 1
HAS A FAULTY PEARL OR NOT.....OK
If you find the odd pearl then you are done..........OK
If you do not find the odd pearl, then it is the one in your pocket....OK THAT IS GROUP 2...SO WITH N+1 PEARLS AND M WEIGHINGS WE COULD IDENTIFY THE ODD PEARL IF IT EXISTS AND SEPARATE IT...
IF IT IS ONLY A PROBLEM OF THESE N+1 PEARLS WITH ONE OF THEM BEING ODD THEN WE CAN IDENTIFY IT AND TAKE IT OUT . BUT THE CATCH IS THAT IF IT IS NOT THERE IN THE N+1 PEARLS WHICH COULD BE THE CASE WITH MORE THAN N+1 PEARLS.NOTE THAT FOR INDUCTION WE HAVE TO PROVE THAT IF A STATEMENT OR FORMULA IS TRUE FOR N , THEN IT IS ALSO TRUE FOR N+1 IN ALL CASES..WHICH IS VIOLATED HERE.....WHAT IS PROVED BY THE ABOVE BOGUS INDUCTION PROOF IS THAT ...
IF WE ARE GIVEN THE PROBLEM IN STAGES AND NOT IN ITS ENTIRITY.....THAT IS
AT FIRST WE ARE GIVEN 9 PEARLS ..THEN WE FOUND OUT WHETHER IT HAS AN ODD PEARL IN 3 WEIGHINGS.
THEN WE ARE GIVEN A 10 TH. PEARL SEPARATELY...THEN WE CAN FIND THE ODD PEARL IN SAME 2 WEIGHINGS..
NOW USING THE ABOVE FACT ONLY WE CAN SOLVE THE PROBLEM FOR 11 TH.PEARL.THAT IS HAVING CONCLUDED THAT THE ODD PEARL IS ONE OF GROUP 1 OF NINE PEARLS OR GROUP 2 OF 1 PEARL [10 TH. PEARL] ..OR NEITHER...ON THAT FACT ONLY WE CAN FIND THE ODD PEARL .
BUT IF ALL 11 PEARLS ARE GIVEN IN ONE STAGE , THEN OUR INDUCTION ARGUMENT FAILS.
WHILE OUR GROUP 1 IS SAME WITH 9 PEARLS AND COULD BE CHECKED IN 3 WEIGHINGS , IF THE ODD PEARL IS NOT THERE IN THAT , THEN IT IS IN GROUP 2 OF 2 PEARLS FOR WHICH WE NEED ONE MORE WEIGHING...TAKING ONE OF THEM AND COMPARING WITH THE ONE OF THE 9 GOOD ONES IN GROUP 1..SO THE NUMBER OF WEIGHINGS IS NOT 3 , BUT 4
HOPE YOU UNDERSTOOD THE FLAW NOW..
That completes the case (n+1) and the proof.........OF BOGUS INDUCTION !!!!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.