18
$\begingroup$

My attempt. Let us assume $n$ is a large positive integer. ${n \choose 0},{n \choose 1},{n \choose 2}$ are the numbers of such subsets having $0,1,2$ elements respectively, which is trivial. For $3$ elements, the number of such subsets is ${n \choose 3}-(n-2)$. Starting from $4$ elements, my brain begins muddling up; I have no idea how to proceed further systematically. Any hint or idea would be appreciated.


Remark. Thanks to the partial solutions by VIVID and Masacroso, I have completely solved this problem. Following VIVID's answer, I have posted an answer which completes the solution primarily for future reference.
I am going to give the accepted answer to VIVID who has been very dedicated to this problem seen from his number of edits. Also, most importantly, VIVID was the first person who posted the core part of the solution. Masacroso, hope you would not mind.

Last, though this problem has been completely resolved, any new approach is always welcome.

$\endgroup$
8
  • $\begingroup$ I'm not sure I could fully answer the question, but here's a hint I notice right away: In which cases must the subset contain three consecutive integers? For instance, a subset of $n$ integers must contain three consecutive integers for $n\geq3$ because it contains all integers up to $n$, but if you can find a general rule based on $n$, you've eliminated cases you need to check. $\endgroup$ Aug 24, 2020 at 7:47
  • 1
    $\begingroup$ These will be Tribonacci numbers: one closed form involves the three roots (two complex) of a cubic equation $\endgroup$
    – Henry
    Aug 24, 2020 at 7:57
  • $\begingroup$ Hi Henry. Your statement is very intriguing. I understand the 'Tribonacci' part, but what cubic equation are you talking about? Please clarify a bit more. Thanks a lot. @Henry $\endgroup$ Aug 24, 2020 at 13:35
  • 1
    $\begingroup$ @IncredibleSimon The roots of $x^3-x^2-x-1=0$ apply here, rather like the roots of $x^2-x-1=0$ being part of the closed form solution for the Fibonacci sequence $\endgroup$
    – Henry
    Aug 24, 2020 at 13:57
  • 1
    $\begingroup$ @IncredibleSimon You can express it as a weighted sum of the powers of the three roots so in the form $a x_1^n+bx_2^n +cx_3^n$ $\endgroup$
    – Henry
    Aug 25, 2020 at 7:49

4 Answers 4

13
$\begingroup$

Partial solution: Let's denote by $S \subseteq \{1,2,\dots,n\}$ all sets that satisfy the condition. And let $a_n$ be the number of such sets.

There may be some cases:

  1. $n \not \in S \implies$ there are $a_{n-1}$ possibilities for $S$ (clear)
  2. $n \in S$:
  • a) $n-1 \not \in S \implies$ there are $a_{n-2}$ possibilities for $S$ (why?)
  • b) $n-1 \in S, \ \ n-2 \not \in S \implies$ there are $a_{n-3}$ possibilities for $S$. (why?)

Hence, we get the recurrence formula $$\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$$


Answer two (why?) parts above and it will become a full solution.

$\endgroup$
2
  • $\begingroup$ Hi, VIVID. Sorry for commenting late. I have been trying to understand your solution for quite a few hours; I am a slow thinker... Thanks a lot indeed for your help and dedication. By the way, if you do not mind, please help me review my self-posted answer to check if my understanding is alright. Thank you again! @VIVID $\endgroup$ Aug 24, 2020 at 13:30
  • $\begingroup$ @IncredibleSimon, No worries about the later comment. I have reviewed your completion and it seems you understand it well enough! (+1) $\endgroup$
    – VIVID
    Aug 24, 2020 at 15:42
5
$\begingroup$

Sketch for the solution: you can construct a recursion to find this number. Let $x_k$ the number of subsets in $\{1,\ldots ,k\}$ that doesn't contain three consecutive numbers, then $x_{k+1}=x_k+x_{k-1}+x_{k-2}$ because

  • $x_k$ is the number of subsets in $\{1,\ldots ,k+1\}$ that doesn't contain $k+1$ and dont have three consecutive numbers
  • $x_{k-1}$ is the number of subsets in $\{1,\ldots ,k+1\}$ that contains $k+1$ but doesn't contain $k$ and doesn't contain three consecutive numbers
  • $x_{k-2}$ stay for the subsets in $\{1,\ldots ,k+1\}$ that contains $k+1$ and $k$ but doesn't contains three consecutive numbers.
