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)
    if haskey(sub_multiset, parts[end])
        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.

Moebius Noodles

小時候學數學的時候都是有一點填鴨式的在學習,從九九八十一到初階歐幾里得幾何的圓規和尺至對邊除以斜邊幾乎都是在背和作習題,甚少去將概念做延伸和應用。去加拿大之讀高中後感覺也沒有變多少,只是用英文重新學一次加上一點有 TI-83 陪伴的微積分罷了,總是有種學的用不上的感覺。雖然我很喜歡數學,但總覺得一路學習過來缺少了什麼。

好像是去年從某一篇文章中看到一些美國數學教育家對現代數學教育的一些批判,詳細內容忘記了,但令我印象深刻的是其作者提到:

現代數學教育往往先教孩童一些對人類而言最難的數學,然後把對人類而言最比較簡單而有趣的數學留到最後,讓許多幼年學童感覺數學很難而灰心放棄。事實上,微積分還有抽象代數的概念往往比算法複雜而無趣的計算題來得容易。人腦強在於它對抽象的概念的理解能力,而不是它的算數能力;算數能力是電腦的領域。

我對此頗有同感:會算 143+49 或是 6 times 13 固然重要,但是懂得無限大的概念或是了解對稱和循環的概念是不是更重要呢?但是這些抽象的數學反而都是到了比較大的年紀才會正式學到,但是有些兒童往往在學加減乘除時就對數學失去興趣,認為數學是個枯燥乏味,滿是計算的學科。

我讀到的那篇文章中,作者提到了一本書叫做 Moebius Noodles, 是一本教導父母如何啓蒙兒女(六到十二歲?)的數學思維的書,我看了幾章。其中一章講的是數數,像是數 1, 2, 3 dots 數一條魚兩條魚固然簡單,但很無趣,不如把小孩喜歡的故事變成數數字的機會。三隻小豬故事中有一隻大野狼,兩棟被垮掉的房子,三隻小豬等等(長一點的故事比較好找。)小嬰兒可以分辨在五以下的數量,所以可以貼便利貼在嬰兒的腳上,玩具的輪子上,或是他的小熊們上面,幫助孩童認識數量。類似下面的圖


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

或是在家裡用跟數學相關的圖畫勞作藝術做裝飾(或是例如自己印一個巨大的 infty 符號等等的。)

還有一些電視節目(雖然我覺得不是很多)電視節目會融入一些數學題材,例如美國卡通 Futurama (中譯:飛出個未來)第六季第十集就是一個例子。卡通中的問題既是有趣,又可以介紹高階數學中較簡單的概念給小孩。

希望墨兒就算數學不好,也可以開心得,不要害怕得數學。

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.

Emma More Yang - First Day
Emma More Yang – First Day

Emma More Yang - Day 1