Counting Pieces

This problem is from Futulity Closet  wonderful site who itself brought this from Ross Honsberger's book - Mathematical Delights:

"In a certain chess position, each row and each column contains an odd number of pieces. Prove that the total number of pieces on black squares is an even number."

You can see a nice "simple" solution in Futilty Closet, but I would like to post a different solution involving linear algebra.

Let \(A\) be the \(8\times8\)  matrix that represents the pieces configuration. This matrix \(a_{ij}\) entry is \(1\) if there is a piece on that entry else it is \(0\).  It can be thought of a matrix in \(\mathbb{F}_{2}^{8,8}\) - that is over the finite field of 2 elements.

Let \(v^{t}=\left(\begin{array}{cccccccc}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\in\mathbb{F}_{2}^{8}\) , from the given data it can be shown that
\(Av=v\), (sum of each row is odd ) and that  \(v^{t}A=v^{t}\) (sum of each column is odd).

We want to prove that the sum of the pieces in the dark squares is even, it can be shown that this sum is actually the trace (sum of diagonal) of the multiplication of \(A\) with a certain matrix \(B\),
where \(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).

If \(AB=C\), check that \(c_{11}\)  is the number of pieces in the first black row, \(c_{22}\) is the number of all pieces in the second black row etc.

So we can see that the number of pieces in the black squares is even if and only if \(tr(AB)=0\) mod 2.

The matrix \(B\) can re presented as the sum of two 1-ranked matrices:

\(B=\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0
\end{array}\right)\).

Each of those 1-ranked matrices can be represented as a multiplication of vectors:

\(B=\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).

Now we know that \(v\) is an eigen-vector of \(A\). Using that, we can compose \(v\) into two parts

\(Av=A\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)=A\left(\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\).

Thus

\(A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)-A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\).

The last equality is because \(-1 = 1\) mod 2.

Replacing this in the multiplication of \(AB\).


\(AB=A\left(\begin{array}{c}
1\\
0\\
1\\
0\\
1\\
0\\
1\\
0
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)

\(=\left(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)=\)
\(=\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\)
\(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)\).

But note that the first matrix term \(\left(\begin{array}{c}
1\\
1\\
1\\
1\\
1\\
1\\
1\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)\) is a matrix with even trace, that means that we can neglect it.

\( tr(AB)=tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right))\).

\( =  tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)(\left(\begin{array}{cccccccc}
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0\end{array}\right)+\left(\begin{array}{cccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{array}\right)))\) =

\(tr(A\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))\).

Now we use the famous equality \(tr(AB)=tr(BA)\).

\(=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A)\).

But \(\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)A= \left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right)\)  (remember?).
So, finally:

