# Test Your Intuition (18): How many balls will be left when only one color remains?

(Thanks to Itai Benjamini and Ronen Eldan.) Test (quickly) your intuition:  You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same colour. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly $\sqrt n$?

3) Roughly log n?

4) Roughly a constant?

# Test Your Intuition (17): What does it Take to Win Tic-Tac-Toe

(A few more quantum posts are coming. But let’s have a quick break for games.)

Tic Tac Toe is played since anciant times. For the common version, where the two players X and O take turns in marking the empty squares in a 3 by 3 board – each player has a strategy that can guarantee a draw.

Now suppose that the X player has a budget of Y dollars, the O playare has a budget of 100 dollars and before each round the two players bid who makes the next move. The highest bidder makes the move and his budget is reduced by his bid.

For example, if, to start with, the X player have 120 dollars, and if for the first move X bids 40 dollars and O bids 30 dollars, then X will make the first move and will be left with 80 dollars while O will be left with his 100 dollars.

What would you expect the minimal value of Y is so the X player has a winning strategy? Of course if Y>300, X can make 3 uninterrupted moves and win, but perhaps much less is enough?

(Thanks to Reshef Meir and Moshe Tennenholtz)

Update: Another variant of this game is when the player winning the turn pays his bid to the other player. (This version is called “Richman game,” while the variant above is called “Poorman game”. In this case if Y> 800 the X player can play three moves and win. And again the question is what is the infimum value of Y for which the X player can force a win…

# What does “beyond a reasonable doubt” practically mean?

(Motivated by two questions from Gowers’s How should mathematics be taught to non mathematicians.)

# Test Your Intuition (16): Euclid’s Number Theory Theorems

Euclid’s

Euclid’s book IX on number theory contains 36 propositions.

The 36th proposition is:

Proposition 36.If as many numbers as we please beginning from a unit are set out continuously in double proportion until the sum of all becomes prime, and if the sum multiplied into the last makes some number, then the product is perfect.

It asserts that if $2^n-1$ is a prime number then $2^{n-1}\cdot (2^n-1)$ is a perfect number. (A number $m$ is perfect of it is equal to the sum of its proper divisors.)

This is certainly a remarkable achievement of ancient Greek mathematics. Other Propositions of the same book would be less impressive for us:

Proposition 23.If as many odd numbers as we please are added together, and their multitude is odd, then the sum is also odd.

Proposition 24.If an even number is subtracted from an even number, then the remainder is even.

Proposition 25.If an odd number is subtracted from an even number, then the remainder is odd.

Proposition 26.If an odd number is subtracted from an odd number, then the remainder is even.

Proposition 27.If an even number is subtracted from an odd number, then the remainder is odd.

Proposition 28.If an odd number is multiplied by an even number, then the product is even.

Proposition 29.If an odd number is multiplied by an odd number, then the product is odd.

Test your intuition: What is the reason that deep mathematical results are stated by Euclid along with trivial results.

# Test Your Intuition (15): Which Experiment is More Convincing

Consider the following  two scenarios

(1) An experiment tests the effect of a new medicine on people which have a certain illness. The conclusion of the experiment is that for 5% of the people tested the medication led to improvement while for 95% it had no effect. (The experiment followed all rules: it had a control test it was double blind etc. …)

A statistical analysis concluded that the results are statistically significant, where the required statistical significance level is 1%. This roughly means that the probability $p_1$  that such an effect happend by chance (under the “null hypothesis”) is less or equal 0.01. (This probability is called the $p$-value. Suppose that $p_1$= 0.008.)

(2) An experiment tests the effect of a new medicine on people which have a certain illness. The conclusion of the experiment is that for 30% of the people tested the medication led to improvement while for 70% it had no effect. (The experiment followed all rules: it had a control test it was double blind etc. …)

A statistical analysis concluded that the results are statistically significant, where the required statistical significance level is 1%. (Again, this roughly means that the probability $p_2$  that such an effect happend by chance (under the “null hypothesis”) is less or equal 0.01. And again suppose that $p_2$= 0.008.)

Test your intuition: In which of these two scenarios it is more likely that the effect of the medication is real.

You can assume that the experiments are identical in all other terms that may effect your answer. E.g., the theoretical explanation for the effect of the medicine. Note that our assumption $p_1=p_2$ is likely to imply that the sample size for the first experiment is larger.

# Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

## The Question

Suppose that you want to send a message so that it will reach all vertices of the discrete $n$-dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round $i$ all its neighbors will receive it at round $i+1$.

We will denote the vertices of the discrete $n$-cube by $\pm 1$ vectors of length $n$. The Hamming distance $d(x,y)$ between two such vertices is the number of coordinates they differ and two vertices are neighbors if their Hamming distance equals 1.

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (-1,-1,-1,…,-1). At round 2 you send the message to vertex (1,1,…,1). Then you sit and wait. With this strategy it will take $\lceil n/2\rceil+1$ rounds.

Test your intuition: Is there a better strategy?

The answer to the question posed in test you intuition (14) is no. There is no better strategy. The question was originated in Intel. It was posed by Joe Brandenburg and David Scott, and popularized by Vance Faber. The answer was proved by Noga Alon in the paper Transmitting in the n-dimensional cube, Discrete Applied Math. 37/38 (1992), 9-11. The result is closely related to combinatorial discrepancy theory and the proof is related to the argument in the Beck-Fiala theorem and a related lemma by Beck and Spencer. This is a good opportunity to present the Beck-Fiala Theorem.

## The general form of a discrepancy problem

Let $H$ be a hypergraph, i.e., a collection of subsets of a ground set $A$. $A$ is also called the set of vertices of the hypergraphs and the subsets in $H$ are also called edges.

The discrepancy of $H$, denoted by $disc(H)$  is the minimum over all functions $f:A \to \{-1,1\}$ of the maximum over all  $S \in H$ of

$\sum \{f(s):s\in S\}$.

The Erdős Discrepancy Problem (EDP) asks about the following particular hypergraph: The vertices are {1,2,…,n} and the edges are sets of vertices which form arithmetic progressions of the form (r,2r,3r,…kr}. EDP was extensively discussed and studied in polymath5. Here is the link of the first post. Here are links to all polymath5 posts.  Here is the link to polymath5 wiki.

## The Beck-Fiala theorem

Theorem (Beck-Fiala): If every element in $A$ is included in at most $t$ edges  of  $H$ then $disc(H)<2t$.

Before proving this theorem we mention that it is a famous open conjecture to show that actually $disc(H)=O(\sqrt t)$