# CS-113. Problem Set 6

Due Tuesday, Nov.21.

## Numbers and their representations

1. 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

1. How many different arrangements are there for the letters of the word ARRRRRANGEMENT? (yes, I meant to spell it like that;-)
2. How many different arrangements of arbitrary length can you make out of the letters of the word LENGTH?
3. 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)
4. 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}n -> {0,1}m. How many different such functions are there?