‘Teach For Fun’ is a contest we at 2IIM announced as a run-up to the Teachers’ Day. Teaching and learning are two things that do not have finite limits (talking the language of Math, a subject that gives me immense joy). It is our strongest belief that new ideas, concepts and teaching methodologies, approaches and puzzles can come from anybody, irrespective of the “teacher” tag. When I took a look at all the entries submitted by our ever-enthusiastic students, it was thoroughly fascinating . It is always a good, refreshing sign when students chime in with Mathematical, logical puzzles and thoughtful views on education, in general.
Thank you, once again, for participating in the contest. Happy Teachers’ Day to everybody out there. All of us are teachers, one way or the other.
Cracking the Code
The puzzle – Bulls and Cows
Ramesh and Suresh, while enjoying their five-star chocolate, decided to forget the world around them by playing a version of the game “Bulls and Cows”.
The rules of the game are as follows:
Ramesh forms a secret 4-digit code (without repetition and excluding 0) and Suresh must break the code using clues given by Ramesh.
For every guess from Suresh, Ramesh tells the number of Bulls – the number of digits in his code and in correct position – and the number of Cows – the number of digits in his code and not in the correct position.
- If Ramesh’s number is 8352 and Suresh guesses 3459, Ramesh would reply 1 Bull (5 is in the code and in the right position) and 1 Cow ( 3 is in the code and not in the right position).
- Ramesh’s code = 6724; Suresh’s Guess = 7429
Ramesh’s reply in this case would be 1 Bull 2 Cows
The questions: Codes, Guesses, Bulls and Cows
(Please note each question is independent and the information must not be taken forward to the following questions unless otherwise informed in the question)
- What are the total number of possible codes that can be formed by Ramesh?
- If Ramesh replies Suresh with 4 Bulls and 0 Cows, what is the total number of possible ordered pairs of Ramesh’s Code and Suresh’ guess?
- What is the total number of possible ordered pairs of Ramesh’s Code and Suresh’x guess, if Ramesh replies Suresh with 2 Bulls and 2 Cows?
- Assuming Ramesh replies Suresh with 3 Bulls and 1 Cows, what is the total number of possible ordered pairs of Ramesh’s Code and Suresh’s guess?
- What is the total number of possible ordered pairs of Ramesh’s Code and Suresh’s guess, if Ramesh replies Suresh with 0 Bulls and 4 Cows?
- If Ramesh replies Suresh with 0 Bulls and 0 Cows, what is the total number of possible ordered pairs of Ramesh’s Code and Suresh’s guess
- What is the total number of valid reply pairs of Bulls and Cows possible?
Please do not read further until and unless you have tried solving the questions on your own.
- 9P4 or 3024
- 9P4 or 3024
- 9P4 x 5P4 = 9! = 362880
We must find the total number of possible codes that can be made by Ramesh.
This question is analogous to the famous P&C question asked: “How many 4 digit numbers can be formed without any repetition and without using 0?”
- Total number of ways of choosing first digit = 9
- Total number of ways of choosing Second digit = 8 (we can’t use the digit used up for the first digit)
- Similarly, number of ways of choosing third and fourth digits are 7 and 6, respectively.
So, the total number of ways is obtained by 9*8*7*6 = 9P4 = 3024
Total number of ordered pairs of Ramesh’s code and Suresh’s guess with 4 Bulls and 0 Cows
Let us say Ramesh’s code is 1234 and for Suresh’s guess to obtain 4 Bulls, Suresh must also guess 1234.
Therefore, to obtain 4 Bulls, Suresh must exactly guess the same number formed by Ramesh.
Hence, the answer for this question would also be the total number of codes that are possible to be made = 9P4 =3024
Total number of ordered pairs of Ramesh’s code and Suresh’s guess with 2 Bulls and 2 Cows
We must use a concept of Derangements here.
(Denote the function D(x) to return the number of derangements of x. The same notation will be used in the following solutions)
Observe that Suresh’s guess must contain these 4 digits only and no other digit. Hence, we don’t require to select digits from the other 5 digits as the response from Ramesh is 2 Bulls and 2 Cows.
Therefore, 4 Common digits from 9 digits can be selected in 9C4 ways.
First number in the pair can be arranged in 4! Ways
Therefore, first number can be formed in 9C4 * 4! Or 9P4
Suresh’s guess or second number in the pair
2 out of these 4 digits are in right place and the other 2 are not in right place.
Number of ways of selecting 2 digits from 4 digits to be fixed = 4C2
Number of ways of other 2 digits not in the right place = Number of derangements of 2 = D (2) =1
(Number of possibilities of selecting first number in the pair) *(No. of possibilities of selecting the second number in the pair with the condition)
Number of ways of selecting first number = 9P4
No. of ways of forming second number in the pair with the condition = 4C2 * D(2) = 6*1
Final Solution = (9P4) * (4C2 *D(2) ) = 3024 *6 = 18144
Total number of ordered pairs of Ramesh’s code and Suresh’s guess with 3 Bulls and 1 Cows
Let us try to solve this question in 2 ways.
Simple Analysis of the given condition involving Bulls and Cows
From the condition, we understand that all 4 digits from Suresh’s guess exist in Ramesh’s code. And, 3 of these are in the right place and 1 digit is in the wrong place.
Can this situation ever occur?
When the 3 digits are fixed in their right place, 4th digit if not in its right place , cannot displace another digit from its right place too.
Suresh must tell the code maker Ramesh to check his response and not be too distracted by the taste of his chocolate (some fun from the old five star chocolate commercials😊)
Final Solution: Zero
Reusing the same analysis from the previous question,
Ways of forming Suresh’s guess = 4c3 * D(1)
We know that D(1) =0.
Therefore, final solution = 0
Total number of ordered pairs of Ramesh’s code and Suresh’s guess with 0 Bulls and 4 Cows
Again, reusing most of the analysis from the previous questions:
Ramesh’ Code or first number in the pair can be formed in 9P4 ways
Suresh’s guess must have all the 4 digits and no digit must be in right place.
This is the same as finding Derangements of 4 = D(4) = 9
Solution = (Number of possibilities of selecting first number in the pair) *( No. of possibilities of selecting the second number in the pair with the condition)
= (9P4) * (D(4)) = 3024 * 9 = 27216
Total number of ordered pairs of Ramesh’s code and Suresh’s guess with 0 Bulls and 0 Cows
Number of ways of forming Ramesh’s code or First number in the pair = 9C4*4! Or 9P4 = 3024
Number of ways of forming Suresh’s guess
Suresh’s guess must contain no digit from Ramesh’s code and must have been formed from the 5 other digits not in Ramesh’s code.
Therefore, total number of ways Suresh could have formed his code = 5C4 * 4! = 5P4
Solution= Total possibilities of Ramesh’s code X Total possibilities of Suresh’s guess
= 9P4 * 5P4 = 9!
Total number of possible valid pairs of Bulls and Cows possible
Does this question resemble a question as follows?
Number of ordered pairs (b,c) such that b and c non – negative integers and satisfying b+c < =4? (b for number of bulls and c for number of cows)
Let us solve b+c < =4
Introduce dummy variable d such that b+c+d = 4 (b, c,d >=0)
Number of solutions = (n+r-1)C(r-1) = (4+3-1) C(3-1) = 6C2 =15
Are we getting the right number of combinations of Bulls and Cows, though?
NO. Caution here!!!!
Remember the case – Bulls = 3 Cows = 1? We did find out it is not possible.
We must not count this case.
So, let us just count all 15 possible cases and remove invalid pairs.
Case B+C =4
(3,1) – Not Valid
Case B+C =3
Case B+C =2
Case B+C = 0
Total valid pairs = 4+4+3+2+1 = 14
So, indeed, we could have subtracted the invalid (3,1) from 15 cases earlier but as the number is quite low, we could do this counting in order to be completely sure.
Hope you had fun solving this puzzle 🙂 Cheers!
Vishnu Sai has been working as a software developer in Bengaluru for a year now. He finds interest in learning and exploring new fields in Mathematics. He loves to solve logical puzzles and games. Vishnu is preparing for the CAT examination this year and wishes all aspirants good luck for CAT 2020! He can be reached at firstname.lastname@example.org.