Given that ⌈ x ⌉ &lt; x + 1, give a proof by contradiction that if n items are placed in m boxes then at least one box must contain at least ⌈ n m ⌉ items.

Question

Given that   ⌈  x  ⌉  &amp;lt;  x  +  1, give a proof by contradiction that if   n items are placed in   m boxes then at least one box must contain at least       ⌈                  n        m              ⌉   items.

Paityn Arroyo · Accepted Answer

Suppose for the purpose of contradiction that we can place the n items in the boxes such that the maximum number of items in any one box is       ⌈          n      m        ⌉    −  1  =      ⌈          n      m        −    1    ⌉  .Then using       n    ′   to count up total number of items placed in boxes we see       n    ′    ≤  m  ⋅      ⌈          n      m        −    1    ⌉   and from the given inequality we have       n    ′    &amp;lt;  m  ⋅      (          n      m        −    1    +    1    )    =  m  ⋅      n    m    =  nand       n    ′    &amp;lt;  n is a contradiction, since we assumed all   n items were placed.Thus the number of items in some box must be greater than the assumption, that is       ⌈          n      m        ⌉   as required.

Given that ⌈x⌉<x+1, give a proof by contradiction that if n items are placed in m boxes then at least one box must contain at least ⌈n/m⌉ items.

Open question

Answer & Explanation

New Questions in High school geometry