I don't understand this problem. How many cars are there in a position?

Thare are exactly n cars in a position.

Can you clarify the problem?I still don't understand it.

Are the cars 'labeled'? : can you distinguish the cars in a position?

Here is the original statement

Attachments:

Okay, I think it can be interpreted as: Define an arrangment to be a vector of length n, with each number in the vector an integer from 1 to n (not necessarily all different). Prove that there for any alpha there exists an n such that there exists a 100^n different arrangements that have a taxicab distance of at least n*alpha.

programjames1 wrote: Okay, I think it can be interpreted as: Define an arrangment to be a vector of length n, with each number in the vector an integer from 1 to n (not necessarily all different). Prove that there for any alpha there exists an n such that there exists a 100^n different arrangements that have a taxicab distance of at least n*alpha. Actually not. If the path of any two different cars overlap, then the minimum number of units needed to be fixed is smaller than just the taxicab distance.

Any solutions?

I don't think we understand the problem. How are you determining the "minimum number of units needed?"

programjames1 wrote: I don't think we understand the problem. How are you determining the "minimum number of units needed?" For two positions , construct $n$ segments on the road. each segment has car $i$'s first position and the last position as endpoints. Then the distance of two positions is the length of the union of $n$ segments

I think I see it then. It looks like this? [asy][asy] draw((0,0)--(10,0)); draw((2,0.2)--(7,0.2), green); draw((4, 0.4)--(8, 0.4), blue); draw((2,0.6)--(8, 0.6), red); draw((2, -0.1) -- (2, 0.1)); draw((4, -0.1) -- (4, 0.1)); draw((7, -0.1) -- (7, 0.1)); draw((8, -0.1) -- (8, 0.1)); [/asy][/asy] If the green represents the beginning and end points for car $A$ and the blue is the beginning and ending positions for car $B$, then the red would be the distance between cars $A$ and $B$.

In fact, we interpret the positions of cars as the set $F$ of all functions $f:\{1,2,\dots,n\}\to \{1,2,\dots,n\}$. Clearly $|F|=n^n$. The distance $d(f,g)$ between $f,g\in F$ is defined as $$\displaystyle d(f,g) := m\left(\bigcup_{i=1}^n [f(i),g(i)]\right)$$where $m(A)$ means the measure (length) of the set $A$ which is an union of intervals. The idea is as follows. For a function $f\in F$ we prove $\#\{g: d(f,g)<\alpha n\}$ is comparatively small. It may be interpret as a ball around $f$. As an implication it yields the maximal subset of $F$, every two elements of which at distance at least $\alpha n$ , has enough (more than $100^n$) elements for large $n$. Let $f\in F$ be fixed. For any $g\in F$ with $d(f,g)<\alpha n$ there exists a union $I$ of $(1-\alpha)n$ unit intervals on $[1,n]$ that don't intersect $[f(i),g(i)], i=1,2,\dots,n$. So, fix any such $I$ and let's see how many $g$ comply to this condition. The knots $i\in [1..n]$ inside $I$ are at least $(1-\alpha)n$. For each $i\in I$, $g(i)$ can take only values that hits the adjacent to $i$ interval in $[1..n]\setminus I$. Denote their number by $n_i$. Note that $\sum_{i\in I}n_i\le 2n$ since each knot of $[1..n]\setminus I$ is counted at most twice. Hence, the number of such functions $g\in F$ is at most $n^{\alpha n}\prod_{i\in I}n_i\le n^{\alpha n}2^n$. An upper bound of the number of all systems $I$ of unit intervals can be very roughly estimated by $2^n$. It yields $$\#\{g:d(f,g)<\alpha n\}\le n^{\alpha n}4^n $$Let $M$ be the number of elements of the maximal subset of $F$, every two elements of which at distance at least $\alpha n$. Then $$\displaystyle M \cdot 4^n n^{\alpha n}\ge n^n$$Hence, $$\displaystyle M\ge \left(\frac{n^{(1-\alpha)}}{4}\right)^n$$Since $\displaystyle \frac{n^{(1-\alpha)}}{4}>100$ for large enough $n$, the result follows.