\(tr(AB)=tr(\left(\begin{array}{c}
0\\
1\\
0\\
1\\
0\\
1\\
0\\
1
\end{array}\right)\left(\begin{array}{cccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\end{array}\right))=\)

\(tr\left(\begin{array}{cccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{array}\right)=0.\)

Drunkard's Walk Puzzles

שתי חידות הליכת שיכור

1.
שיכור מהלך על ציר ה- \(x\). הוא מתחיל מ \(X_{0} = 0\). בכל צעד הוא מתקדם  צעד ימינה ( כלומר  \(X_{n+1}=X_{n}+1\) ) בהסתברות של חצי או צעד שמאלה  (\(X_{n+1}=X_{n}-1\))  בהסתברות דומה.

מהם הסיכויים שהוא יגיע לנקודה  \(2N\)  לפני \(-3N\) ? ( כאשר \(N\)  הוא פרמטר) .

2.
שיכור מהלך על ציר ה- \(x\). הוא מתחיל מ \(X_{0} = 0\). בכל צעד הוא מתקדם  צעד ימינה בהסתברות של
 \(p=\cfrac{2}{3}\)   או צעד שמאלה בהסתברות  \(\cfrac{1}{3}\) .

מהם הסיכויים שהוא יגיע לנקודה  \(N\)  לפני \(-N\) ?

אם יש לכן תשובה פרסמנה אותה בתגובות. אני אפרסם פתרון לשתי החידות בהמשך.

1. A drunkard is walking on the \(x\)-axis starting on \(X_{0} = 0\). Every step he walks one step to the right (that is - \(X_{n+1}=X_{n}+1\)) with probability \(p=\cfrac{1}{2}\) or one step to the left (\(X_{n+1}=X_{n}-1\)) with the same probability.

What is the probability that he would reach \(2N\) before reaching \(-3N\)? (where \(N\) is an integer a parameter)

2. A drunkard is walking on the \(x\)-axis starting on \(X_{0} = 0\). Every step he walks one step to the right with probability \(p=\cfrac{2}{3}\) or one step to the left with probability \(\cfrac{1}{3}\)

What is the probability that he would reach \(N\) before reaching \(-N\)?

If you have a solution post it on the comments. I will post a solution in the future.

מגילות סן מיקלה

את 'מגילות סן מיקלה' הכרתי לראשונה דרך הסופר האהוב עליי, מאיר שליו, שסיפר עליו באחת מההרצאות הכתובות שלו.

קראתי אותו בשקיקה לפני הרבה שנים ולאחר שהנחתי אותו מהיידים (ואולי גם במשך הקריאה עצמה) פשוט לא יכולתי להאמין שלפני מאה שנים בערך חיי לו אדם שצבר חוויות וסיפורים שהיו יכולים להשביע עשרות אנשים בתקופת חייהם.

קינאתי בו כשהוא טייל בלפלנד עם נערה מקומית בתור מורת דרך, כשהוא סיפר על הלקוחות ההזויים שהוא טיפל בהם ברומא, כשהוא עזר לניצולים ברעידת האדמה במסינה, כשהוא סיפר על המחלוקת שהייתה לו עם פרופ' שארקו (המומחה להיפנוט) בפאריס...


מה עם הסיפורים שלי? (ושלכם?)
 האם הם שווים ספר?
טור בעיתון?  
פסקה?

רוצה סיפורים בחיים. סיפורים שיסמרו אנשים. סיפורים בלשים פילמ-נואריים כאלה, אפשר גם אגאתה כריסטיים, סיפורי הרפתקאות כמו 'אי המטמון' ו ( הכנס כאן סיפור הרפתקאות שהוא לא 'אי המטמון'), אפשר גם סיפורי מסעות ופואנטה כמו 'קאנדיד' (שלו אני חייב להקדיש פוסט נפרד!)  ו'הניסוי של השופט פוט'.
סיפורים רבותיי, סיפורים.

אבל בעצם... הייתי נותן את הכל בשביל להוכיח שאין מספר מושלם אי-זוגי.

5:27 בבוקר

אז הנה אני כאן יושב וכותב, יושב ומהרהר....

ככלל אני לא אוהב לחשוב על החיים  - מניסיוני ככל שמרבים לחשוב עליהם, כך נהיים מדוכדכים יותר.

אבל הפעם הזאת היא טיפה שונה.

התעוררתי לפני כשעתיים לאחר נדודי שינה קשים. אני ממש לא מבסוט מהנקודה שאליה הגעתי כרגע בחיים שלי.

מלכתחילה תנאיי ההתחלה לא היו פשוטים.

התייתמתי מאמי בגיל מאוד צעיר ולאחר כמה שנים גם מאבי. 

אני לא אוהב לדבר על זה או לכתוב על זה כי בשבילי מוות תמיד היה עניין מאוד פרטי, מאד אישי. 

החוייה של לגדול וללמוד בחטיבת הבניים והתיכון עם המשא הייתה מאוד לא נעימה - התבודדתי הרבה, היו לי מעט חברים. וכן - מעולם, אבל מעולם לא הצלחתי להסתדר עם המין השני.

פעמיים בחיים שלי התאהבתי - הפעם הראשונה הייתה חוויה מדהימה. היא גרמה לי לרצות להיות בן אדם יותר טוב ולצאת מהבור העמוק שבו הייתי.

 אבל זה היה קרב אבוד מראש, בכלל לא חשבתי על להתחיל איתה.

הפעם השנייה הייתה בסטודנטית לארכיטקטורה - היא הייתה (ואני מניח שעודנה עוד) בחורה יוצאת דופן. בחורה משוחררת, חזקה והרפתקנית.

 היא הייתה מלאת בסתירות - התכונה שאני הכי לא אמור להעריך (אחרי הכל אני מתמטיקאי)
אבל בעצם- כן, כן ועוד פעם כן! (אחרי הכל אני מתמטיקאי) 

אני מניח שגם הקרב הזה היה אבוד מראש.

ומאז עוד דייט ועוד דייט

 ועוד קרב אגו עם המנחה שלי שגרם לי לעזוב את האקדמיה

 ועוד דייט ועוד דייט. 

ואני עדיין לא מצליח להתחבר.

האם כל הקרבות אבודים מראש?

מספיק לנצח רק פעם אחת, לא? 

ומי בכלל רוצה  להלחם? 

The mathematics of listening to songs - Part 2

In this post I will prove that the strategy that is presented in the previous post 

is indeed an optimal strategy in the sense that it minimize the expected number 

of button-pressing for reaching a certain song.

One of the ways to show this is using the model of decision tree. Every algorithm/strategy that has a final number of states (in our case the states represented by the number of the song) and a final number of decisions to make (in our case there are three decisions in every state - pressing 'prev'/'next'/'rdm') can be presented as a rooted tree.

Pic 1. Directed Rooted Tree

'tree' means a connected graph with no cycles.

'rooted' means that there is a special node (vertex) in the tree that we consider to be the common ancestor of all other nodes. Rooting a tree induces a natural direction on the tree edges: from the root to its neighbors, from its neighbors to the rest of their neighbors and so on... (see pic 1). 

For example: consider the case where there are only three songs, we start from song no. 1 and want to reach song no. 3. We decide to press 'rmd' one time and then to 'prev'/'next' until we reach the song.
then the desired decision tree will look like :

Pic 2. Simple Decision Tree.

I have decided to color random decision with red and deterministic decision with blue; 

Also note that random-decision nodes have 3 descendants (representing all the nodes that the random pressing might lead to) while deterministic-decision nodes have only one descendant.

Before I start the proof I need to present a few definitions:

Definition: A decision tree that represent a successful strategy for reaching a song (will reach the song with a finite expected number of decisions) shall be called Finite Pressing Tree (FPT).

Definition: The average height (AH) is defined in the following recursive manner:

The average height of a leaf (node with no descendants) is 0.

The average height of a FPT is the 1+ the average of the average height of its root's descendants.

For example the average height of the tree in Pic. 2 is \(AH = 1 +\cfrac{1}{3}\cdot(2+2+1)=\cfrac{8}{3}\).

Observation: The average height of FPT is simply the expected number of pressing of the strategy it represents.

Definition: The set of FPTs that their initial state is \(i\) and end state \(j\) shall be denoted with \(T(i,j)\).

Definition: For any \(i\) and \(j\), \(OptT(i,j)\) is the set of all \(T\in T(i,j)\) such that for any \(U\in T(i,j)\) \(AH(T)\leq AH(U)\). 

Theorem: For any \(i\) and \(j\), \(OptT(i,j)\) is not empty, that is there exists a optimal strategy.

I actually don't need this theorem, but it makes the proof much more easier. One way for proving this theorem is to define a certain topology on \(T(i,j)\)- such that this topology would be compact and the AH function would be continuous- Existence of a minima is immediate. 

We have two important lemmas in to order prove our goal. The first one is the observation that you should not use 'deterministic' buttons before random buttons:

Lemma 1: Suppose that \(T\in T(i,j)\) and throughout the algorithm that \(T\) represents we press a deterministic 'prev/next' button that is represented by a node \(d\) of the tree. Suppose further that one of the descendants of this node is a random pressing ('rdm') node, then \(T\notin OptT(i,j)\). 

proof: We can construct another tree \(U\in T(i,j)\) such that \(AH(U) < AH(T)\). The construction is the following: follow the route of node \(d\) untill we reach a 'rdm' node \(r\) (remember that all the buttons are deterministic, there is only one path) - To generate the new tree simply replace the node \(d\) with the node \(r\). (i.e throw away the deterministic path). Note that this new graph is still in \(T(i,j)\). Moreover, we only reduced one of its branches' height so the overall average height is decreased (see Pic 3). 

                         

Pic 3.  Every decision tree that uses deterministic buttons before non-deterministic buttons could be reduced to a tree with a strictly smaller average height.

We conclude that with optimal strategy if we press a deterministic button then we must press deterministic buttons all the way till we reach our goal.

Lemma 2: Suppose that \(T\in T(i,j)\) and throughout the algorithm that \(T\) represents we reach a node \(v\) with state \(k\), then the sub-tree \(K\) that its root is \(v\) is a FPT and \(K\in OptT(k,j)\).

proof: The proof is straightforward. The average height of \(T\) should be some convex combination that one of its terms is the average height of \(K\) - if \(K\) is not optimal then \(T\) is not optimal. 

Now we can glue everything together to prove the main goal: 

Let \(T\in OptT(i,j)\) . We know from the previous post that pressing 'rdm' all the time is not an optimal strategy. Therefore there must be a node of the tree \(v\) where we press a deterministic button; Suppose that the state represented by the node is \(k\) - we know from Lemma 1 that all the decision following this node are deterministic all the wall until \(j\). We search for other occurrences of \(k\) in the decision tree. From Lemma 2 we know that if there is an occurrence then its sub-decision tree should be optimal, note that the pressing deterministic buttons all the way is also an optimal strategy! Therefore, for every vertex of \(T\) that represents state \(k\) (regardless of its branch) we can replaces its sub-tree with a deterministic branch and \(T\) should still be an optimal FPT. 

Altogether we have that an optimal strategy should be of the form :

A. Press 'rdm' untill \( Distance(i,j) < f(n) \).

B. Press 'prev/next' to reach \(j\).

How should \(f(n)\) look like? The expected value of number of button-pressing \(N\) should be (see previous post)  \(\mathbb{E}N = \cfrac{n}{2f(n)}+\cfrac{f(n)}{2}\).

Minimizing the above formula yields \(f(n) = \sqrt{n} \).

\(\square\)

The mathematics of listening to songs - Part 1

"What is mathematics?"  The Professor asked us in the first class of Set Theory. None of us could find a satisfying answer. Finally he replied : "Mathematics is the study of patterns". 

What particularly nice about this definition is that it suggests that one could find mathematics in many areas, not only in science and engineering but also in our every day life - if only we will listen and pay attention for the right clues; I would like to post here an example where an every daily boring trip with a car can be mathematically fascinating.

Suppose you are driving your car alone in the night listening to your favorite songs in your mp3 player. You are listening now to song number 32  ('Ramona' by Beck Hansen from the Scot Pilgrim's soundtrack)  the song is over and you are in the mood for song number 103 ('39 by Queen). 

A conventional mp3-player has three buttons for controlling the songs flow- 

'prev' button, 'next' button and a 'rdm' (random) button. (see pic) 

Assuming that you have a circular list of 300 songs in the mp3-player, how should you press the button to reach the song?  

The obvious way is to press 'next' button 71 times but remember that you are a safe driver and want to avoid accidents. Pressing the same button so many times might  be dangerous (and tedious). Is there a strategy that allows you to press buttons as little as possible?

Close inspection of two strategies

In order to understand what do I mean by 'as little as possible', let us analyze two strategies:

Suppose that we have a circular list of \(n\) songs. Assume that we are now in song \(i\) and that we want to reach song \(j\).

Strategy 1 - Pressing 'prev/next' to reach j.
Since the list is circular there are two paths between any two songs - and the maximal distance should be   \(\cfrac{n}{2}\). Now, assuming  that  \(i\) and \(j\) are uniformly distributed (i.e are arbitrary) their distance should be uniformly distributed between \(1,...,\cfrac{n}{2}\) (not counting the case where \(i=j\)). This would give us an expected number of \(\cfrac{n}{4}\) pressings.

Strategy 2 - Pressing 'rdm' until the destination.
This strategy is also easy to analyse - In each press, the odds of reaching the desired song are \(p=\cfrac{1}{n}\). The number of button-pressing is a geometric random variable with parameter \(p\), it is known that its expected value is \(\cfrac{1}{p}=n\).

Note that the number of button-pressing in both strategies yield a  linear result that is, they belong to the class of \(O(n)\).

Now we can state the problem: Does there exist a strategy that yields an expected number of button pressing that is asymptotic better than  \(O(n)\)?
.
.
.
The answer to this problem is yes!


Optimal Strategy - 
A. Press 'rdm' until \(Distance(i,j)<\sqrt{n}\).
B. Press 'prev/next' to reach j.

Let us calculate the expected time for this strategy: Suppose \(T\) is the number of button-pressing for reaching song \(j\). Note that \(T\) is a random variable and that we can decompse it to two random variables \(T=R+U\), where:
 \(R\) is the number of button-pressing for reaching the set \(A=\{k\in{1...n}|Distance(k,j)\leq\sqrt{n}\}\)  (note: \(|A|=2\sqrt{n}\)).
\(D\) is the number of 'prev/next' button-pressing.

The probability for reaching the set \(A\) each time we press the 'rdm' button is \(p=\cfrac{|A|}{n}=\cfrac{2}{\sqrt{n}}\) - hence \(R\) should be a geometric random variable and \(\mathbb{E}R=\cfrac{1}{p}=\cfrac{\sqrt{n}}{2}\).

After reaching the set \(A\) we can be in any one of the songs \(j-\sqrt{n},..,j+\sqrt{n}\) and the probability to be in any one of these songs is uniform, so \(D\) should be uniformly distributed in the set \(\{1,...,\sqrt{n}\}\}\) and,as the case of strategy 1, \(\mathbb{E}D=\cfrac{\sqrt{n}}{2}\).
altogether \(\mathbb{E}T=\mathbb{E}R+\mathbb{E}D=\sqrt{n}\), which is \(O(\sqrt{n})\).


Proving that this strategy is optimal is quite hard and technical. I will discuss it in my next post.

אות חיים

אז חזרתי עוד לכתוב כאן מתוך שעמום.

עשיתי כאן טיפה שינויים כי אני רוצה שהפרסומים שלי שעוסקים במתמטיקה יהיו גם נגישים לקורא באנגלית.

מבדיקה זריזה גיליתי שהשם 'ravens and writing desks'  הוא לא כל כך מקורי - יש לפחות ארבעה בלוגים שונים שנושאים את השם הזה או וריאציה כלשהי שלו. מצד אחד זה מעודד שיש כל כך הרבה מעריצים של לואיס קארול, אבל מצד שני זה מבאס בגלל אובדן היחודיות. שקלתי לשנות אותו אבל אז הבנתי שאני פשוט לא מסוגל לחשוב על שם אחר שמתאים יותר.

זה הזכיר לי שלפני שש שנים בערך אימצתי מ'תנו לחיות לחיות' כלבה בשם 'סנדי'. כשהגיע הרגע לשנות את השם שלה ממש רציתי לקרוא לה 'קוסט' (Coset)  מכמה סיבות:

א. קוסט זה שם של אובייקט מתמטי מ'תורת החבורות'.

ב. קוסט (Cosette)  זה גם שם של אישה בצרפתית. זה ידוע לי כי זה זה שם של אחת הגיבורות ברומן הידוע 'עלובי החיים' של ויקטור הוגו. 

בסופו של דבר אני שמח שהחברים שלי עצרו אותי (כלומר, צחקו עליי מספיק) כדי שאני אבחר בשם הזה ובסוף נשארתי עם השם הסטנדרטי,  'סנדי'. 

אז הנה שוב אני כותב כאן כאיזה סוג של תרפיה בבלוג שמספר האנשים הכולל שקרא אותו כנראה אינו עולה על מספר האצבעות ביד של בארט סימפסון. שיהיה לי בהצלחה.

Picking marbels from a jar - rigorous proof

Hurray! I have returned :)


