Results 1 to 5 of 5

Thread: help!

  1. #1
    Newbie
    Joined
    Jun 2006
    Posts
    13

    Exclamation help!

    Q1-Total number of squares of any size(side being natural nos.) in a rectangle of $\displaystyle \[m\times n(m<n),(m,n\in N)\]$
    Q2-In how many ways can 15 boys and 3 girls can sit in a row such that between the girls at most two boys sit?
    all the persons are distinguishable and their order must be considred.
    Last edited by Navesh; Jun 23rd 2006 at 10:00 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    Hello, Navesh!

    These problems raise even more questions . . .

    Q1) Total number of squares of any size (side being natural nos.)
    . . . in an $\displaystyle m \times n$ rectangle . . . $\displaystyle m < n,\;m,n \in N$
    Are we allowed to use the Greatest Integer Function?
    . . $\displaystyle [x]$ = the greatest integer less than or equal to $\displaystyle x.$
    Basically, it is a "round down" function.


    Then we count the number of squares of various sizes . . .

    $\displaystyle 1\times1:\;\;m\cdot n$

    $\displaystyle 2\times2:\;\;\left[\frac{m}{2}\right]\cdot\left[\frac{n}{2}\right]$

    $\displaystyle 3\times3:\;\;\left[\frac{m}{3}\right]\cdot\left[\frac{n}{3}\right]$

    $\displaystyle 4\times4:\;\;\left[\frac{m}{4}\right]\cdot\left[\frac{n}{4}\right]$

    . . $\displaystyle \vdots$ . . . . . . . $\displaystyle \vdots$

    $\displaystyle m\times m:\;\;1\cdot\left[\frac{n}{m}\right]$

    Then add these numbers.


    Q2) In how many ways can 15 boys and 3 girls can sit in a row
    . . . such that between the girls at most two sit?
    (a) If the 18 children are distinguishable (they have different names),
    . . then their order must be considered.

    (b)If the 15 boys and 3 girls are indistinguishable (arrange 15 blue marbles
    . . and 3 red marbles in a row), the problem is still quite difficult.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2006
    Posts
    13
    Quote Originally Posted by Navesh
    Q1-Total number of squares of any size(side being natural nos.) in a rectangle of $\displaystyle \[m\times n(m<n),(m,n\in N)\]$
    Q2-In how many ways can 15 boys and 3 girls can sit in a row such that between the girls at most two boys sit?
    all the persons are distinguishable and their order must be considred.
    The answer given in my textbook is $\displaystyle \[\sum (m-r)(n-r), r=0,1,2,\ldots ,m-1\] $.Why is it so? I think you are missing some of the squares.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    Hello, Navesh!

    The answer given in my textbook is: $\displaystyle \[\sum^{m-1}_{r=0} (m-r)(n-r)$.

    Of course, it is! . . . I looked at it from the worst direction . . . *blush*
    I've solved this type of problem before, but totally forgot the approach.

    We have an $\displaystyle m \times n $ "chessboard" with $\displaystyle m$ rows and $\displaystyle n$ columns.

    How many $\displaystyle 1\!\times\!1$ squares are there? .Let's call them $\displaystyle \text{one-squares}.$
    . . Place a $\displaystyle \text{one-square}$ in the upper-left corner.
    . . There are $\displaystyle m$of them in the first row, and there are $\displaystyle n$ such rows.
    Hence, there are: $\displaystyle (m)(n)\text{ one-squares.}$

    How many $\displaystyle \text{two-squares}$ are there?
    . . Place a $\displaystyle \text{two-square}$ in the upper-left corner.
    . . There are $\displaystyle n-1$ of them in the first row, and there are $\displaystyle m-1$ such rows.
    Hence, there are: $\displaystyle (m-1)(n-1)\text{ two-squares.}$

    How many $\displaystyle \text{three-squares}$ are there?
    . . Place a $\displaystyle \text{three-square}$ in the upper-left corner.
    . . There are $\displaystyle n-2$ of them in the first row, and there are $\displaystyle m-2$ such rows.
    Hence, there: $\displaystyle (m-2)(n-2)\text{ three-squares.}$
    . . . $\displaystyle \vdots$
    How many $\displaystyle \text{m-squares}$ are there?
    . . Place an $\displaystyle \text{m-square}$ in the upper-left corner.
    . . There are $\displaystyle n-m+1$ of them in the first row, and there is $\displaystyle 1$ such row.
    Hence, there are: $\displaystyle 1(n-m+1)\;\text{m-squares.}$


    Therefore, the total number of squares is:
    . . $\displaystyle m\cdot n + (m-1)(n-1) + (m-2)(m-2) +$$\displaystyle \hdots + 1(n-m+1)$

    which can be written: .$\displaystyle \sum^{m-1}_{r=0}(m - r)(n - r)$
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2006
    Posts
    13
    Quote Originally Posted by Soroban
    Hello, Navesh!


    Of course, it is! . . . I looked at it from the worst direction . . . *blush*
    I've solved this type of problem before, but totally forgot the approach.

    We have an $\displaystyle m \times n $ "chessboard" with $\displaystyle m$ rows and $\displaystyle n$ columns.

    How many $\displaystyle 1\!\times\!1$ squares are there? .Let's call them $\displaystyle \text{one-squares}.$
    . . Place a $\displaystyle \text{one-square}$ in the upper-left corner.
    . . There are $\displaystyle m$of them in the first row, and there are $\displaystyle n$ such rows.
    Hence, there are: $\displaystyle (m)(n)\text{ one-squares.}$

    How many $\displaystyle \text{two-squares}$ are there?
    . . Place a $\displaystyle \text{two-square}$ in the upper-left corner.
    . . There are $\displaystyle n-1$ of them in the first row, and there are $\displaystyle m-1$ such rows.
    Hence, there are: $\displaystyle (m-1)(n-1)\text{ two-squares.}$

    How many $\displaystyle \text{three-squares}$ are there?
    . . Place a $\displaystyle \text{three-square}$ in the upper-left corner.
    . . There are $\displaystyle n-2$ of them in the first row, and there are $\displaystyle m-2$ such rows.
    Hence, there: $\displaystyle (m-2)(n-2)\text{ three-squares.}$
    . . . $\displaystyle \vdots$
    How many $\displaystyle \text{m-squares}$ are there?
    . . Place an $\displaystyle \text{m-square}$ in the upper-left corner.
    . . There are $\displaystyle n-m+1$ of them in the first row, and there is $\displaystyle 1$ such row.
    Hence, there are: $\displaystyle 1(n-m+1)\;\text{m-squares.}$


    Therefore, the total number of squares is:
    . . $\displaystyle m\cdot n + (m-1)(n-1) + (m-2)(m-2) +$$\displaystyle \hdots + 1(n-m+1)$

    which can be written: .$\displaystyle \sum^{m-1}_{r=0}(m - r)(n - r)$
    Thanks for help
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum