Insert the $N$ guests, and in the $N$ gaps $g_i$ between them insert the hosts. Clearly $g_1 + \ldots + g_N = N$, and if a gap $g_i \leq 2$, the the two guests bounding it can talk. Furthermore, if two consecutive gaps ${g_i, g_{i+1}}$ (cyclically, so $g_{N+1} = g_N$) have sum $\leq 1$, the the guests bounding it can talk. It remains to show that the number of $g_i \leq 2$ added with the number of pairs of cosecutive $g_i$ summing to $\leq 1$ is $\geq N$. This is stupid. Let $k$ be the number of $g_i \geq 3$. These $g_i \geq 3$ gaps kill off at most $2k$ of the $N$ consecutive pairs in contention. So among the remaining $\geq N - 2k$ pairs, which sum to $\leq 2N - 6k$, clearly $<= N - 3k$ sum to $\geq 2$ else the sum is $> 2N - 6k$. So there are $\geq (N - 2k) - (N - 3k) = k$ pairs that sum to $\leq 1$. So total $\geq (N - k) + k = N$.

sniped Call a pair of guests a single if there are no guests between them, and a double if there is one guest between them. Let the value of a pair of guests be the number of hosts in between them. Notice that a single can talk to each other iff it is not separated, and a double can talk to each other iff its value is at most $1$. Say there are $S$ singles that cannot talk with each other, i.e. have value at least $3$. Notice that the hosts between a single are contained within exactly $2$ doubles, hence these $2S$ doubles have values at least $3$; let's call them bad, and the rest good. There are $N-2S$ good doubles. Now the sum of the values of all doubles is $2N$ since all hosts are counted twice, so the sum of the values of all bad doubles is at least $6S$, and the sum of the values of all good doubles is at most $2(N-3S)$. Now every good double either has value at least $2$ or can talk with each other. But the sum of the values of all good doubles is at most $2(N-3S)$, so there are at most $N-3S$ good doubles with value at least $2$. It follows that at least $S$ good doubles can talk with each other (since there are $N-2S$ good doubles). We have $N-S$ singles that can talk with each other and at least $S$ doubles than can talk with each other, hence we have $N$ pairs of guests that can talk with each other, as desired. $\blacksquare$

