Skip to main content
MathOverflow

Return to Answer

Rollback to Revision 1 - Edit approval overridden by post owner or moderator
Source Link
JKreft
JKreft
  • 176
  • 8

$G(3,2)=\frac{1}{2}$.

Proof. Assume by contradiction that, for some family-set For any set $F$ composed of 3-element sets, Red haslet's assume there's a strategy that allows him to makesequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand and has two red elements inchosen out of more than half the sets in $F$ (a "strategy" means, despite A playing optimally. If B can force such a reply to every sequence of moves played by Green). Then, Greenthen A can makeforce the first move arbitraily, and from then onsequence $b_1,?,b_2,?\dots,b_k$ for itself, just copy Red's strategyleaving it with more than half the sets in (i.e$F$, reply to each sequence of moves played by Reddespite B playing optimally. Therefore, inB can never gain the same way Red would reply to that sequence if played by Green). This guarantees that there will beupper hand at least two green elementsany move in more than$G(3,2)$, so it can have at most half the sets with two of its chosen elements in $F$them.

$G(3,2)=\frac{1}{2}$.

Proof. Assume by contradiction that, for some family-set $F$ composed of 3-element sets, Red has a strategy that allows him to make two red elements in more than half the sets in $F$ (a "strategy" means a reply to every sequence of moves played by Green). Then, Green can make the first move arbitraily, and from then on, just copy Red's strategy (i.e, reply to each sequence of moves played by Red, in the same way Red would reply to that sequence if played by Green). This guarantees that there will be at least two green elements in more than half the sets in $F$.

$G(3,2)=\frac{1}{2}$.

For any set $F$ composed of 3-element sets, let's assume there's a sequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand and has two elements chosen out of more than half the sets in $F$, despite A playing optimally. If B can force such a sequence, then A can force the sequence $b_1,?,b_2,?\dots,b_k$ for itself, leaving it with more than half the sets in $F$, despite B playing optimally. Therefore, B can never gain the upper hand at any move in $G(3,2)$, so it can have at most half the sets with two of its chosen elements in them.

Suggesting an alternative wording of the same proof
Source Link
edit approved Aug 7, 2018 at 9:11
Erel Segal-Halevi
edit approved Aug 7, 2018 at 9:11
Erel Segal-Halevi
  • 3.5k
  • 20
  • 40

$G(3,2)=\frac{1}{2}$.

For any setProof. Assume by contradiction that, for some family-set $F$ composed of 3-element sets, let's assume there's a sequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand andRed has a strategy that allows him to make two red elements chosen out ofin more than half the sets in $F$, despite A playing optimally. If B can force such (a "strategy" means a reply to every sequence of moves played by Green). Then, then AGreen can forcemake the sequence $b_1,?,b_2,?\dots,b_k$ for itselffirst move arbitraily, leaving it with more than half the sets in $F$and from then on, despite B playing optimallyjust copy Red's strategy (i. Thereforee, B can never gainreply to each sequence of moves played by Red, in the upper handsame way Red would reply to that sequence if played by Green). This guarantees that there will be at any moveleast two green elements in $G(3,2)$, so it can have at mostmore than half the sets with two of its chosen elements in them$F$.

$G(3,2)=\frac{1}{2}$.

For any set $F$ composed of 3-element sets, let's assume there's a sequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand and has two elements chosen out of more than half the sets in $F$, despite A playing optimally. If B can force such a sequence, then A can force the sequence $b_1,?,b_2,?\dots,b_k$ for itself, leaving it with more than half the sets in $F$, despite B playing optimally. Therefore, B can never gain the upper hand at any move in $G(3,2)$, so it can have at most half the sets with two of its chosen elements in them.

$G(3,2)=\frac{1}{2}$.

Proof. Assume by contradiction that, for some family-set $F$ composed of 3-element sets, Red has a strategy that allows him to make two red elements in more than half the sets in $F$ (a "strategy" means a reply to every sequence of moves played by Green). Then, Green can make the first move arbitraily, and from then on, just copy Red's strategy (i.e, reply to each sequence of moves played by Red, in the same way Red would reply to that sequence if played by Green). This guarantees that there will be at least two green elements in more than half the sets in $F$.

Source Link
JKreft
JKreft
  • 176
  • 8

$G(3,2)=\frac{1}{2}$.

For any set $F$ composed of 3-element sets, let's assume there's a sequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand and has two elements chosen out of more than half the sets in $F$, despite A playing optimally. If B can force such a sequence, then A can force the sequence $b_1,?,b_2,?\dots,b_k$ for itself, leaving it with more than half the sets in $F$, despite B playing optimally. Therefore, B can never gain the upper hand at any move in $G(3,2)$, so it can have at most half the sets with two of its chosen elements in them.