Let's start from an easy one:
The following is a well known puzzle. I have encountered it several times in my life.

(cited from:
http://www.techinterview.org/post/526363745/red-marbles-blue-marbles/)

"You have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red."


Solution:
The solution to this puzzle is to throw one red marble to one of the jars (say, w.l.o.g, jar A) and to throw all other marbles (49 reds and 50 blues) to the other jar (jar B). If we do so the probability to pick a red marble is:
 

\(P(picking\, a\, red\, marble)=\)

\(P(picking\, a\, red\, marble|choosing\, jar\, A)\cdot P(choosing\, jar\, A)+\)

\(P(picking\, a\, red\, marble|choosing\, jar\, B)\cdot P(choosing\, jar\, B)=\)
\(1\cdot\frac{1}{2}+\frac{49}{99}\cdot\frac{1}{2}\sim0.74\)

This solution is also well known and easy to come up with, however most of the places and web sites that solve this puzzle fail to post a convincing proof for this solution. Indeed trying to find a rigorous explanation for it might be seem a little  tedious, but it is essential -from my experience facts that seem 'obviously true' can fall apart easily with close inspection. 


Proof of Solution
The method of the proof is the following:
We start with any  ordering of the marbles in the jars (we call this ordering 'ordering 1'( and show that the probability to draw a red marble in this ordering will always be smaller or equal than the probability to draw a red marble with the ordering of the solution (we call this ordering- 'ordering 2').

We use the following notations:
(These notation are all with respect to ordering 1)
The number of blue marbles in jar A - \(\textrm{N}_{blue}^{A}\)

The number of red marbles in jar A - \(\textrm{N}_{red}^{A}\)

The number of blue marbles in jar B - \(\textrm{N}_{blue}^{B}\)

The number of red marbles in jar B - \(\textrm{N}_{red}^{B}\)

W.l.og - we assume that \(\textrm{N}_{red}^{A}\leq \textrm{N}_{red}^{B}\).
We also need to assume that \(0<\textrm{N}_{red}^{A}\). Because if one of the jar doesn't have any red marbles then the probability of getting a red marble is \(\frac{1}{2}\cdot\frac{50}{50+\textrm{N}_{blue}^{B}}\leq\frac{1}{2}\) which is smaller than the probability of our solution.

Now let us move all the blue marbles from jar A to jar B. We call this new ordering - 'ordering 3'.

Lemma 1

First I will show that :
\(\frac{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\geq\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\)   (1)

Proof of Lemma 1
This inequally is valid  if and only if both the l.h.s and the r.hs.  complementaries to 1 will satisfy the opposite inequallity:

\(\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\leq\frac{\textrm{N}_{blue}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\).

Note that the denominator of the l.h.s is greater than the denominator of the r.h.s- hence this inequality holds.

We will show that:

\(P(picking\, a\, red\, marble\, with\, ordering\, 1)\leq P(picking\, a\, red\, marble\, with\, ordering\, 3)\)

Proof:

\(P(picking\, a\, red\, marble\, with\, ordering\,1)=P_{1}=\)

\(\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}+\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\)

\(P(picking\, a\, red\, marble\, with\, ordering\,3)=P_{3}=\) 

\(\frac{1}{2}\cdot1+\frac{1}{2}\cdot\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\) 

We take the difference between \(P_{3}\) and \(P_{1}\) and get :

\(P_{3}-P_{1}=\)

\(\frac{1}{2}\cdot\left(1-\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)

\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)

\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}}\right)\)

