Folklore
In Chicago, there are 36 gangsters, some of whom are at odds with each other. Each gangster is a member of several gangs, and there are no two gangs with the same membership. It turned out that gangsters who are in the same gang do not feud, but if a gangster is not a member of a certain gang, then he feuds with at least one of its members. What is the maximum number of gangs that could exist in Chicago?
If gangsters are not enemies, we will consider that they are friends. Then a gang is the largest friendly group (adding any gangster violates its friendliness). We will call any such group a gang if it is not one already.

Example. Suppose gangsters are divided into 12 triples, gangsters from the same triple are enemies, and from different triples are friends. Then each gang contains exactly one gangster from each triple. Therefore, there will be $3^{12}$ gangs.

Estimate. First method. Let's call the authority of a gangster the number of gangs he is a part of.

Lemma. Suppose two gangsters are enemies. Then replacing one of them with a clone of the other, more authoritative one, increases the number of gangs. We assume that the gangster and his clone are enemies.

Proof. Consider gangster G. Each gang contains him or one of his enemies. Let the gangs of the first type form the set $A$, and the second type - $B$. Remove $G$.

In this case, all gangs from $B$ remain gangs, while some gangs from $A$, having lost a member, may cease to be gangs, losing their maximality.

We will show that no new gangs have formed. Consider a new gang. If it contains someone from the enemies of $G$, then it was already a gang from $B$. If it consists only of friends of $G$, then it is not possible to add enemies of $G$ to it, so $G$ was part of it before removal. Thus, this gang was already a gang from $A$.

Therefore, the number of gangs has decreased by no more than the authority of $G$.

Let gangster $X$ be a more authoritative enemy of gangster $G$. The authority of $X$ has not changed. Each gang now contains $X$ or an enemy of $X$. Add gangster $K$ - a clone of $X$. The former gangs will remain gangs, but gangs containing $K$ will be added, and their number is equal to the authority of $X$. Thus, the number of gangs has increased over the two operations.

Suppose the relationships of 36 gangsters are such that the number of gangs is the largest possible. From the lemma, it follows that in this case, enemies have the same authorities. Take any gangster $X$. Replace his enemy with a clone of $X$. According to the lemma, the number of gangs will not change. Therefore, the authorities of the enemies will again be the same. Consequently, we can replace another enemy of $X$ with a clone of $X$ without changing the number of gangs. We will do this with all the enemies of $X$. We will get a group of gangsters who are enemies of each other and are friends with all other gangsters.

Take a gangster not from this group and do the same with him, and so on. In the end, all gangsters will be divided into groups, where gangsters from the same group are enemies, and from different groups are friends. Then the number of gangs is the product of the sizes of the groups.