{"id":1873,"date":"2017-03-19T16:55:34","date_gmt":"2017-03-19T21:55:34","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1873"},"modified":"2017-03-20T10:48:47","modified_gmt":"2017-03-20T15:48:47","slug":"convex-ranches","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/convex-ranches\/","title":{"rendered":"Convex ranches"},"content":{"rendered":"

This Riddler puzzle<\/a> is about randomly generating convex quadrilaterals.<\/p>\n

Consider four square-shaped ranches, arranged in a two-by-two pattern, as if part of a larger checkerboard. One family lives on each ranch, and each family builds a small house independently at a random place within the property. Later, as the families in adjacent quadrants become acquainted, they construct straight-line paths between the houses that go across the boundaries between the ranches, four in total. These paths form a quadrilateral circuit path connecting all four houses. This circuit path is also the boundary of the area where the families\u2019 children are allowed to roam.<\/p>\n

What is the probability that the children are able to travel in a straight line from any allowed place to any other allowed place without leaving the boundaries? (In other words, what is the probability that the quadrilateral is convex?)<\/p><\/blockquote>\n

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

\n

The only way the quadrilateral can be nonconvex is if one of its vertices is “inward”. In other words, an internal angle of the quadrilateral is greater than 180 degrees. The figure below shows an example of a nonconvex case (on the left) and a convex case (on the right). For the nonconvex example, the vertex labeled K is inward.<\/p>\n

\"\"<\/p>\n

It’s clear that at most one vertex can be inward. So, by symmetry, we can write the following statement regarding the probability of the quadrilateral being convex.
\n\\begin{align}
\n\\mathbb{P}(\\text{convex}) &= 1-\\mathbb{P}(\\text{nonconvex}) \\\\
\n&= 1-\\mathbb{P}(\\text{one vertex is inward})\\\\
\n&= 1-4\\cdot\\mathbb{P}(\\text{a particular vertex is inward})
\n\\end{align}So let’s calculate the probability of a particular vertex being inward. This only depends on the positions of the two adjacent vertices. Consider the diagram below and opposite vertices $J(-a,b)$ and $L(p,-q)$ where $0 \\le a,b,p,q \\le 1$ are the coordinates. The vertex $K(u,v)$ with $0 \\le u,v \\le 1$ will be inward if it ends up in the shaded triangle. The probability of this occurring is equal to the area of the triangle.<\/p>\n

\"\"<\/p>\n

Since we’d like to find the total probability of $K$ being inward, we must find the expected area of the shaded triangle with respect to the points $J$ and $L$ being uniformly randomly chosen in their respective regions. The area is $A=\\tfrac{1}{2}xy$ where $x$ and $y$ are the intersections with the axes indicated. Calculating $x$ and $y$ amounts to finding the intersection of the line segment $JL$ with the axes. A bit of algebra reveals the formula:
\n\\[
\nx = \\frac{bp-aq}{b+q},
\n\\qquad
\ny = \\frac{bp-aq}{a+p}
\n\\]To find the expected area, we integrate $\\frac{1}{2}xy$ over $0\\le a,b,p,q \\le 1$. We must take care to account for the case where $x$ and $y$ are both negative, which we do by dividing the result by $2$. Finally, we substitute the result into the formula for the probability of convexity and we obtain:
\n\\begin{align}
\n\\mathbb{P}(\\text{convex}) &= 1-4\\cdot\\mathbb{P}(\\text{vertex }K\\text{ is inward})\\\\
\n&= 1-4 \\int_0^1\\int_0^1\\int_0^1\\int_0^1 \\frac{1}{2}\\cdot\\frac{1}{2}\\,x\\,y\\,\\,\\mathrm{d}a\\,\\mathrm{d}b\\,\\mathrm{d}p\\,\\mathrm{d}q\\\\
\n&= 1-\\int_0^1\\int_0^1\\int_0^1\\int_0^1 \\frac{(bp-aq)^2}{(a+p)(b+q)}\\,\\mathrm{d}a\\,\\mathrm{d}b\\,\\mathrm{d}p\\,\\mathrm{d}q\\\\
\n&=\\frac{1}{6}(11-8\\log2)\\\\
\n&\\approx 0.909137
\n\\end{align}So the probability that the quadrilateral is convex is about 90.9%.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This Riddler puzzle is about randomly generating convex quadrilaterals. Consider four square-shaped ranches, arranged in a two-by-two pattern, as if part of a larger checkerboard. One family lives on each ranch, and each family builds a small house independently at a random place within the property. Later, as the families in adjacent quadrants become acquainted, … Continue reading “Convex ranches”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1876,"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":[10,8,2],"class_list":["post-1873","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-geometry","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1873","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=1873"}],"version-history":[{"count":13,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1873\/revisions"}],"predecessor-version":[{"id":1875,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1873\/revisions\/1875"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1876"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1873"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1873"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1873"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}