Choose 'k' numbers from 'n' with no two consecutive.


Proof 1: Using stars and bars
There are 'n' positions(1,2....n) laid down in a line from which we have to pick 'k' positions such that no 2 are adjacent.
Let's say the picked positions are X and unpicked are O.
First we put 'k' Xs followed by 'n-k' Os. (So total positions are 'n').
Now the picked positions can't be adjacent so we put 'k-1' Os between them.
Now we are left with how many Os? n-k-(k-1) = n-2k + 1
These remaining Os can be freely distributed among the 'k+1' buckets.
Why 'k+1' buckets?
Because 'k' Xs have 1 gap on either side and 'k-1' gaps between them. So total k-1+2 = k+1 gaps(buckets).
So we have 'n-2k+1' identical objects(remaining Os) to be put in 'k+1' distinct buckets.
Stars and bars formula for the same for 'n' identical objects and 'k' distinct buckets:
(n+k-1)C(k-1)
Putting the new values here:
( (n-2k+1) + (k+1) - 1)C((k+1) - 1)
=
(n-k+1)C(k) 

So these are the ways of arranging Xs and Os.
Let's take one of those arrangements and pick indices of positions of X.
That is one of the valid picks.

So (n-k+1)C(k) is the number of ways to pick those numbers.


Proof 2:(Compression trick)
 

Picture the numbers as spots on a line

Write the numbers 1, 2, 3 … n in a row.
Your job is to place k check-marks on some of those spots, but no two check-marks are allowed to sit next to each other (that’s the “no consecutive numbers” rule).

The trick: squeeze the gaps away

  1. Label the chosen numbers
    Call them

    a1<a2<⋯<ak. a_1 < a_2 < \dots < a_k .

    Because you never picked two in a row, each gap between aia_i and ai+1a_{i+1} is at least 1.

  2. Shift each choice left by its position in the list
    Define

    b1=a1,b2=a2−1,b3=a3−2,  …  ,bk=ak−(k−1). b_1 = a_1,\quad b_2 = a_2 - 1,\quad b_3 = a_3 - 2,\; \dots\; ,\quad b_k = a_k - (k-1).

    In words: for the 2nd chosen number slide it left one step, for the 3rd slide it left two steps, and so on.

  3. What just happened?

    • Because each gap was at least one, sliding never makes two numbers collide.

    • After sliding, the bib_i’s are still in increasing order but can now sit next to each other—we erased the “no-consecutive” rule!

    • The smallest b1b_1 is still at least 1.

    • The largest bkb_k can’t go past n−k+1n-k+1 (we slid aka_k left by k−1k-1).

    So the list

    b1<b2<⋯<bk b_1 < b_2 < \dots < b_k

    is simply any set of k distinct numbers chosen from

    {1,2,3,…,n−k+1}. \{1,2,3,\dots,n-k+1\}.

  4. Reverse the shift = perfect one-to-one match
    Starting with any kk numbers inside {1,…,n−k+1}\{1,\dots,n-k+1\} and sliding them right (add 0,1,2,…,k−10,1,2,\dots,k-1) recreates a legal gap-filled set in {1,…,n}\{1,\dots,n\}.
    Therefore the two tasks are in bijection (perfect pairing).

Count the easy task

Choosing kk numbers from a list of n−k+1n-k+1 without any restrictions is the ordinary binomial coefficient

( n−k+1 k). \binom{\,n-k+1\,}{k}.

Because of the perfect match above, that is also the number of gap-separated (no-consecutive) choices you wanted.


Quick example

Take n=8,  k=3n=8,\;k=3.

legal picks (no two consecutive) slide left (subtract 0,1,2) lands in {1,…,6}\{1,\dots,6\}
{1,3,6}\{1,3,6\} {1,2,4}\{1,2,4\} ✓
{2,5,8}\{2,5,8\} {2,4,6}\{2,4,6\} ✓
{3,5,7}\{3,5,7\} {3,4,5}\{3,4,5\} ✓

All (63)=20\binom{6}{3}=20 “easy” triples in {1,…,6}\{1,…,6\} correspond to 20 legal triples in {1,…,8}\{1,…,8\}.

Comments

Post a Comment

Popular posts from this blog

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more

Simon's factoring trick(complete the rectangle)

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more