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)  זה גם שם של אישה בצרפתית. זה ידוע לי כי זה זה שם של אחת הגיבורות ברומן הידוע 'עלובי החיים' של ויקטור הוגו. 

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

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