1

Let $A$ be a finite set with $n \geq 4$ elements and let $\rho$ be an equivalence relation on $A$. Suppose that there are exactly $4$ equivalence classes, $C_1$, $C_2$, $C_3$, $C_4$. Moreover we know that $|C_1| = |C_2| = 1$. Let $a\in A$ be a fixed element that we know is in $C_3$. What is the maximum number of ordered pairs of $(x, y) \in \rho$ in which a can occur (meaning $a = x$ or $a = y$ or $a = x = y$)?

Brian Fitzpatrick
  • 26,559
sfreeman2494
  • 43
  • This is what I currently have: In order to maximize the number of pairs that contain $a$, $|C_4|$ must also be equal to 1. If $n$ = 4, there is only one possible pair that contains $a$, which is ($a, a$). When $n$ = 5, you can add the fifth element, say $b$, to [$a$]. This would add the pairs ($a,b$) and ($b,a$). Therefore, each time you are adding two more possible pairs containing $a$. The answer ends up being $2n - 7$. – sfreeman2494 Mar 04 '14 at 03:28
  • +1 for showing your thoughts on the question. It makes it much easier to give a(n |I hope) useful answer. – Ross Millikan Mar 04 '14 at 03:55

1 Answers1

0

Hint: You are correct that to maximize the number of pairs you should have $|C_4|=1$, which gives $|C_3|=n-3$ But when you add the third element to $C_3$ you add more than two ordered pairs. $c$ can be paired with each of $a$ and $b$ in either order, so you add four pairs. Can you determine what happens for larger $n$?

Ross Millikan
  • 374,822
  • I thought $a$ had to be in the pair. Therefore, it only adds two more pairs each time an element is added to $C_3$. – sfreeman2494 Mar 04 '14 at 04:48