\(\geq\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)+\frac{1}{2}\cdot\left(\frac{\textrm{N}_{red}^{B}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}-\frac{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\)

Where the last inequality holds because of Lemma 1 ( we subtract a smaller  quantity). Carring on :

\(=\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)-\frac{1}{2}\cdot\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\).

Now all we need to show is that :\(\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{A}+\textrm{N}_{blue}^{A}}\right)\geq\left(\frac{\textrm{N}_{blue}^{A}}{\textrm{N}_{red}^{B}+\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}}\right)\).
but this inequality holds since \(\textrm{N}_{blue}^{B}+\textrm{N}_{blue}^{A}\geq\textrm{N}_{blue}^{A}\), and \(\textrm{N}_{red}^{B}\geq \textrm{N}_{red}^{A}\) because of our assumption. Therefore the denominator of the l.h.s is smaller than the denominator of the r.h.s.

We have proven the 'hard part'. We are only left with the relatively easy part of proving that moving from ordering 3 to ordering 2 can only increase the odds of getting a red marble. I leave this proof for the reader.

  

 

משולש

Universal Mind / The Doors

I was doing time
In the universal mind,
I was feeling fine.
I was turning keys,
I was setting people free,
I was doing alright.

אני חושב שאני יכול בהחלט להעיד על עצמי שאני לא מבין גדול במוזיקה. 

 אף על פי כן, היא לוותה אותי במשך חיי, יש שירים שפשוט מייצגים את התקופה.

