## Make a Dollar and Pave a Road

A popular interview questions involving programming and combinatorics is the Making a Dollar problem, Generally stated as follows:

Making a Dollar Given unlimited numbers of 1, 5, 10, 25, and 50-cent denomination coin, how many ways are there to make a dollar.

We can count the number of ways to mix the coins into a dollar in two different ways: 1) the biggest denomination is in the mix, and 2) the biggest denomination is not in the mix. If the biggest denomination is in the mix, then let us use one coin of the biggest denomination, and count the number of ways to make the remaining amount using using all available coins. If it is not in the mix, then let us calculate the number of ways to make a dollar using all but the coins of the biggest denomination. Let $f(n,S)$ be the number of ways to make $n$ using coins with denominations in $S = \{d_1, \dots, d_n\}$, then $f(n, S) = f(n - d_n, S) + f(n, S \setminus \{d_n\})$. This recursive relation needs boundary condition of when the amount to make is less than or equal to zero, and when the set of denominations is empty. These are respectively $f(0, S) = 1$, $f(n, S) = 0, n < 0$, and $f(n, \varnothing) = 0$. The first boundary condition says that we have just a way to make the exact change. The second boundary condition says that we have not been able to found an exact change because the denomination we just used is too large. The last boundary condition says that we have used up all possible denominations and still cannot make the change.

Since I am in the process of learning the Julia language, I decided to code this up using Julia while ignore the issue of efficiency. WordPress does not have syntax highlighting for Julia yet, so…

function const_comb(sum::Int, parts::Array{Int})
if sum == 0
return 1
end
if sum < 0 || length(parts) < 1
return 0
end
if(n==0 || all(i-> i==0,r))
return 1
else
return exp(lfact(n) - sum(lfact(r)));
end
end


This problem can be slightly generalize this way. Suppose that the order in which the coins are used to make the dollar matters, for example, $\{1, 3, 1, 1\}$ is different from $\{1, 1, 1, 3\}$, then how many ways can we make a dollar? It may seem that we need to keep track of the way we get to the current state and count each way separately. Turns out this is not necessary. We can recycle the algorithm above, but instead of return 1 when we have the the exact change, we return the number of permutations of the $\{1, 1, 1, 3\}$. It is easier to model permutation with repetition with a multi-set. A multi-set is a collection of objects that need not be distinct. a multi-set $M =\{a_i \cdot d_i, \dots a_k \cdot d_k\}$ where $k, a_i$ are non-negative integers and $d_i$ are distinct objects, contains $a_i$ of $d_i$. From combinatorics theory, the number of ways to form a permutation on a multi-set $M$ such that $\sum_{i=1}^{k} a_i = a$ is $\frac{a!}{a_1!\dots a_k!}$. Let us first code up the above express for multi-set permutation. Since it involves quite a bit of factorials, special care should be taken to avoid integer overflow.

function nPr(n::Int, r::AbstractArray{Int,1})
if(any(i->i>n, r))
return 0
end
if(n==0 || all(i-> i==0,r))
return 1
else
return exp(lfact(n) - sum(lfact(r)));
end
end


Now we simply need to keep track of the multi-set of numbers of coins of each denomination, and count the permutation when we have the exact change or return 0 otherwise. The distinct nature of the objects $d_i$ makes the use of a dictionary in our code a natural choice.

function const_comb_rep(sum::Int, parts::AbstractArray{Int, 1}, multiset::Dict)
if sum == 0
return nPr(sum(collect(values(multisite))), collect(values(multiset)))
end
if sum  0 || length(parts)  1
return 0
end
sub_multiset = copy(multiset)
sub_multiset[parts[end]] = sub_multiset[parts[end]] + 1
else
sub_multiset[parts[end]] = 1
end
return const_comb_rep(sum - parts[end], parts, sub_multiset) + const_comb_rep(sum, parts[1:end-1], multiset)
end


where line 5 should be sum < 0 || length(parts) < 1 where for some very bizarre reasons WordPress just cannot render correctly and have cost me several hours to finally give up trying.

running with some test input get

const_comb_rep(7, [1, 2, 3], Dict())
44.0
[const_comb_rep(n,1:n, Dict{Int,Int}()) for n = 1:10]
10-element Array{Union{Float64,Int64},1}:
1.0
2.0
4.0
8.0
16.0
32.0
64.0
128.0
256.0
512.0


Here the multi-set is modelled as a dictionary with keys being the distinct object and value being the number of object. As we recurse, the dictionary keeps tract of the number and denomination of the coins used. Finally when we have an exact change, the number of ways to arrange them is computed and returned back.

Note that the number of ways to make Integer $n$ using numbers from $1 \dots n$ is $2^{n-1}$.

Of course, in real life one does not care the order of which changes are returned to make up the right amount. The problem is perhaps more suitable to the pave a road problem:

Paving a Road Find the number of ways to pave a $1 \times 7$ block of road using $1 \times 1$, $1 \times 2$, and $1 \times 3$ blocks, assuming each block is indistinguishable.

The above algorithm gives 44 ways, and one can actually print out each way if one add a print command inside the if sum == 0 statement.

## Random Walk Down n-gon

I found this problem to be quite interesting.

Random Walk on a Square Consider a random walk around the edges of a square. From any vertex, the probability of moving to any adjacent vertex is 0.5. Suppose the walk stops as soon as after all traversing through all the vertices, you return to your starting vertex. What is the expected path length?

