A bit string is a finite sequence of 0\'s and 1\'s. How many bit strings have le
ID: 2969436 • Letter: A
Question
A bit string is a finite sequence of 0's and 1's. How many bit strings have length 8? 28 = 256 How many bit strings of length 8 begin and end with a 1? 28-2=26 How many bit strings of length 8 have four 0's and four 1's? 8! / 4!4! =40,320 / 576 = 70 Give a proof by contradiction or proof by contraposition for the statement: If x is an irrational number, then 2 + 3x is also irrational. Consider the equation x1 + x2 + x3 + x4 = 25. How many solutions are there such that each xi, is a nonnegative integer? How many integer solutions are there such that x1 1, x2 2, x3 3, and x4 4? How many integers from 1000 to 9999 (.i.e., 4 digit numbers) divisible by 5? How many integers from 1000 to 9999 are divisible by 5 and have distinct digits? (Recall that an integer is divisible by 5 if and only if its last digit either 0 or 5.)Explanation / Answer
14. Assume that 2 + 3x is rational. Then, it may be written as p/q p, q integers, q not equal to 0.
2 + 3x = p/q
Then, p/q - 2 = 3x
p/q - 2q/q = 3x
(p-2q)/q = 3x
(p-2q)/(3*q) = x
p-2q is an integer, and 3*q is an integer not equal to 0, so
(p-2q)/(3*q) is rational
Thus, x is rational.
This is a contradiction.
Thus, if x is irrational, so is 2 + 3x.
15.
There are many ways to answer this. Most rely upon showing a 1-1 relationship with a known combinatorial result.
For example, separate an ordered line of 25 balls by 3 walls. balls to the left of the first wall are x1, between walls 1 and 2 x2, between walls 2 and 3 x3, and to the right of wall 3 x4.
Clearly, moving the balls gives possible value of x1, x2, x3, and x4
The number of ways to have 3 walls among 25 balls is equivalent to choosing 3 from 25+3=28, so the answer is
C(28,3) = 3276
b)x1 >= 1, x2 >= 2, x3 >= 3, and x4 >= 4
This is equivalent to choosing x1, x2, x3, and x4 nonnegative where they sum to less than 25 - 1 - 2- 3 - 4 = 15, then adding 1, 2, 3, and 4 respectively (thus, we get back to the inequalities and adding to 25.
Then, the solution, similar to the one above, is C(15+3, 3) = C(18, 3) = 816
16. (10000 - 1000)/5 = 9000/5 = 1800 (Since the fraction is an integer, we don't have to worry about the starting point or ending point to know the answer; we add 1 because the number of integers is 1 greater than the difference between the smallest and largest.
Another way, more similar to the argument below: the 1s digit may be 0 or 5, the tens and 100s digit may be 0-9, and the 1000s digit may be 1-9, and 9 * 10 * 10 * 2 = 1800
b) How many between 1000 and 9999 are divisible by 5 and have distinct digits. The final (1s) digit must be 5 or 0
If the final digit is 0, then we have P(9,3) (we can choose an ordering of the digits from 1 to 9) = 9*8*7 = 504
Next, donsider the final digit as 5.
The leading (1000s) digit may be any of 1-9 excluding 5 (8 possibilities), then the 100s digit may be any of the 8 digits (5 and the leading digit) not selected, and the 10s digit may be any of the 7 digits not selected, and
8*8*7 = 448
504 + 448 = 952