Homework 2 Solutions#

The write-ups below model the amount of explanation expected in a complete handwritten submission.

A constrained integer sum#

Problem. How many integer solutions are there to subject to

Solution.

Approach. Find the smallest possible value of the left-hand side.

Because the variables are integers, the strict inequalities imply Any five integers satisfying these lower bounds must have sum at least The required sum is 19, which is smaller than this minimum. Therefore there are solutions.

A route through specified points#

Problem. A northeast lattice path uses only unit steps to the right or unit steps up. How many northeast lattice paths from to pass through each of the points

Solution.

Approach. Break the path at the three required points and count the four segments independently.

The required points occur in northeast order, so every path through them breaks uniquely into segments with the following counts: The choices of segments are independent, so the product rule gives

Anagrams with letters and digits#

Problem. How many anagrams of ABRACADABRA676767 have every digit before every letter?

Solution.

Approach. Arrange the six digits in the first six positions and the eleven letters in the last eleven positions.

The condition that every digit occurs before every letter forces the six digits to occupy the first six positions and the eleven letters to occupy the last eleven positions. The digit block contains three copies of 6 and three copies of 7, so it has distinct arrangements. In ABRACADABRA, the letter occurs five times, and occur twice each, and and occur once each. Its distinct arrangements number Each choice for the digit block can be followed by each choice for the letter block. Hence the number of anagrams is

Drawing colored balls#

Problem. A bag contains an unlimited supply of red balls and blue balls, and exactly 10 yellow balls. A person draws 15 balls.

  1. How many possible outcomes are there if the order of the draws is irrelevant? Thus an outcome records only how many balls of each color are drawn.

  2. How many possible outcomes are there if the balls are drawn one at a time and placed in a row?

Solution.

(1) Order is irrelevant. An outcome is a triple of nonnegative integers satisfying . If yellow balls were unlimited, stars and bars would give outcomes.

The impossible outcomes have . Setting gives so there are impossible outcomes. Therefore

(2) The balls are placed in a row. If yellow balls were unlimited, there would be color strings. An impossible string has at least 11 yellow positions and therefore has nonyellow positions for some .

For a fixed , choose the nonyellow positions in ways and color them red or blue in ways. Thus the number of impossible strings is Subtracting these strings from all color strings gives

Passwords with increasing digits#

Problem. A password has length 12. Each character is either one of the 26 lowercase letters or one of the decimal digits . A password contains exactly three digits; those three digits are distinct and appear in increasing order when read from left to right. The remaining nine characters are letters, which may repeat.

How many passwords satisfy these conditions?

Solution.

Approach. Choose the digit positions, choose the digit values, and then fill the letter positions.

First choose the three positions occupied by digits; there are choices. Next choose three distinct digit values from the ten available digits, giving choices. Once the positions and values are chosen, there is exactly one way to put the digits in increasing order: the smallest chosen digit goes in the leftmost digit position, the next smallest in the next digit position, and the largest in the rightmost digit position.

The nine letter positions can be filled in ways. Thus