2
$\begingroup$

Adriana will be examinated in $5$ subjects, one at each day.She has $5$ dresses in different colors: red-blue-green-white-yellow.

On Monday she does not want to wear the blue or green one.

On Tuesday, she does not wear the red or green one.

On Wednesday,she does not wear the blue, white or yellow one.

On Friday ,she does not wear the white one.

With how many different ways can Adriana be dressed,if she does not want to wear the same dress more than once?

Can you tell me how I could solve the above exercise?

EDIT: I tried to solve it using a diagram.

enter image description here

So,there are $18$ ways that she can be dressed..Could you tell me if it is right?

$\endgroup$
3
  • 1
    $\begingroup$ Spam comment: I was tutoring someone in a problem similar to this, except it said "Professor <name> has $4$ unique shirts, $8$ unique pants, and $2$ unique pairs of shoes. In how many ways can Professor <different name> be dressed?" :) $\endgroup$
    – apnorton
    Jun 2 '14 at 16:04
  • $\begingroup$ Could you tell me if the diagram I did and the solution I found is correct? $\endgroup$
    – evinda
    Jun 2 '14 at 16:07
  • $\begingroup$ I believe your diagram is correct. $\endgroup$
    – apnorton
    Jun 2 '14 at 16:10
2
$\begingroup$

In this case, a simple exhaustive tree-based counting, as in your question or in 5xsum's answer, seems the more direct way.

For a general approach:

Write a 5x5 matrix, with weekdays in columns and colors in rows. Place a 1 where an assignment is allowed, a 0 otherwise.

    Mo Tu We Th Fr
 R  1  0  1  1  1 
 G  0  0  1  1  1 
 Y  1  1  0  1  1 
 W  1  1  0  1  0 
 B  0  1  0  1  1 

Then the problem is equivalent to counting the number of placements of 5 non-attacking rooks over the restricted checkboard (zeroes forbidden). This can be attacked via rook polynomials, or via the permanent (sort of a determinant without the signs) of the matrix (this is not very easy to compute, though).

In Octave, with code from here:

 function y=permanent(A)

 [m,n]=size(A);
    if n==1
        y=A;
    else
        for k=2:n
     P=ones(1,k);
     for i=1:k
         SubA=A([1:k-1],[1:i-1 i+1:k]);
         P(i)=permanent(SubA);
     end
     y=A(k,1:k)*P';
        end
    end
 endfunction

> M = [1 0 1 1 1 ; 0 0 1 1 1 ; 1 1 0 1 1 ; 1 1 0 1 0 ; 0 1 0 1 1]
M =

   1   0   1   1   1
   0   0   1   1   1
   1   1   0   1   1
   1   1   0   1   0
   0   1   0   1   1
> permanent(M)
ans =  18
$\endgroup$
5
  • $\begingroup$ Nice...Is the diagram that I created also right??? $\endgroup$
    – evinda
    Jun 2 '14 at 16:07
  • 1
    $\begingroup$ It seems so. That we got the same result is enough proof for me :-) However, I believe that starting with the more restricted day (W) towards the less restricted days, as in the other answer, is slightly easier. $\endgroup$
    – leonbloy
    Jun 2 '14 at 16:08
  • $\begingroup$ Great!!!Thanks a lot!!! $\endgroup$
    – evinda
    Jun 2 '14 at 16:09
  • $\begingroup$ @leonbloy, I do not know Octave but M = [1 0 1 1 1 ; 0 0 1 1 1 ; 1 1 0 1 1 ; 1 1 0 1 0 ; 1 1 0 1 0 ; 0 1 0 1 1] looks like a 6 x 5 matrix. Is that what you intended? $\endgroup$
    – bobbym
    Nov 10 '16 at 17:10
  • $\begingroup$ @bobbym Fixed, thanks $\endgroup$
    – leonbloy
    Nov 10 '16 at 18:05
1
$\begingroup$

I would first focus on wednesday, since the can only wear the red and green dresses, giving her $2$ choices. Whichever dress she picks, she then still has $3$ options for tuesday, but then it gets complicated. I will only solve one of the six possibilities here, namely picking red on wednesday and blue on tuesday.

  • She can then pick white on monday and green or yellow on friday (and the other on thursday), giving $2$ options.
  • She can pick yellow on monday, leaving only green for friday and white for thursday, so there is only one option here.

This means that the possibility of red on wednesday and blue on tuesday only leaves $3$ clothing options for the rest of the week. Now, repeat the process for the other $5$ options.

A more mathematical approach would probably consider the principle of exclusion and inclusion. Let $A_n$ denote the set of all dress combinations that satisfies the demands for day $n$. For example, $|A_1| = 3\cdot 4\cdot 3\cdot 2\cdot 1$. Now, calculate $$\left|\left(\bigcap_{i=1}^n A_i\right)^c\right| = \left|\bigcup_{i=1}^nA_i^c\right|$$ using the principle of exclusion and inclusion. It takes a while, but it will get you there.

$\endgroup$
5
  • $\begingroup$ Is numerating the possibilities the only way to solve the exercise?? Maybe with graphs or something else?? $\endgroup$
    – evinda
    Jun 2 '14 at 12:29
  • $\begingroup$ @evinda I edited my question with the principle of exclusion and inclusion which may prove a more mathematical way of solving the problem, but I don't really think it's any quicker. $\endgroup$
    – 5xum
    Jun 2 '14 at 12:38
  • $\begingroup$ So isn't it possible,to solve the exercise,using graphs? $\endgroup$
    – evinda
    Jun 2 '14 at 12:43
  • $\begingroup$ It may be possible, but I don't see an obvious and simple way to translate the problem into graph theory. That does not mean, of course, that the way does not exist. It just means I cannot help you. Sorry. $\endgroup$
    – 5xum
    Jun 2 '14 at 12:55
  • $\begingroup$ A ok..I edited my post,maybe you have an idea... $\endgroup$
    – evinda
    Jun 2 '14 at 13:16

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.