{"id":2445,"date":"2018-09-23T18:29:09","date_gmt":"2018-09-23T23:29:09","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2445"},"modified":"2018-09-23T18:29:09","modified_gmt":"2018-09-23T23:29:09","slug":"paths-to-work","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/paths-to-work\/","title":{"rendered":"Paths to work"},"content":{"rendered":"

This Riddler puzzle<\/a> is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem.<\/p>\n

\nThe streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How many different paths are there? (Assume you don\u2019t take paths that are longer than required). Your home is M blocks west and N blocks south of the office.\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

See the diagram below, where we start at $A$ and we’d like to get to $B$. In this version, Since we can only walk along roads, we must move East a total of $M$ times and north a total of $N$ times to arrive at our destination. This means we must walk $M+N$ blocks to get to work. Backtracking (moving south or west) will necessarily lead to paths that are longer than necessary, so we can exclude these cases.<\/p>\n

\"\"<\/a><\/p>\n

Each path from A to B is a sequence of $M$ “easts” and $N$ “norths” in some order. In the example above, $M=4$ and $N=3$. The solution I traced is:
\n\\[
\n\\{\\text{east, east, north, north, east, north, east}\\}
\n\\]Here is another way to think about the problem: out of the $M+N$ decisions we must sequentially make (moving east or moving north), which $M$ of them will be “east”? The answer is the binomial coefficient<\/a>!<\/p>\n

$\\displaystyle
\n\\text{Ways to work} = \\binom{M+N}{M} = \\frac{(M+N)!}{M!\\cdot N!}
\n$<\/span><\/p>\n

To answer the specific problem posed with $M=5$ and $N=10$, the number of different paths from $A$ to $B$ is $3003$.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem. The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, … Continue reading “Paths to work”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2448,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[9,29,2],"class_list":["post-2445","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-classics","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2445"}],"version-history":[{"count":4,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2445\/revisions"}],"predecessor-version":[{"id":2450,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2445\/revisions\/2450"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2448"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}