Principles of Counting Recitation

Week one

Your TA will work through the following problems with you.

  1. How many six character passwords are there that start with two digits and end with four lowercase letters?
  2. How many five or six character passwords are there that use only lowercase letters?
  3. If there are 1500 teams playing in a tournament, where a team is eliminated after a round in which they lose, how many total games are played in this tournament?

Use your knowledge of the product and sum rules to answer the following questions.

  1. How many ways are there for a person to have three initials?
  2. How many bit strings of length seven begin with two zeros AND end with three ones?
  3. How many permutations of \{a,b,c,d,e,f,g\} start with g and end with a?
  4. How many different ways are there to choose a president, vice president and treasurer out of ten people?
  5. How many ways are there to choose a committee of five people out of nine people?
  6. How many permutations of the letters ABCDEFG contain
  7. If a password is made up of lowercase letters or digits, how many passwords of length six are there that contain AT LEAST two digits?
  8. How many ways can a set of three positive integers less than 100 be chosen?
  9. In how many ways can nine people sit around a circular table, all seats being identical?
  10. If there is a room with 36 people and every person shakes hands with every other person exactly once, how many handshakes are there in all?
  11. In a rectangular grid, how many paths are there to get from (0,0) to (3,3) only moving right or up?
  12. A professor writes 40 discrete mathematics true/false questions. Of the statements in these questions, 17 are true. If the questions can be positioned in any order, how many different answer keys are possible?

Week two

  1. How many permutations of ABCDEFG are there with E preceding G? What about with E preceding G or C preceding A?
  2. How many anagrams of “banana” are there?
  3. A drawer contains 5 blue socks, 4 green socks, 8 red socks, and 2 yellow socks
  4. A group of foreign language students was surveyed about languages they spoke. How many students spoke any of the three languages?
  5. Call a number “prime-looking” if it is composite but not divisibly by 2, 3, or 5. There are 25 prime numbers less than 100. How many prime-looking numbers are there less than 100?
  6. The German Engima machine is a cryptographic device that creates a mapping from the alphabet to itself. This mapping is also based on previous key-presses: A could map to C originally but after more of a message is encrypted it could end up mapping to G. The method to do this are the rotors. Each rotor consists of 26 keys representing the letters of the alphabet. Each rotor forms a bijective mapping from one letter to another. Each rotor passed it’s output to the next in the sequence, and there were three rotors selected from a pool of five. When a key was pressed, one rotor would rotate by one letter. Additionally, every 26 keystrokes a second rotor would rotate as well. This meant that the machine was 26*26*25 periodic. A reflector was used meaning that the encryption and decryption operations were equivalent. However, the implementation used meant that no letter could map to itself. There was also a plugboard that could map a letter to another before and after the rotor process - up to 10 pairs were be used.

To crack these, operators ran many Enigma copies in parallel that ruled out settings that led to logical contradictions.