Here is an alternate solution. If the guests' talks "form a circle", then we are trivially done. Otherwise, there exists a guest next to a row of 3 hosts, talking to another guest. We proceed by induction on $N$. The base case, $N=3$ can be verified with 3 cases. It suffices to show we can remove a guest and a host such that the number of pairs of talking guests decrease by 1. Consider a guest next to at least two hosts that talks Case 1: HHGGG -> Removing H[HG]GG works, can be easily verified because the person to the left to the two hosts don't matter, and nothing to its right matters as well. Case 2: HHGHG -> HH[GH]G works: nothing to the right changes and nothing to the left changes. Case 3: HH[GH]HG Case 4: HHGGH Subcase 1: H[HG]GHG. If it's HH[HG]GHG then we lose two pairs but gain at most one from the guest to the removed guest's right. If it's GH[HG]GHG, then GHGHG gives at most 1 new pair to the guest in the middle from the left. Therefore, we have [>=2H's][2G's][>=2H's][2G's] forever. Since the number of hosts and guests are equal, it follows that it must be [2H's][2G's][2H's][2G's], so we are done.

Here is a low iq solution Let the guests in order be $g_1,g_2,\ldots,g_N$, so that $g_i$ and $g_{i+1}$ do not have a guest between them. Take indices $\pmod{N}$, so for instance $g_{N+1}=g_1$. Now define $a_1,a_2,\ldots,a_N$ such that $a_i$ is equal to the number of people between $g_i$ and $g_{i+1}$ (also take indices mod $N$). For instance, if $g_5$ and $g_6$ sat next to each other, then $g_5=0$, and if $g_3$ and $g_4$ had five hosts between them, then $g_3=5$. One can clearly see that for every $a_i \leq 2$ there exists a (unique) pair of guests talking with each other. One can also see that for every $i$ such that $a_i+a_{i+1}\leq 1$, there exists a (unique) pair of guests talking with each other, and that no other "combinations" of $a_i$ will cause any guests to talk with each other. With this in mind, let $w$ denote the number of $1 \leq i \leq N$ such that $a_i=0$, $x$ denote the number of such $i$ such that $a_i=1$, $y$ denote the number of such $i$ such that $a_1=2$, and $z$ denote the number of such $i$ such that $a_1>2$. Clearly this covers all of the $a_i$, yielding the condition: $$w+x+y+z=N.$$Now observe that since the sum of all of the $a_i$ must also equal $N$ (since there are $N$ hosts): $$x+2y+3z\leq N.$$I now claim that the number of $i$ such that $a_i+a_{i+1} \leq 1$ is at least $w-y-z$. In fact, the number of $i$ such that $a_i=1$ and $a_{i+1} \leq 1$ is at least this number. This is because ignoring the $a_i$ where $a_i \geq 2$ there are clearly $w$ such numbers $i$, and each $a_i$ with $a_i \geq 2$ "breaks" at most one such pair. Since there are obviously $y+z$ such $i$ with $a_i\geq 2$ the proof of the claim follows. This implies that there are at least: $$w+x+y+w-y-z=2w+x-z$$pairs of people who talk to each other. We wish to prove that this is at least $N$, or: $$2w+x-z \geq w+x+y+z \iff w \geq y+2z.$$This inequality is true, since: $$x+2y+3z \leq N \iff x+2y+3z \leq w+x+y+z \iff y+2z \leq w.~\blacksquare$$

Originally solved with p_square and Arwen713 and did something similar to KaiDaMagical336's above solution. Later I found this- We consider an edge between two guests if they can talk with each other and we divide the circle into blocks of guests and hosts. Now, consider any block of $a$ guests and say it is followed by(in clockwise order) $b$ hosts. Now, its easy to check that there are atleast $2a-b$ clocwise edges from this block of $a$ guests. Now, summing over all blocks of guests, we get that there are atleast $2N-N$ edges and we are done.

I think this works. I copied some part from #1 cause I think it's well explained. jj_ca888 wrote: Insert the $N$ guests, and in the $N$ gaps $g_i$ between them insert the hosts. Clearly $g_1 + \ldots + g_N = N$, and if a gap $g_i \leq 2$, the the two guests bounding it can talk. Furthermore, if two consecutive gaps ${g_i, g_{i+1}}$ (cyclically, so $g_{N+1} = g_N$) have sum $\leq 1$, the the guests bounding it can talk. It remains to show that the number of $g_i \leq 2$ added with the number of pairs of cosecutive $g_i$ summing to $\leq 1$ is $\geq N$. This is stupid. Let $k$ be the number of $g_i \geq 3$. These $g_i \geq 3$ gaps kill off at most $2k$ of the $N$ consecutive pairs in contention. The remaining is $\ge N-2k$. We want to prove that the number of $g_i \leq 2$ added with the number of pairs of consecutive $g_i$ summing to $\leq 1$ is $\geq N$: $$(N-2k)+(N-k) \ge N$$$$\iff N \ge 3k$$The last is obvious

This is a pretty grindy solution. Basically, we shall transform the given seating step by step so that the number of pairs of chatting guests does not decrease with each step. Then, once the configuration is special enough, we put numbers into the game and get it done. First, note by "obvious" case bash that any host that sits immediately between $2$ guests can be removed without decreasing the number of chatting pairs. Now, partition the resulting seating into blocks of consecutive guests and blocks of consecutive hosts so that the host blocks and guest blocks alternate. Note that within a guest block with $k$ guests, there are at least $2k-3$ chatting pairs, and each host block of size $2$ gives us one pair of chatting guests. Therefore, the number of chatting pairs is at least $2N-3g+t_2$ where $g$ is the number of guest blocks (which is equal to number of host blocks of course), and $t_r$ is the number of host blocks of size $r$. Now, we can finish it in an unintuitive and magical way like this: $$2N-3g+t_2 = 2N-3(t_2+t_3+t_4+t_5+\dotsb)+t_2 = 2N - (2t_2 + 3t_3 + 3t_4 + 3t_5 + \dotsb) \ge 2N - (2t_2 + 3t_3 + 4t_4 + 5t_5 + \dotsb) = N.$$

Does this work? Let us define the "size" of a guest to be $1$ and the size of a host to be $\tfrac 12$. The clockwise distance between two persons $A$ and $B$ is defined to be the sum of the sizes of persons between $A$ and $B$ when going clockwise from $A\to B$, and denoted by $d(A,B)$. In particular, (i) If $A$ and $B$ are adjacent and $A$ is before $B$ clockwise, then $d(A,B)=0$. (ii) If the config is $G_1\star \star\;G_2$, where at least one of the $\star$ is a host, then $d(G_1,G_2)\le 1.5$. (iii) If the config is $G_1\star G_2$, then $d(G_1,G_2)\le 1$ (iv) The function $d$ takes only half integer values. Label guests clockwise $G_1,\ldots, G_N$. By (ii), (iii) and (iv), we can say that two guests chat if $i<j$ and $\lfloor d(G_i,G_j) \rfloor\le 1$. Note that $d(X,Y)\ge 2\iff \lfloor d(X,Y)\rfloor \ge 2$. It is easy to check the following equalities: \begin{align} \sum_{j=1}^N d(G_j,G_{j+1}) &=\frac N2 \\ \sum_{j=1}^{ N} d(G_{j},G_{j+2}) &=\frac {3N}2 \end{align}In $(1)$, number of $d\ge 2$ is at most $\tfrac 14N$ and in $(2)$, the number of $d\ge 2$ is at most $\tfrac 34N$. The rest $\ge 2N-(\tfrac 14 N+\tfrac 34N)=N$ terms must satisfy $\lfloor d(\bullet,\bullet )\rfloor \le 1$, so we are done. EDIT: There seems to be some error. Checking if it can be salvaged. In particular, we need to find particular sums like (1) and (2). The first sum is correct but the second one looks incorrect.

My solution: Let $h-chain$ be a chain of consecutive host and the same for $g-chain$. If a pair of guests can chat to one another, call this pair $chatable$ if there is a host between any 2 guests we can remove that host without changing the problem, so assume all $h-chain$ has length at least 2. Let $x$ be the number of $h-chain$ of length 2, $y$ be the number of $g-chain$ of length at least 3, we have $2x+3y \leq N$ Its easy to count within a $g-chain$ of length $l$ there are $2l-3$ chatable pairs, and with a $h-chain$ of length 2, there is a $chatable$ pair seated on two side of this $h-chain$. Note that there are $(x+y)$ $h-chains$ so there are $(x+y)$ $g-chains$ Therefore we have $x+ (2N -3(x+y))=2N -2x-3y \geq N$ $chatable$ pairs

Bad solution, will edit later ...? Define a desert to be at least three consecutive hosts bounded by guests. Note if there are no deserts, each guests talks with their neighbor, resulting in at least $N$ conversations. Consider $N=4,$ supposing there are less than $N$ conversations. We place the $4$ guests, and we must place $3$ of the hosts together. Then, wherever we place the remaining host (there are only three distinguishable choices), it is clear that there are at least $4$ conversations. Hence, assume $N>4$ and number the guests $G_1,G_2,\dots,G_N.$ If we only place the guests, there will be $N$ conversations between $G_i$ and $G_{i+1}$ with $1\le i\le N$ and $N$ conversations between $G_i$ and $G_{i+2}$ with $1\le i\le N,$ where $G_{N+1}=G_1$ and $G_{N+2}=G_2.$ Hence, there will be $2N$ conversations without any hosts. Now, place $\ell>0$ deserts. If the desert is between guests $G_i$ and $G_{i+1},$ we are removing conversations $(G_i,G_{i+1}),$ $(G_{i-1},G_{i+1}),$ and $(G_i,G{i+2}).$ Hence, $3\ell$ conversations are removed, and we are left with $\ell$ strings of guests and at most $N-3\ell$ hosts. We wish to find the maximum conversations which can be removed using the remaining hosts. Consider a string of $m$ guests, such as $G_iG_{i+1}\dots G_j,$ where we can insert hosts between two consecutive guests. We claim that $h<m$ hosts can prevent at most $h$ conversations. We claim the position where hosts can stop the most conversations is alternating guests and hosts, which would prove our first claim as all conversations of the form $(G_{k},G_{k+2})$ would be prevented. Indeed, if we have a configuration with at least one gap between two guests, say $G_k$ and $G_{k+1}$ with two hosts, move one of the hosts to the gap between $G_{k+1}$ and $G_{k+2}$ if it is empty; if not, move it to any other empty gap. This will not increase the number of conversations as the only conversation the displaced host had been preventing was $(G_k,G_{k+2})$ and it is still prevented. Thus, the hosts $N-3\ell$ can prevent at most $N-3\ell$ conversations. Thus, there are at least $2N-(3\ell)-(N-3\ell)=N$ conversations. $\square$

Essentially similar to rg's solution, posting for storage. Let us consider $A_1, A_2 \dots A_{k}$ to be the maximum disjoint continuous blocks of guests in the circle in clockwise order and $B_1, B_2 \dots B_{k}$ to be the maximum disjoint continuous blocks of hosts in the circle in clockwise order. We claim the following: Claim : Going clockwise, if $B_i$ is the maximum continuous block of hosts adjacent to $A_i$ and $A_{i+1}$ , then the number of pairs of guests chatting in the block $A_i$ to any other guest is greater than or equal to $2|A_i| - |B_i|$. Proof : If $ |B_i|\geq3$ , then observe that the number of guests talking in $A_i$ to another guest in $A_i$ is equal to |$A_i|-1 + |A_i|-2 = 2|A_i|-3 \geq 2|A_i|-|B_i|$ . If $|B_i| = 1$ , then observe that the left most guest $G_j$ from $A_{i+1}$ can talk to right most and second right most guests in $A_i$ , implying that number of pairs of guests talking in $A_i$ to any other guest is $\geq |A_i|-1+|A_i|-2+2 = 2|A_i|-1 = 2|A_i|-|B_i|$ . If $|B_i| = 2$ , then observe that the left most guest $G_1$ from $A_{i+1}$ can talk to the right most guest in $A_i $, implying that the number of pairs of guests in $A_i $ talking to any other guest is $\geq |A_i|-1 + |A_i|-2 + 1 = 2|A_i| -2 = 2|A_i|-|B_i|$ . Thus, our proof for the claim is complete. Coming back to the main question, we observe that the minimum number of guests talking to each other is at least $\sum\limits_{i=1}^k 2|A_i| - |B_i| = 2N - N = N$ , as desired.