@above Great solution! Maybe this is basically a similar approach, but in fact we can interpret the problem in an alternative way. For a position $S$, let $S_i$ be the set of cars that are on the interval $[1,i]$ Then, for two positions $S$ and $T$, we can calculate the distance between the two positions in a following way: Quote: $Distance =$ $||\{i :S_i=T_i \}||$ This works because $S_i=T_i $ means that there are no cars "crossing" the unit $[i,i+1]$ while moving to its first position to the second position. So all we have to do is construct $100^n$ positions so that at most $(1-\alpha)n$ indices satisfy $S_i=T_i $ for each pair. This is quite straight-forward since we can just calculate the probability.

Contradiction wrote: ... This is quite straight-forward since we can just calculate the probability. It sounds interesting, would you elaborate please?

@above, I think it's basically the same as yours, just with a different interpretation so I felt no reason for explaining it again. But anyways, let $\epsilon=1-\alpha$ and we want to show that the number of positions that have "coinciding indices" less than $\epsilon n$ be sufficiently small. So, fix the coinciding $\epsilon n$ sets $T_i$ and to fill up the rest $n(1-\epsilon)$ sets, the number is $\sum i_1^{n_1}i_2^{n_2}\cdots i_{n\epsilon}^{n\epsilon}$ where $i_1+\cdots+i_{n\epsilon}=n(1-\epsilon)$, $n_1+\cdots+n_{n\epsilon}=n(1-\epsilon)$ the scale of this formula is at most $(n(1-\epsilon))^{n\epsilon}$, and now since for efficiently large $n$ we have $100^n<\frac{n^n}{n^{n(1-\epsilon)}}$, we are done

A question about the distances beetwen them.What if we have disjoint segments?For example $[1,2]$ and $[4,5]$.What is the distance beetwen them?Is it $2$ or $4$?

We in fact prove the theorem for permutations. Let $f(\sigma, \pi)$ be their distance. We think of distance in another way: $f(\sigma,\pi) = |\cup_{j=1}^n [\sigma(j), \pi(j)] | = \sum\limits_{t\in [\sigma(j), \pi(j)] \text{for some j}} 1 =n-\sum\limits_{t\notin [\sigma(j), \pi(j)] \forall j} = n - \# (\{\sigma(1),\cdots,\sigma(x)\}=\{\pi(1),\cdots,\pi(x)\})$. Now we use my favorite trick when considering relations between pairs of elements: consider a graph of permutations such that two perms are adjacent if and only if their distance is at most $\alpha n$. We know this is a regular graph, so let $d$ be the degree of a permutation. Then any maximal independent set must have size at least $\frac{n!}{d+1}$ because the neighbourhood of $x$ vertices is at most $dx$. We now bound $d$. For at least $(1-\alpha)n$ values of $x$, $$\{\sigma(1),\cdots,\sigma(x)\}=\{\pi(1),\cdots,\pi(x)\}$$ which happens with probability $(\binom nx)^{-1}$ which is at most $n^{-1}$. Therefore, we pick $\binom{n}{(1-\alpha)n}$ choices for $x$ and we have the degree of a permutation is at most $n! \sum_{S} n^{(\alpha-1)n}$ where $S$ is over all subsets of $\{1,\cdots,n\}$ with cardinality $(1-\alpha)n$. This sum is at most $n! n^{(\alpha-1)n}\binom{n}{(1-\alpha)n}< n! n^{(\alpha-1)n}2^n$. Now, $\frac{n!}{d+1} \ge \frac{n!}{2d}>\frac 12 (n^{1-\alpha}/2)^n$. Picking $n^{1-\alpha}/2>200$ suffices.