1
$\begingroup$

Determine whether the function f is one-to-one

f(t) is the number of people in line at a movie theater at time t.

$\endgroup$
  • $\begingroup$ Don't you mean $f(t)$? Do you understand what a one-to-one function is? $\endgroup$ – Git Gud Sep 25 '13 at 16:39
  • 2
    $\begingroup$ Not necessarily one to one. We could have $f(t_0)=17$, and at some later time $t_1$, $f(t_1)=17$. This could happen in a couple of ways: (i) The line has not moved or (ii) It has moved, $3$ people have entered the theatre, but $3$ have joined the end of the line. $\endgroup$ – André Nicolas Sep 25 '13 at 16:41
  • $\begingroup$ One to one means that you can (in theory) uniquely figure out the input if you know the input. $\endgroup$ – copper.hat Sep 25 '13 at 17:01
1
$\begingroup$

Informally, we can think of a one-to-one function as one that maps distinct elements in the domain to distinct elements in the codomain. Or, in other words, if $f$ maps $a$ and $b$ map to the same thing, then $a=b$.

Formally, a function $f:A \rightarrow B$ is called one-to-one if $f(a)=f(b)$ implies $a=b$. Equivalently, if $a \neq b$, then $f(a) \neq f(b)$.

In this question, we have a function $f:T \rightarrow \mathbb{Z}^{\geq 0}$ defined by $f(t)$ is the number of people in line at a movie theater at time $t$, and $T$ is the set of times for which "time" is defined. The task is to find two distinct times $t_1 \in \mathbb{R}$ and $t_2 \in \mathbb{R}$ for which $f(t_1)=f(t_2)$.

Here's a simple mathematical answer; it assumes (a) the theater has been open longer than an instant, and (b) there are a finite number of people in existence.

  • Suppose there are $N<\infty$ people in existence. We pick $N+1$ distinct points of time $t_1,t_2,\ldots,t_{N+1}$ (assuming the theater has been open longer than an instant, since time is continuous, such points of time exist). Then the pigeonhole principle implies there are two points in time $t_i$ and $t_j$ in which $f(t_i)=f(t_j)$; in other words, we have $N+1$ numbers $$f(t_1),f(t_2),\ldots,f(t_{N+1})$$ that all belong to $\{1,2,\ldots,N\},$ so they can't all be distinct.
$\endgroup$
  • $\begingroup$ $0$ is also a possible value of $f$... $\endgroup$ – user103402 Nov 20 '13 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.