0
$\begingroup$

Suppose $S=\{1,2,\dots,7\}$, already we know that, $S$ have $2^7$ subsets. But the problem is, when we multiply elements of each subset $S$, how many different value we can obtain from multiplication of elements of each subsets? In $2^7$ subsets, some of them are equal, for example, for subset of size 2, $3\times 4=6\times 2$. Are there a simple way that eliminate the duplicate values for any subsets?

$\endgroup$
4
  • 2
    $\begingroup$ It's usually nice to add some context (from where is this problem) and some thoughts or early attempts you've done. As a hint, I'd start with writing the possible factorizations in primes of numbers you can obtain from the set $S$. $\endgroup$
    – AnilCh
    Jul 29 '21 at 9:39
  • 2
    $\begingroup$ Every number you get is a divisor of $7!=5040$. But you can't get every divisor of $5040$, e.g., you can't get $9$. That should get you started. $\endgroup$ Jul 29 '21 at 11:08
  • $\begingroup$ That is already a huge hint. The hint in more words again is that the odd multiples of $9$ who are divisors of $7!$ are not possible. Can you think of any others who are not possible? Can you prove that? Note that the only prime factors possible in the results are $2,3,5,7$ which limits the search considerably. $\endgroup$
    – JMoravitz
    Jul 29 '21 at 12:49
  • $\begingroup$ Now... $7! = 2^4\cdot 3^2\cdot 5\cdot 7$... The number of factors of a number is well known to be the product of one more than each of the exponents in the prime factorization... in this case $(4+1)\cdot (2+1)\cdot (1+1)\cdot (1+1)=5\cdot 3\cdot 2\cdot 2 = 60$, and the number of these which are not possible you can count simply as well and remove from the count. $\endgroup$
    – JMoravitz
    Jul 29 '21 at 12:54
2
$\begingroup$

$7!=2^4\cdot 3^2\cdot 5^1\cdot 7^1$ has $(4+1)(2+1)(1+1)(1+1)=60$ divisors

Of these, the divisors who are multiples of $2^4$ but not multiples of $3$ are not possible to make (as $6$ would have been needed for that last factor of $2$ and would have brought a factor of $3$ along with it) as well as the divisors who are multiples of $9$ but not multiples of $2$ are not possible (for a similar reason).

There are $2\cdot 2 = 4$ factors who are multiples of $2^4$ but not multiples of $3$ (seen by looking at factors of the form $2^4\cdot 3^0\cdot 5^z\cdot 7^w$) and similarly there are $2\cdot 2 = 4$ factors who are multiples of $9$ but not multiples of $2$ (looking at $2^0\cdot 3^2\cdot 5^z\cdot 7^w$).

As such the total will be

$$60 - 4-4 = 52$$

$\endgroup$
1
$\begingroup$

Since $1$ has no effect in the multiplications you can put it aside. Put the number $6$ aside for now. Factorize all the other numbers. The multiplication of the elements of any nonempty subset of $\lbrace 2, 3, 4, 5, 7 \rbrace$ would be of the form $$2^{x} \times 3^{y} \times 5^{z} \times 7^{w} $$ where $x$ and $y$ and $z$ and $w$ are whole numbers and $0 \leq x \leq 3$ and $0 \leq y \leq 1$ and $0 \leq z \leq 1$ and $0 \leq w \leq 1$. As a result of the multiplication principle, you can say that there are $4 \times 2 \times 2 \times 2 = 32$ such multiplications. Now what if we play the number $6$ into the game? Then any multiplication would be of the form $$2^{x + 1} \times 3^{y + 1} \times 5^{z} \times 7^{w} $$ where $x$ and $y$ and $z$ and $w$ are whole numbers and $0 \leq x \leq 3$ and $0 \leq y \leq 1$ and $0 \leq z \leq 1$ and $0 \leq w \leq 1$. However, if $0 \leq x \leq 2$ and $y = 0$ no new state will be generated and vice versa so you should suppose either $x = 3$ or $y = 1$. You can deduce from the inclusion-exclusion principle that the number of the new states will be $2 \times 2 \times 2 + 4 \times 2 \times 2 \; - 2 \times 2 = 20$. So overall the answer would be $32 + 20= 52$.

$\endgroup$
4
  • 1
    $\begingroup$ You overcounted the divisor $1$. It appeared in not only your first case (where you considered only the divisor $1$) but also in your second case where you considered divisors of the form $2^x3^y5^z7^w$ in the case of $x=y=z=w=0$. Note, the empty-product is equal to $1$. $\endgroup$
    – JMoravitz
    Jul 30 '21 at 12:07
  • $\begingroup$ Yes. I made a mistake. You're right. I'll edit it. Good point. $\endgroup$
    – Emad
    Jul 30 '21 at 18:03
  • $\begingroup$ @Emad, I wish you had let OP work it out from the comments, instead of spoiling the fun by writing it all out yourself. $\endgroup$ Jul 31 '21 at 7:45
  • 1
    $\begingroup$ @GerryMyerson That's right. I should pay more attention to these things. $\endgroup$
    – Emad
    Jul 31 '21 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.