0
$\begingroup$

I am reading a book where the following reduction is performed, but it's not explained exactly what is going on. I'm sorry if this is a dumb question, but I simply don't get how we are deriving the second line from the first line. Can anyone help me?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ what is S? you need to state the whole problem $\endgroup$ – user190080 Jun 24 '15 at 22:56
  • 1
    $\begingroup$ Are you sure about that statement (it seems false) ? Where is it from ? Maybe give a bit more context. $\endgroup$ – Joel Cohen Jun 24 '15 at 22:56
  • $\begingroup$ It's from Artificial Intelligence, a Modern Approach, 3rd ed. q. 3.5. The S is the state space. I will post a screencap. $\endgroup$ – picardo Jun 24 '15 at 22:58
  • $\begingroup$ This follows by grouping like terms. Then use $(n-k) \le (n-k-l)$ (for appropriate $k,l$, of course). $\endgroup$ – copper.hat Jun 24 '15 at 22:59
  • $\begingroup$ now wait...this is completely not what you wanted in the first place, $S^3\ge n!$ and not $S^3=n!$ $\endgroup$ – user190080 Jun 24 '15 at 23:00
4
$\begingroup$

ok the reasoning goes as follows, whatever $S^3$ is, we know that $$ S^3\ge n*n*n*(n-3)*(n-3)*(n-3)\dots $$ but we also know that $n>(n-1),n>(n-2)$ and $(n-3)>(n-4),(n-3)>(n-5)$ and therefore we just plug in and get the following inequality $$ S^3\ge n*n*n*(n-3)*(n-3)*(n-3)\dots \ge n*(n-1)(n-2)*(n-3)(n-4)(n-5)\dots=n! $$ and thats it.

bests

$\endgroup$
  • $\begingroup$ Ah, of course. I need to work on my inequalities... thank you. $\endgroup$ – picardo Jun 24 '15 at 23:19
1
$\begingroup$

In the first line we have nnn which has been replace by n*(n-1)(n-2) This is valid because we are saying that that S^3 is greater or equal to the first line and since nnn > n(n-1)*(n-2) for all n, it is a valid substitution.

The next 3 terms are (n-3)(n-3)(n-3) which is then replaced by (n-3)(n-4)(n-5). This is valid because (n-3)(n-3)(n-3)>(n-3)(n-4)(n-5) for all n.

The factors continue repeating 3 numbers and being replaced by 3 consecutive decreasing numbers. The new group of numbers is always less than the 3 numbers it replaced so the new group of numbers is always a valid substitution.

The advantage of these substitutions is that you can combine the numbers to equal n!

$\endgroup$
0
$\begingroup$

It is true that $$ S \ge \prod_{k=0}^K (n - 3 k) $$ and so \begin{align} S^3 & \ge \prod_{k=0}^K (n - 3 k) \cdot (n - 3 k) \cdot (n - 3k) \\ & \ge \prod_{k=0}^K (n - 3 k) \cdot (n - 3 k - 1) \cdot (n - 3k -2) = n! \end{align} if $n - 3K - 2 = 1$ or $K=n/3-1$.

$\endgroup$
  • $\begingroup$ ah, ok, that looks nicer, although it is $S^3\ge\dots$ $\endgroup$ – user190080 Jun 24 '15 at 23:14
  • $\begingroup$ don't want to be a nitpicker, but the first $=$ needs to be a $\ge$ $\endgroup$ – user190080 Jun 24 '15 at 23:17
  • $\begingroup$ Details, details, .. :-) $\endgroup$ – mvw Jun 24 '15 at 23:20

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.