{"id":211,"date":"2018-11-09T12:56:05","date_gmt":"2018-11-09T18:56:05","guid":{"rendered":"http:\/\/blogs.acu.edu\/mu_sigma\/?p=211"},"modified":"2019-01-25T14:27:20","modified_gmt":"2019-01-25T20:27:20","slug":"problem-9-fat-setty-november-9-2018","status":"publish","type":"post","link":"https:\/\/blogs.acu.edu\/mu_sigma\/2018\/11\/09\/problem-9-fat-setty-november-9-2018\/","title":{"rendered":"Problem 9 &#8211; Fat Setty &#8211; November 9, 2018"},"content":{"rendered":"<h3><strong>Fat Setty<\/strong><\/h3>\n<p><i>This problem was submitted by Dr. Jason Holland.<\/i><\/p>\n<p>Let <i>n<\/i> be a positive integer. What is the largest number of elements that a set of integers from 1 through 2<i>n<\/i> can have so that no one element in the set is divisible by another element in the set?<\/p>\n<p>Submit your answers to mathpotw@acu.edu. \u00a0Details for submissions can be found\u00a0<a href=\"http:\/\/blogs.acu.edu\/mu_sigma\/2018\/08\/28\/problem-of-the-week-competition\/\">here<\/a>.<\/p>\n<p>There was one correct solution to this problem submitted by Wyatt Witemeyer.<\/p>\n<p><span style=\"font-size: large\">Solution to <b>Fat Setty<\/b><\/span><\/p>\n<p>We show that such a set can have at least <i>n<\/i> members by giving an example. In the set {<i>n<\/i>+1, <i>n<\/i>+2, <i>n<\/i>+3, &#8230; , 2<i>n<\/i>}, it is clear than no member is a factor of another member, and this set has <i>n<\/i>members.<\/p>\n<p>To show that no larger set can be found, we suppose that we <b>can<\/b> find a larger set, and argue to a contradiction. So suppose D is a subset of {1, 2, 3, &#8230; , 2<i>n<\/i>} for which no element in D is divisible by another element in D, and suppose D has <i>m<\/i> members, with <i>m<\/i> &gt; <i>n<\/i>. Let <i>r<\/i> denote the number of elements that are in both D and {1, 2, 3, &#8230; , <i>n<\/i>}. Then <i>r<\/i> is larger than 0. Now if <i>a<\/i> is in both D and {1, 2, 3, &#8230; , <i>n<\/i>} then 2<i>a<\/i> is not in both D and {<i>n<\/i>+1, <i>n<\/i>+2, <i>n<\/i>+3, &#8230; , 2<i>n<\/i>}. So the number of &#8220;slots&#8221; available in {<i>n<\/i>+1, <i>n<\/i>+2, <i>n<\/i>+3, &#8230; , 2<i>n<\/i>} for the members of D that are not in {1, 2, 3, &#8230; , <i>n<\/i>} is at most <i>n &#8211; r<\/i>. But <i>n &#8211; r<\/i> &lt; <i>m &#8211; r<\/i>, which is the number of members of D that <b>must<\/b> be in {<i>n<\/i>+1, <i>n<\/i>+2, <i>n<\/i>+3, &#8230; , 2<i>n<\/i>}. This is a contradiction, and the result is proved.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Fat Setty This problem was submitted by Dr. Jason Holland. Let n be a positive integer. What is the largest number of elements that a set of integers from 1 through 2n can have so that no one element in the set is divisible by another element in the set? Submit your answers to mathpotw@acu.edu. [&hellip;]<\/p>\n","protected":false},"author":130,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[181534],"tags":[],"class_list":["post-211","post","type-post","status-publish","format-standard","hentry","category-problem-of-the-week"],"_links":{"self":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/211","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/users\/130"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/comments?post=211"}],"version-history":[{"count":2,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/211\/revisions"}],"predecessor-version":[{"id":215,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/posts\/211\/revisions\/215"}],"wp:attachment":[{"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/media?parent=211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/categories?post=211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.acu.edu\/mu_sigma\/wp-json\/wp\/v2\/tags?post=211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}