אז פעם לפני הצבא הייתי מכור לImagine של לנון ולא יכולתי שלא להקשיב לו כל איזה חצי שעה.

זה השיר היחידי שאני זוכר את המילים שלו בעל פה (ויש לי זכרון מאוד גרוע למילים של שירים) 

בגלל שאני חושב שהקשבתי לו  (נטו בזמן אוויר) איזה שבוע  מהחיים שלי.

יש פשוט משהו מאוד מהפנט בדרך שלנון שר את ה"יואו-הו-או-הווו" לפני שהוא מתחיל הפזמון.

( בדיוק כמו שאלטון ג'ון מענטז עם הקול שלו  בסוף כל בית בשיר "goodbye yellow brick road" )

Then you came along,
With a suitcase and a song,
Turned my head around.
Now I'm so alone,
Just looking for a home
In every place I see.

קורה שבאמצע נסיעה ברכב אתה שומע איזה שיר מסקרן ואז מגיע איזה סולו או אקורד או צליל של משולש*
ובעצם אתה מוצא את עצמך מקשיב באמת למילים שלו. הוא נכנס אליך ואתה מבין שהשיר הזה הוא כבר בכרומוזומים שלך.

יש לי כבר כל כך הרבה שירים כאלה.

I'm the freedom man,
I'm the freedom man,
I'm the freedom man,
That's how lucky I am.

*  בשיר "Good old fashioned lover boy"  מסתתר צליל של משולש, ויש לי חבר שחושב שאי אפשר לעשות קאבר לשיר בלי הצליל הזה. צודק!

מה נשמע?

במסגרת הפרוייקט האישי שלי להעלות  לאינטרנט דברים שחיפשתי במשך שנים ולא מצאתי

אני מביא לכם מאמר של מאיר שלו שפעם נגע מאוד לליבי:

 מאיר שלו- מה נשמע? 

( 8.2.2002.  המוסף לשבת)

אני משער שהקוראים כבר שמו את ליבם לתופעה הלשונית
המעניינת שמתחוללת כאן באחרונה.  פעם כשהיית שואל
מישהו "מה נשמע?" או "מה שלומך?".  היית מקבל תשובה
פשוטה ? "טוב" "רע" "בסדר" "ככה ככה".  אבל היום כל
מי שנשאל לשלומו עונה בהתחכמויות ובהתפתלויות שמעידות
על תערובת של גישה בריאה לחיים עם מנה נאה של דאגה ומבוכה.

כיוון שכך ערכתי מחקר קצר וחובבני שאלתי ודרשתי ואף
הטיתי אוזן לשיחות לא לי והרי לפניכם הלקט המעודכן של
תשובות שאנשים משיבים ל"מה נשמע?"

קבוצת התשובות הראשונה מעידה על תחושה של ניכור והפרדה מן הכלל:

 "אני בסדר, אבל המדינה בזבל"

 "אתה שואל בספציפיות או בכלליות?"

"מה נשמע אצלי או מה נשמע אצל כולנו?"

 "אישית על הכיפאק"

 "הרוב בסדר"

לכך מצטרפת עוד תשובה חדשנית : "במיקרו על הכיפאק
במאקרו על הפנים" 

( את התשובה הזאת אפשר ורצוי להפוך
בייחוד אם אתה תרנגולת בשלב ההפשרה)

הקבוצה השנייה היא של שימושים מחודשים בביטויים ישנים.

"חרא-גיל" .  תשובה זו ל"מה נשמע? " היא הכלאה של המילה "חרא"
עם המילה "כרגיל" והיתה נפוצה מאוד בשנות החמישים והשישים
אחר כך נעלמה מן השוק ובימים אלה שבה והתחדשה ( מעניין למה?)

"וואלה?"( כאן חשובה מאוד האינטונציה שעל הנייר קשה
להעבירה( אין זו ה"וואלה" של תימהון ושל סימן שאלה ולא
ה"וואלה" של "הבנתי אותך" אלא "וואלה" שנאמרת בנמיכות
מסוימת, ואפילו במונוטוניות של חוסר-ברירה. כיוון שאיני יכול
לומר "סבבה" או "אחלה" אומר "וואלה" שמשמעותה מאיכשהו
נסחבים או "זה מה יש"

 "סוף הדרך"

( ביטוי זה שבדרך כלל מביע שבחים והתפעלות

התחיל להיאמר כ"סוף הדרך" פשוטו כמשמעו )

"המצב בטטה" 

( מטאפורה וגטטיבית קצרה. ייתכן שהומצאה על ידי שונא בטטות

או כנגזרת פונטית של "המצב בתחת")

הקבוצה השלישית של תשובות ל"מה שלומך?" מציגה חדירת
נוסחים דתיים לפה החילוני. אולי הדבר קשור לצורך הדחוף
שאנו חשים בסיעתא דשמייא ?, אבל עובדה היא, שגם בועלי
טריפות ואוכלי נידות התחילו משיבים ל"מה שלומך?" במלים
כמו " ישתבח שמו"  "השם יעזור" ו"ברוך השם"  לתשובה האחרונה 

התפתחה גם וריאציה חביבה  "בְרוֹך השם".

לקבוצה הרביעית מצטרף המימד הכרונולוגי,

התשובה המקובלת "יהיה טוב" התחלפה באחרונה 

ב"היה טוב". כמו כן אומרים "נכון לרגע זה, בסדר" או

"חיים, עד הפיגוע הבא".

יש גם תשובה עם מלכודת:  "יותר טוב" השואל מגיב בתמיהה:  "ממה יותר טוב? 

ואז עונים לו:  "היום יותר טוב ממחר".

בקבוצה החמישית של התשובות ל,מה שלומך?" משתלבים
תיאורי אופן מצב ופעולה. כאן נמצאות תשובות לאומיות גאות
כמו "מכניסים להם" ו"מראים להם" ובצידן תשובות מהסוג של

"מורידים את הראש ומחכים" ( חשוב לציין שלשון הרבים של
התשובות האלה מעידה על כך שהמשיבים בניגוד לאנשי הקבוצה 

הראשונה עדיין רואים עצמם חלק מן הציבור).

הקבוצה השישית היא של אלה שמשיבים בשאלה נגדית: 

"בתור מה אתה שואל אותי?"

"מה אתה רוצה לשמוע בתור תשובה?"

ותשובה נוגעת ללב ל"מה שלומך?" :"מה זה חשוב?" או
"מה זה משנה?"

לכך מצטרפות גם כמה תשובות מתריסות:
"מה שלומי? אין לי מושג, עוד לא קראתי עיתון"

"אתה רוצה תשובה דובר-צה"ל או תשובה את האמת?"

וכן "עזוב אותי מהשמאלנים" ולחלופין:  "עזוב אותי משרון"

והקבוצה האחרונה היא של מי שיש להם גם כושר המצאה. על
השאלה "מה שלומך" הם ענו בתשובות הבאות:

 "תשאל את ההנהלה"

 "בסדר גמור, עם דגש על הגמור"

 "הכל בסדר, רק חסר קצת מלח בפצעים"

ואחד מחברי שזה שנים היה משיב על "מה שלומך" ב"תודה, רע" 

התחיל באחרונה לענות: "סביר מינוס, נא להתקשר שוב
שעה לפני הנחיתה"

את כל התשובות הנ"ל שמעתי בהיאמרן לי או לאחרים.

למותר לציין שאשמח לקבל ולפרסם עדכונים ותוספות.

בפעם הבאה במסגרת הפרוייקט: קטעים מ"המעופפים הנועזים" בעברית.

אהובתי

אהובתי לא צריכה לדעת שום דבר במתמטיקה,
רק מה הנגזרת  של .

זה עניין עקרוני

On Terrorists and Ultrafilters

One of the coolest puzzles ever:

Three Big-Endian terrorists have plated a bomb somewhere in Lilliput's Little-Endian quarter.
The police was able to capture them however they refuse to cooperate and deliver the location of the bomb.

The police chief decided ti separate them to three cells and every day to chose one to be electroshocked.

The terrorists are not able to control when the bomb will be detonated, however it's still can be exploded by other members of the terrorist organization or by chance.

If the bomb explodes the authorities will punish the terrorists by electrifying  two of them every day.

After infinity days (this is were it gets abstract) the terrorist die and go to heaven. Each of them
is brought before God separately and is asked whether the bomb has exploded or not.

If at least two terrorists answer rightfully they all go to heaven.
otherwise: hell it is!

Before entering the jail rooms the terrorists are given some time to plan a strategy to
go to heaven, after which they don't see one another and don't communicated.
(i.e each terrorist know only what happened to him after infinite days.)

Can they devise a winning strategy?

Formal Defenition


It is a little boring to convert this problem, but it usually makes problem brighter :

We are given three binary sequences . We know that excluding finitely many n; There are two possibilities:

1.          for all n.
2.          for all n.

Is it possible to find a function   such that

A. If case 1 occurs then at least two of the numbers are 0.

B. If case 2 occurs then at least two of the numbers  are 1 ?

We want to say that if we are terrorist we "see" a sequence of zeros and one

(0 represent a day without show and 1 otherwise) and we see "a lot" of 1s then we should say that the bomb has exploded.

This function exists but how can we prove it mathematically?

To understand it we must know a basic idea from Set Theory:
 Every binary sequence is equivalent to a subset of the natural numbers:

Therefore the first thing for the prisoners to do is to convert the sequence to a subset of the natural numbers.

Theorem:

There exist a function that satisfy to following properties:

A.

B. .

C.

Those two properties remind us the properties of the measure function, but two major differences:

there is no sigma-additivity (only finite sums) and the values are only 0,1.

We can conclude from (A-C) the following  properties:

Properties:

1.

From property (A)  the fact that only 0,1 value are allowed.

2.

3.

4.

( from (1) (from (3) (De-Morgan law)

First we show  how the existence of this function helps the terrorists to go to heaven:

Lets assume that the bomb didn't explode. we can prove that at least two of the terrorist have said no. (the terrorist say no if the function value is 0 on his subset)

since only one of them was electroshock everyday it means that the subset representing

their sequences are mutually disjoint! :

therefore at least two of them must say no!.

Lets assume that the bomb had exploded, them because of property (B) we can assume that is has exploded on the first day. Pick any two of the terrorists.

Every day, at least one of them was electroshock, therefore:

at least one of them must say yes !

because we picked any two terrorists it must mean that at least two of them said yes!

Why such function exists?- Axiom of Choice FTW!

Once again, we think of the function a little differently. We think of it as a collection of subsets of the natural numbers by :

What are the properties of this subset (we can conclude it from properties of the function)

i. (this means it is close to supersets)

ii.

iii.

iv.

Definition: 

A non empty collection of subsets that not contains the empty set satisfying properties i and ii is called filter. If it satisfy property iii as well it is called ultra-filter.

Ultra-filter do exists: for example is an ultra-filter however this

ultra-filter don't satisfy property iv.

Ultra-filters that do satisfy property iv are called non-principal or free ultra-filter, their existence must be assumed or be proven with AC.

Theorem:

Let be an infinite set, then there exist an free ultra-filter on .

Proof:

Every filter is contained in a maximal filter. (Zorn's Lemma)

We show that every maximal filter is an ultrafilter: Denote our maximal filter ; Notice that contains the all set since we can add it to the filter without interfering with the filter propertyies.

Because that it not contains the empty set, we know :

Else it could be shown with property (ii) that it contains the empty set.
Now we prove property (iii); Let us assume that , then because of the maximality :   (because the r.h.s is also a filter)
since contains , . This proves is an ultra-filter.

Now we can define the filter: (it is indeed a filter because is infinite)

This filter is contained in an ultrafilter .

The ultra-filter contains no finite subset - assume is finite, this means because of property iii of the ultra-filters. but which is a contradiction.

Quite remarkable, isn't it?