The solution I saw involves breaking the problem down into several possibilities, and find the expected path length and the probability of each possibility, then sum them up. This method seem to work with the case when the number of nodes are small, but such method seem to become intractable when the square is generalized to a regular n-gon.

Indeed someone has already thought of that, and wrote a paper about it. What I particularly like about this paper is that it transform the problem into a gambler’s ruin problem, which was my first thought when I read the problem.

## The 100 Hat Puzzle

I am starting to keep a list of things I learned throughout the day. Nothing horrifies me more than realizing at the end of a day that nothing has been learned, not even the trivial things. Keeping track of them will probably alleviate this kind of anxiety. Today I learned that there are generalizations to the 100 hats puzzle.

I read about the 100 hat puzzle from the NYT a while back. Today in a conversation I learned that the problem have been generalized perhaps several times, and that there are quite a few variants of the problem. The problem goes like this, copied from the NYT article:

One hundred persons will be lined up single file, facing north. Each person will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the color of the hat on 99 persons in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat.

Beginning with the last person in line, and then moving to the 99th person, the 98th, etc., each will be asked to name the color of his or her own hat. If the color is correctly named, the person lives; if incorrectly named, the person is shot dead on the spot. Everyone in line is able to hear every response as well as hear the gunshot; also, everyone in line is able to remember all that needs to be remembered and is able to compute all that needs to be computed.

Before being lined up, the 100 persons are allowed to discuss strategy, with an eye toward developing a plan that will allow as many of them as possible to name the correct color of his or her own hat (and thus survive). They know all of the preceding information in this problem. Once lined up, each person is allowed only to say “Red” or “Blue” when his or her turn arrives, beginning with the last person in line.

Your assignment: Develop a plan that allows as many people as possible to live. (Do not waste time attempting to evade the stated bounds of the problem — there’s no trick to the answer.)

There are countless number of papers (too many), presentations, master thesis, and blogs (such as this) that talk about the solutions to this set of problems. I also learned a nice application of the axiom of choice to this problem.

。。
。。。
。。。。
。。。。。
。。。。。。

## Emma More Yang

Two weeks ago I returned to Taipei to help my wife Summer with her pregnancy, and, well, to “be there” when the kid was born. The expected date was July 4th, 2014, but I suppose the child couldn’t wait for another day. Summer felt some mild contraction and we were at the hospital by 5:00am. It went by pretty quickly afterwards, and Emma More Yang was born on July 3rd, 2014 at 8:47am.

Naming her took a while. We started thinking about her English name a few months ago when we learned the gender. The English name is the easy part, and we took care of it pretty quickly. The only criteria is that our entire family should be able to pronounce it without the need of a correction. In our families, that means that the name can’t contain “r”, “l”, “x”, “h”, “ch”, “sh”, and “th”, can’t have two adjacent vowels or something close to that (like “Fiona”, “Chloe” and “Jewel”,) and should have at most two syllables and no more than 5 or 6 letters. Summer proposed the name “Emma”. Since it satisfies all of the above and we like the name a lot (I personally like both Emma Stone and Emma Watson, so that suits me,) we decided to call her Emma. According to ourbabynamer.com, it has been ranked number 1 or 2 most popular names since 2003 in the United States and number 1 in Canada in the year 2013… not that we knew this before.

Chinese name is trickier. On the one hand there is a sizeable array of Chinese characters that appear more often in names of female infants born between 1970 and 2000 in Taiwan. Characters such as 婷, 琪, 宜, 玲, 君 and their phonetic equivalents were quite commonly used. Taiwan’s Ministry of the Interior conduct a survey in 2012 that is quite comprehensive. Another set of Chinese characters with not a small intersection with the above are those that also appear in Japanese names, such as 美, 奈, 亞, 惠. There is also the set of female celebrity names, characters in names that become popular because some celebrities have or use them as their names or screen names, such as 薰, 妍, 蔓, 蕾, 詩; my wife is particularly fond of these characters. In the same survey, I also learned that the most commonly used characters in female infant names in Taiwan after 1990s are 品, 蓁, 妤, 詩, 涵, 妍.

Since Chinese name has more meaning to me personally, I want to give her a name that embodies some of myself and my wish for her. I like to read and write, and have lots of interest in arts in general, the character 墨 (meaning ink for those Chinese(ly) challenged) come to my mind. I suggest it to my wife and she seems to like it too. The only problem is that even though this character does not usually appear in names, it still possesses a masculine connotation. I need another characters to soften it.

To soften the name I need a more feminine character. I thought I could use a character that my wife like, such as 妍. However, it combines to 墨妍, pronounced the same as the now famous Chinese author 莫言 (Mo Yan) which is fine but honestly none of the characters in his novels are someone I want my daughter to become, or their experience felt; 墨妤 sounds the same as 墨魚 (Cuttlefish,) another no go… and as for 蕾, I don’t feel the kind of connection I am looking for.

I thought the character 兒 (meaning children, son, or a term of endearment if following another character.) reflect what I want her to be, always having the heart of a child, explorative, interested, and harmless. It also occurs to me that 墨兒 pronounce similarly to the English word “more”; more will be bestowed to you; more happiness and prosperity will come to you; and in Christianity, 2 Corinthians 9:8 says “And God can give you more blessings than you need. Then you will always have plenty of everything — enough to give to every good work”. This connection to the English word more is the one that settles the issue. 墨兒 would be her Chinese name and “More” would be her middle name.

Here is Emma More Yang, 楊墨兒 in her first 12 hours of life.