6.042J Study Guide - Midterm Guide: Coin Flipping, Waste Collector, Lord Voldemort
22 May 2016
School
Course
Professor
Document Summary
We know the total number of digits is 1 and there are ( -1) numbers without a 1. The -1 is for 0, which is not in our range. To get the amount of numbers containing a 1, we compute the total number minus the number without. There are 20 books on a shelf. Describe a bijection between ways of choosing 6 of these books so that no two adjacent books are selected and 15 bit strings with exactly six 1"s. A selection of six books among twenty can be represented by a 20-bit string with exactly six 1"s that indicate the selected books. We want to find a bijection between 20-bit strings with six nonadjacent 1"s and 15-bit strings with six. In a string, s, with six nonadjacent 1"s, all but the final 1 must have a zero to its right.
