CS-113. Problem Set 6

Due Tuesday, Nov.21.

Numbers and their representations

Here is a nice game: www.milaadesign.com/wizardy.html. Try it. And then
1. Give a concise explanation of how it works (i.e. how the game "reads" your mind).
2. Translate this game to binary and hex notations (i.e. base 2 and base 16) - how would you have to change it so that it still "guesses" the correct symbol?
Be concise in your explanations and provide proofs where necessary; you should not need more than a paragraph or two - a half a page at most with the proofs.

(For your entertainment you can also look at the other puzzle similar to what we saw in the beginning of the course: www.milaadesign.com/triangle.html)

Permutations, Combinations, and other counting

How many different arrangements are there for the letters of the word ARRRRRANGEMENT? (yes, I meant to spell it like that;-)
How many different arrangements of arbitrary length can you make out of the letters of the word LENGTH?
How many different k-substrings (substrings of length k) does the word LENGTH have for each of k=1, 3, and 6? How about word ARRRRRANGEMENT? (a 1-substring "N" is to be counted once even though it appears in two places, and so on)
A Boolean n-input m-output function f is a function which takes n Boolean inputs and produces a m Boolean outputs (if m=1 then we call it predicate); we write f : {0,1}ⁿ -> {0,1}^m. How many different such functions are there?
Hint: start with m=1.
How many ways are there to choose two distinct numbers from {0,1,2,...,100} so that their sum is odd? How about three distinct numbers whose sum is even?
"Dumb Nim": In the past we had a game of 2-Nim where there are two piles of matches (or cookies:). Now let us consider a really "dumb" version of the game: 1-Nim. In this version there is only one pile, and each move can take any number of matches from this pile. It is of course too easy to win in this game, so we will not worry about winning. Instead, compute the number of different games possible when you start with n matches. In other words, compute the number of different sequences of natural numbers (>0) whose sum is n (order matters!).
Extra credit: How many different games of 2-Nim are possible if you start with n matches in each pile (each move can remove >0 matches from only one pile).
You are driving on an empty divided highway listening to Tom Waits "On the wrong side of the road". Once in a while, you get too swayed by the music and cross over to the wrong side of the road. Some time later you come to your senses and cross back to the right side (we are not in Britain, so there is no ambiguity:). Between your starting point and destination there are n breaks in the line separator where you can cross over.
1. How many different routes can you possibly take (assume you always start on the right side of the road)?
  Write a simple pseudo-code algorithm to enumerate these routes.
2. How many different routes can you take if you want to arrive at your destination on the right side of the road?
  Write a simple pseudo-code algorithm to enumerate these routes.
3. Extra Credit: There are k>n highway patrol cars that you meet on your way, at least one between any two cross-over points (and between the start/end and the nearest cross-over). Each gives you a ticket either for speeding or for driving on the wrong side of the road, depending on the side of the road you were driving just before meeting the police officer (assume that when you are on the wrong side, the police officer is so excited to see you she does not notice your speed). Suppose you start on the right side of the road and cross over exactly n times. How many different sequences of tickets are there possible to be collected by you (each sequence may correspond to a different set of positions of the police cars)?
  [Hint: you can imagine the k policemen to be stationary, and you change the locations (with respect to the police cars) of the n crossovers.]
  Now take another look at the 2-Nim problem above.