We have learned many mathematical methods to solve counting problems. Some of these problems require a deep understanding of permutation and combination. In this chapter, we will learn examples of how to use programming to solve counting problems.
Example
Tickets on a bus were $4.00 and $6.00. A total of 45 tickets were sold and $230 was earned. How many $4.00 tickets were sold? (2007/MathIsCool problem at http://academicsarecool.com)
Answer
This can be solved by a single loop. We set the variable tickets as the number of $4.00 tickets. Because the total number of tickets is 45, the number of $4.00 tickets cannot be greater than 45. Therefore, tickets is an integer under 46.
System.out.println(tickets + " $4.00 tickets were sold.");
break;
}
}
}
Example
A chair has 4 legs, a stool has 3 legs, and a table has 1 leg. At a birthday party, there are 4 chairs per table and a total of 18 pieces of furniture. One of the children counts 60 legs total. How many stools are there? (2016/MathIsCool problem at http://academicsarecool.com)
Answer
In the following method, the variable tables represents number of tables. Then, the number of chairs is 4 × tables, and the number of stools is (18 – tables – 4 * tables).
A multiple-choice examination consists of 20 questions. The scoring is +5 for each correct answer, -2 for each incorrect answer, and 0 for each unanswered question. John’s score on the examination is 48. What is the maximum number of questions he could have answered correctly? (1987/AMC8 problem at https://artofproblemsolving.com/wiki/index.php/1987_AJHSME)
Answer
Unlike the previous two examples, in this one we will use two variables, c and w, in the loop. Let’s assume the number of correct answers is c, and the number of wrong answers is w. Their sum cannot be greater than 20 – the total number of problems. Because it may have more than one solution, we don’t use break to exit the program right after it finds the first solution. This is a different approach from in the previous examples.
Ruthie has 10 coins, all either nickels, dimes, or quarters. She has N nickels, D dimes, and Q quarters, where N, D, and Q are all different, and are each at least 1. Amazingly, she would have the same amount of money if she had Q nickels, N dimes, and D quarters. How many cents does Ruthie have? (2012 MathIsCool problem at http://academicsarecool.com)
Answer
Two for-loops are to be used in the following solution.
We use two for-loops to simulate how we distribute the six identical pencils to three people represented by variables, first, second, third.
private static void countWays() {
int count = 0;
for(int first=0; first <= 6; first++) {
for(int second = 0; second <= 6 - first; second++) {
int third = 6 - first - second;
if (first > 0 && second > 0 && third > 0) {
count++;
System.out.println("first=" + first + "; second=" + second + "; third=" + third); }
}
}
System.out.println("Total count=" + count);
}
The output is:
first=1; second=1; third=4
first=1; second=2; third=3
first=1; second=3; third=2
first=1; second=4; third=1
first=2; second=1; third=3
first=2; second=2; third=2
first=2; second=3; third=1
first=3; second=1; third=2
first=3; second=2; third=1
first=4; second=1; third=1
Total count=10
Example
Seven distinct pieces of candy are to be distributed among three bags. The red bag and the blue bag must each receive at least one piece of candy; the white bag may remain empty. How many arrangements are possible? (2010/10B AMC problem at https://artofproblemsolving.com/wiki/index.php/2010_AMC_10B)
Answer
First, we design an experiment. In this experiment, we want to put seven distinct strings (“A, ” “B, ” “C, ” “D, ” “E, ” “F, ” “G”) into three String arrays. The seven strings represent seven distinct pieces of candy. The three arrays represent red, blue, and white bags. The order of the placement doesn’t matter, but we need to make sure only the last array can be empty after the placement is made. The goal is to find the number of different placements.
When we place “A” in one of the three arrays, we need a for-loop for three different arrays. Then we need another for-loop to place “B,” and so on; in total we will need seven for-loops. In each for-loop, we append the string to the existing array, that is, bag[i]. But after it is done, we need to remove it from the tail of the array string in order for it to try the next option. This is why we use bag[i].replace("A", ""). The same applies to the other six strings.
We come up with a “straightforward” but ugly-looking version as what follows.
Note
BAG – red: 0, blue: 1, white: 2; 3 in the loops represent the three string arrays, that is, the three bags.
The code structure looks too complicated. There are too many nested for-loops. A better idea is to apply a recursive approach to improve its simplicity. Now see a new version:
A palindrome number is a number that reads the same from its left to right as from its right to left.
In the isPalindrome() method, we reverse the number string and compare it with the original number string. If the reversed string turns out to be the same as the original one, it is identified as a palindrome string. For “8558.” its reversed string “8558” is the same as itself.
We introduce StringBuffer class to leverage its reverse() method. Every number within the range [1000, 10000] is converted to a string type, before it is passed to the isPalindrome() method. The solution can be applied to any range of integer numbers.
There is a different way in the method isPalindrome2(), which contains the same functionality as what the isPalindrome() method has. Instead of using StringBuffer, you may simply compare each character from the leading half of one with the trailing half of the original string.
The total count of base-10 three-digit numbers is 900. A three-digit number 124 in base-10 is 147 in base-9, and 103 in base-11; 720 in base-10, 880 in base-9, and 5A5 in base-11.
The crucial method is countBase10Numbers():
private static void countBase10Numbers() {
int count = 0;
for(int i = 100; i < 1000; i++) {
String base9Number = convertToBaseN(i, 9);
String base11Number = convertToBaseN(i, 11);
if (base9Number.length() == 3 &&
base11Number.length() == 3) {
count++;
System.out.println(i + " -> " + base9Number +
"; " + base11Number);
}
}
System.out.println(count + " out of " + (1000 - 100));
}
The supporting method is convertToBaseN().
private static String convertToBaseN(int base10, int n) {
It is actually equivalent to a method with implementation of the switch conditional statement:
private static String convertDigit(int digit) {
String s = "";
switch(digit) {
case 10:
s = "A";
break;
case 11:
s = "B";
break;
case 12:
s = "C";
break;
case 13:
s = "D";
break;
case 14:
s = "E";
break;
case 15:
s = "F";
break;
default:
s = Integer.toString(digit);
break;
}
return s;
}
Obviously, the approach using a string array is simpler.
Problems
1.
Richa and Yashvi are going to Jamaica with their school. They plan on attending a fair where the admission for children is $1.50 and $4.00 for adults. On a specific day, 2,200 people enter the fair and $5,050 is collected. How many children attended? (2017 MathIsCool)
2.
In a mathematics contest with 10 problems, a student gains 5 points for a correct answer and loses 2 points for an incorrect answer. If Olivia answered every problem and her score was 29, how many correct answers did she have? (2002 AMC8)
3.
How many positive integers not exceeding 2001 are multiples of 3 or 4 but not 5? (2001 AMC10)
4.
How many positive three-digit numbers contain exactly two distinct digits (e.g., 343 or 772, but not 589 or 111)? (2006 MathIsCool)
5.
Rebecca goes to the store where she buys five plants. If the store sells three types of plants, how many different combinations of plants can she buy? (2005 MathIsCool)
