A subset S of {1,2,…,n} is said to be packed if whenever i,j∈S the number ⌊(i+j)/2⌋ is also in S. Determine how many subsets of {1,2,…,25} are packed.
Details and assumptions
i and j need not be distinct. If i=j is in the set, then clearly so is ⌊(i+j)2⌋
questions from "brilliant.org" will not be answered.
http://www.jiskha.com/display.cgi?id=1373375428
i am Clavin
oh, well, then -- that explains it.
If you were Calvin, you wouldn't need to have help, you(probably)made this question. Plus, "Clavin" is misspelled.
To determine the number of packed subsets of {1, 2, ..., 25}, we can use a dynamic programming approach.
Let's define a function P(n) that represents the number of packed subsets of {1, 2, ..., n}. We want to find P(25).
To calculate P(n), we can break it down into two cases:
1. n is not included in the subset.
2. n is included in the subset.
Case 1: n is not included in the subset.
In this case, the subset is a packed subset of {1, 2, ..., n-1}. Therefore, the number of packed subsets in this case is P(n-1).
Case 2: n is included in the subset.
In this case, we need to find all the numbers that can be paired with n to satisfy the packed property. Since (i+j)/2 must be an integer, either both i and j are even, or both i and j are odd.
Let's consider the two possibilities:
a) n is even: In this case, there are (n-1)/2 even numbers in {1, 2, ..., n-1}. To form a pair with n, we need to select one even number from {1, 2, ..., n-1} (excluding n) and pair it with n. After selecting this even number, we can form a packed subset of {1, 2, ..., n-1} with the remaining even numbers. Therefore, the number of packed subsets in this case is (n-1)/2 * P(n-1).
b) n is odd: In this case, there are (n-1)/2 odd numbers in {1, 2, ..., n-1}. To form a pair with n, we need to select one odd number from {1, 2, ..., n-1} (excluding n) and pair it with n. After selecting this odd number, we can form a packed subset of {1, 2, ..., n-1} with the remaining odd numbers. Therefore, the number of packed subsets in this case is (n-1)/2 * P(n-1).
Now, we can write the recurrence relation for P(n):
P(n) = P(n-1) + (n-1)/2 * P(n-1)
Let's use this recurrence relation to calculate P(25) using dynamic programming:
Initialize P(0) = 1.
For i from 1 to 25:
P(i) = P(i-1) + (i-1)/2 * P(i-1)
The final answer will be P(25).