Concrete Mathematics, problem 3.31

Proving an inequality in two variables, involving the floor function. We draw contour plots, which make this problem almost obvious.

This nice problem was taken from 𝐶𝑜𝑛𝑐𝑟𝑒𝑡𝑒 𝑀𝑎𝑡ℎ𝑒𝑚𝑎𝑡𝑖𝑐𝑠 textbook — problem 31 from the 3rd chapter.

Source: Source: R. L. Graham, D. E. Knuth, O. Patashnik, 𝐶𝑜𝑛𝑐𝑟𝑒𝑡𝑒 𝑀𝑎𝑡ℎ𝑒𝑚𝑎𝑡𝑖𝑐𝑠. 𝐴 𝑓𝑜𝑢𝑛𝑑𝑎𝑡𝑖𝑜𝑛 𝑓𝑜𝑟 𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝑟 𝑠𝑐𝑖𝑒𝑛𝑐𝑒 (2nd ed.), Addison-Wesley Professional, 1994.

[jkid]

floor(x) + floor(y) + floor(x+y) = 2k + 2l + floor(a+b) = 2k + 2l + {0, 1}
floor(2x) + (2y) = 2k + 2l + floor(2a) + floor(2b) = 2k + 2l + {0, 1, 2}
The only possible way for the inequality to be broken is if floor(a+b)=1, which implies at least one of a or b is >.5, which implies at least one of floor(2a) or floor(2b) is 1, completing the proof.