$\endgroup$
3
  • $\begingroup$ Hi Masacroso. Though your solution duplicates VIVID's, it helps as well. Thank you very much sincerely. If you do not mind, please review my self-posted solution to check if my understanding is alright. Thank you again! @Masacroso $\endgroup$ Aug 24, 2020 at 13:44
  • $\begingroup$ @IncredibleSimon thank you. The thing is that I was writing my answer when the answer of VIVID comes out, and see it just after I published my answer. Incidentally both have the same approach (and I dont know how to approach this question from other point of view). $\endgroup$
    – Masacroso
    Aug 24, 2020 at 14:00
  • $\begingroup$ Got it, buddy. I have never doubted that it was not your own idea. Good job and respect! @Masacroso $\endgroup$ Aug 24, 2020 at 14:55
3
$\begingroup$

Here's perhaps another approach. (Well it's basically equivalent to the answers already given, but maybe the binary string representation makes the problem easier to think about. At least it does for me, but that might be because I happened to already be familiar with these "run length problems".)

You can think a subset $S$ of $\{1,\dots, n\}$ as a binary string of length $n$, where $1$ at position $j$ means $j\in S$ and $0$ means $j\notin S$. Now, the subsets we want to count correspond to binary strings without a $3$-run of $1$'s.

To solve this new problem, lets denote

$$A_n = \{\text{length } n \text{ binary strings without a run of three 1's} \}$$

Now think of a $w\in A_n$ and the number of $1$'s it has in the beginning. That can be either $0$, $1$ or $2$. Then there is a zero and the rest is a word in $A_{n-1}$, $A_{n-2}$ or $A_{n-3}$, respectively. We're assuming $n>3$; the first ones are base cases. You can see the tribonacci-recursion for the size $|A_n|$.

$\endgroup$
1
  • $\begingroup$ Hi, ploosu2. Though it results in the same recursion formula, I think it is definitely another perspective to tackle the problem. Thank you very much! @ploosu2 $\endgroup$ Aug 25, 2020 at 3:14
2
$\begingroup$

First of all, a lot of thanks to VIVID and Masacroso for their partial solutions by a recursive approach which is indeed wonderful. Below, I just want to finish what they left off (which is good so that I can think) for future reference and for reinforcing my own understanding.

Let me follow VIVID's notations.
Let $s$ denote a general element of $S$.

  • For those $s$ which do not contain $n$, there are $a_{n-1}$ such $s$, which is trivial.
  • For those $s$ which contain $n$ but do not contain $n-1$, there are $a_{n-2}$ such $s$. Because by 'isolating' $n$ we need only consider the selection of the rest $n-2$ integers.
  • For those $s$ which contain both $n$ and $n-1$, we must not include $n-2$ in such $s$, and then by 'isolating' $n$ and $n-1$ we need only consider the selection of the rest $n-3$ integers. Thus there are $a_{n-3}$ such $s$.

Then, we recognize that those three sets of different $s$ are disjoint, and indeed their union is $S$. Hence the recursive relation $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. Then we can form a sequence similar to the Fibonacci numbers but this time adding the preceding three numbers to get the next, i.e. $1,2,4,7,13,24,44,81,...$, where the first number indicates $a_0$ which corresponds to the empty set.

Remark. I realize that using this recursive ideology, we can further derive sequences of $a_n$ with the condition replaced by not having $r$ consecutive integers where $r$ can be any positive integer.

$\endgroup$
2
  • 1
    $\begingroup$ the reasoning is not complete or enough clear. The point is that $S$ can be partitioned in three subsets, and each one have cardinalities $a_{n-1},a_{n-2},a_{n-3}$. To see this note that if $s\in S$ then there are two possibilities: $n\in s$ or $n\notin s$, in the latter $s$ can be seen as a subset of $\{1,\ldots ,n-1\}$, and in the former we can divide further in other two cases: $n-1\in s$ or $n-1\notin s$, but the important point is that just one and only one of these three conditions hold for some chosen $s\in S$. $\endgroup$
    – Masacroso
    Aug 24, 2020 at 14:08
  • $\begingroup$ Masacroso, your reasoning is indeed far more elegant and clearer than mine. I have the same idea in mind, but in terms of putting it into words you absolutely nailed it. Thank you so much. @Masacroso $\endgroup$ Aug 24, 2020 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .