These are two quite interesting problems.
First note that the maximum number of elements in a spacy set can be
. Thus, we break the problem into cases:
CASE 0: The Empty Set
The problem says to include this set, so we must. There is
set in this case.
CASE 1: One Element
We can choose any of the twelve numbers in the set for a total of
sets in this case.
CASE 2: Two Elements
This is where things get tricky. According to the spacy condition, each number
in a spacy set, where
, must be placed such that
for
This is because if we pick the number
to be in the set, we can not have any of the numbers
in the set as well. How do we count the number of sets with such a restriction? The answer is to simply remove it.
Let's consider a set of
as shown:
![\[\text{XXXXXXXXXX}\]](//latex.artofproblemsolving.com/4/f/f/4ff219a2e86c9f44a778fd4598bf222cb4ae78d8.png)
I claim that the number of elements in the entirety of Case 2 is equal to the number of ways to select two
from this set of
. Why is this the case? Well, once we select the two
, we can squeeze two
in between our chosen
. An example is shown here:
![\[\text{XXXXX}\boxed{\text{X}}\boxed{\text{X}}\text{XXX}\implies \text{XXXXX}\boxed{\text{X}}\color{red}\text{XX}\color{black}\boxed{\text{X}}\text{XXX}\]](//latex.artofproblemsolving.com/1/a/3/1a3d45ec2e9dc49fbfdf5e9acd18ce8952f11c2f.png)
By adding these letters in this location, we separate our two selections by at least
, all while having a total of
elements, which is what we want! Therefore, the 1-1 correspondence is established, and the number of sets in Case 2 is simply
.
CASE 3: Three Elements
We do the same thing, except start off with
instead of
. This is because there are two places to put two
when we select three of them, and we want the total number of
to still be
at the end. Am example is shown here:
![\[\text{XX}\boxed{\text{X}}\text{X}\boxed{\text{X}}\boxed{\text{X}}\text{XX}\implies \text{XX}\boxed{\text{X}}\color{red}\text{XX}\color{black}\text{X}\boxed{\text{X}}\color{red}\text{XX}\color{black}\boxed{\text{X}}\text{XX}\]](//latex.artofproblemsolving.com/b/c/d/bcd1f806c872b2a24632f4f1c6577e497f38b0da.png)
By this 1-1 correspondence, the number of sets in Case 3 is the number of ways to select
from a set of
, which is simply
.
CASE 4: Four Elements
I think you know what the pattern is by now. We only need six
to begin with now, and we want to select four of them. The number of sets here is
.
Adding all of these values up gives us our desired answer:
.We proceed by induction.
BASE CASE: 
Here, we have
, which is true.
INDUCTIVE STEP:
Assume that
for some
.
Remark that since
, it is obvious that
. Adding
to both sides gives us
, so
. Rearranging this gives us
![\[\dfrac{1}{(2k+1)(2k+2)}\geq \dfrac{2}{(3k+1)(3k+4)}.\]](//latex.artofproblemsolving.com/3/d/5/3d5073893fe43413e96b2902bdcd2eb2d4abcc3f.png)
Next note that the LHS can be rewritten as
.
Also note that the RHS can be rewritten as
. Hence our inequality becomes
![\[\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}-\dfrac{1}{k+1}\geq \dfrac{2(k+1)}{3(k+1)+1}-\dfrac{2k}{3k+1}.\]](//latex.artofproblemsolving.com/2/c/2/2c2f56923efe04a466c9d10dfa67158f4636d5bd.png)
Adding this to our induction step gives us
![\[\left(\dfrac{1}{k+1}+\dfrac{1}{k+2}+\cdots+\dfrac{1}{2k}\right)+\left(\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}-\dfrac{1}{k+1}\right)\geq \dfrac{2k}{3k+1}+\left(\dfrac{2k+2}{3k+4}-\dfrac{2k}{3k+1}\right),\]](//latex.artofproblemsolving.com/f/1/1/f1187bebc4e308df98cdd0b05bef8ee979960bfd.png)
and simplifying this gives us
![\[\dfrac{1}{k+2}+\dfrac{1}{k+3}+\cdots+\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}\geq \dfrac{2(k+1)}{3(k+1)+1}.\]](//latex.artofproblemsolving.com/a/3/7/a370d27526dbb027f1a48b2e384b534d1b3dc106.png)
We assumed the hypothesis was true for
, and we have proven it true for
. Our induction is complete.
by djmathman, Jul 22, 2012, 12:10 AM 
including the empty set, are spacy?
including the empty set, are spacy?
.
set in this case.
sets in this case.
in a spacy set, where 
,
for 
This is because if we pick the number 
to be in the set, we can not have any of the numbers 
in the set as well. How do we count the number of sets with such a restriction? The answer is to simply remove it.
as shown:![\[\text{XXXXXXXXXX}\]](http://latex.artofproblemsolving.com/4/f/f/4ff219a2e86c9f44a778fd4598bf222cb4ae78d8.png)
![\[\text{XXXXX}\boxed{\text{X}}\boxed{\text{X}}\text{XXX}\implies \text{XXXXX}\boxed{\text{X}}\color{red}\text{XX}\color{black}\boxed{\text{X}}\text{XXX}\]](http://latex.artofproblemsolving.com/1/a/3/1a3d45ec2e9dc49fbfdf5e9acd18ce8952f11c2f.png)
elements, which is what we want! Therefore, the 1-1 correspondence is established, and the number of sets in Case 2 is simply 
.
instead of ![\[\text{XX}\boxed{\text{X}}\text{X}\boxed{\text{X}}\boxed{\text{X}}\text{XX}\implies \text{XX}\boxed{\text{X}}\color{red}\text{XX}\color{black}\text{X}\boxed{\text{X}}\color{red}\text{XX}\color{black}\boxed{\text{X}}\text{XX}\]](http://latex.artofproblemsolving.com/b/c/d/bcd1f806c872b2a24632f4f1c6577e497f38b0da.png)
,
.
.
.
be a positive integer. Prove that 
.
be a positive integer. Prove that 
.
,
for some 
,
.
to both sides gives us 
,
.![\[\dfrac{1}{(2k+1)(2k+2)}\geq \dfrac{2}{(3k+1)(3k+4)}.\]](http://latex.artofproblemsolving.com/3/d/5/3d5073893fe43413e96b2902bdcd2eb2d4abcc3f.png)
.
.![\[\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}-\dfrac{1}{k+1}\geq \dfrac{2(k+1)}{3(k+1)+1}-\dfrac{2k}{3k+1}.\]](http://latex.artofproblemsolving.com/2/c/2/2c2f56923efe04a466c9d10dfa67158f4636d5bd.png)
![\[\left(\dfrac{1}{k+1}+\dfrac{1}{k+2}+\cdots+\dfrac{1}{2k}\right)+\left(\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}-\dfrac{1}{k+1}\right)\geq \dfrac{2k}{3k+1}+\left(\dfrac{2k+2}{3k+4}-\dfrac{2k}{3k+1}\right),\]](http://latex.artofproblemsolving.com/f/1/1/f1187bebc4e308df98cdd0b05bef8ee979960bfd.png)
![\[\dfrac{1}{k+2}+\dfrac{1}{k+3}+\cdots+\dfrac{1}{2k+1}+\dfrac{1}{2(k+1)}\geq \dfrac{2(k+1)}{3(k+1)+1}.\]](http://latex.artofproblemsolving.com/a/3/7/a370d27526dbb027f1a48b2e384b534d1b3dc106.png)
,
.
April 2025
November 2024