-3
$\begingroup$

Given a natural number $n>1$,

natural numbers $a$ are chosen uniform randomly between $0$ and $n-1$ i.e.: $$0 \le a \le n - 1$$

and

natural numbers $b$ are chosen uniform randomly between $1$ and $n-1$ i.e.: $$1 \le b \le n - 1$$ The average $\delta$ of the distance $|a-b|$ between numbers $a$ and $b$ equals $6.5$.

What is the given value of $n$?

First, my true apologies for, initially, not having been conform forum guidelines.

As requested (by @Taladris): some additional information about question.

Have a look at answer provided, also upon request (by @lulu), where formula is derived.

Thanks all for getting me on rails.

I personally believe the formula is strikingly simple. Some people would perhaps expect numerical methods to be required for general reasoning, but not so.

Here is the motivation: average distance in this particular case (note $0 \le a$ and $1 \le b$) turns out to have a very simple formula in terms of $n$, allowing to, conversely, easily find $n$ in function of it. As it so happens, linear Gauss formula, and its quadratic generalization, in this particular case, both contain a common factor that perfectly cancels out for probability computation.

I have used (in disguise) the formulas for two puzzles (112210 112821) on puzzling exchange where also, conversely, some amount is asked in function of some average. So now I thought to present the math.

Have a nice day. I hope to contribute in simplicity.

To be honest: I doubted myself about the validity of such answer and therefore presented the question to the kind exchange community.

$\endgroup$
12
  • 3
    $\begingroup$ What have you tried? $\endgroup$
    – p_square
    Dec 18, 2021 at 16:19
  • 2
    $\begingroup$ I suggest: pick a number like $n=10$ or whatever and compute the expected value of $|a-b|$. That ought to give you a pretty good idea. $\endgroup$
    – lulu
    Dec 18, 2021 at 17:22
  • $\begingroup$ I would ideally want to see equation(s) that express $n$ in function of the average distance, and/or vice versa, so one can find $n$ by solving such equation(s). $\endgroup$ Dec 18, 2021 at 19:07
  • 1
    $\begingroup$ Please edit your post to include your efforts. I would not expect a simple closed formula, numerical methods will almost certainly be required. $\endgroup$
    – lulu
    Dec 18, 2021 at 21:55
  • 1
    $\begingroup$ I think this question and its answer have some interest, but its format is very unusual and confusing. If it was written in a more standard way, I would vote to re-open. $\endgroup$
    – Taladris
    Dec 21, 2021 at 0:26

2 Answers 2

1
+100
$\begingroup$

I will start with a few points aimed at the original poster, which they may find useful for the future; the actual problem at hand is going to be dealt with at the very end.

The original problem we are looking at can be summarized as follows: Two integers, $a$ and $b$, such that $0\leq a\leq (n-1)$ and $1\leq b\leq (n-1)$, are chosen uniformly randomly and we compute their distance $\delta=|a-b|$. For which values of $n$ is the expected value of $\delta$ equal to $6.5$?

Now, if one has such a problem, there are multiple questions that can be asked:

  • What should I do? I have no idea at all.

    If this is the case, don't forget to mention that last bit! The comments / answers you get are likely to be small hints or ideas how to start rather than fully-fledged complete solutions. If you manage to solve the problem, feel free to add your own answer.

  • I think I am on the right track but I got stuck. How to deal with this ugly sum?

    Provide the steps you took as part of the question statement. The answers / comments you get might provide a further hint (or a full solution). Again, if you happen to solve the problem yourself in the meantime, feel free to answer it too.

  • I think I have solved this problem but I am not sure if I did it correctly. Can you check my solution?

    Remember, your proposed solution should be part of the question here; with the request for verification of the solution (or certain parts of it) being included explicitly. There is even a nice tag one can use: [solution-verification]. The answer should either point out a flaw in the reasoning or confirm the validity of the approach, possibly filling some gaps if necessary.

  • I have a solution but it feels way too complicated. Can you find a better one?

    This is not that much different from the previous one: Show how you did it and ask for possible improvements. Of course, if you discover a simpler approach to solving the problem yourself, it can be a valid answer here too.

Note that in the last two cases, your original solution to the problem is not an answer; it is part of the question. In general, stating a problem and providing one's own answer without explicitly requesting further feedback from the audience is unlikely to elicit response, especially if the existing answer seems to be answering the question satisfactorily (people won't be adding their own answers unless they (substantially) improve upon the existing one; this is where is might be different from the puzzling SE).


In this particular case, the solution provided by the original poster is correct and is also reasonably simple; hard to be improved upon.

However, if one prefers a pull-out-of-a-hat magic trick, one can observe that for any $1\leq k\leq (n-1)$ there are exactly $(n-k)^2$ pairs of numbers $a$, $b$ for which $|a-b|\geq k$. In the matrix shown in OP's solution, such pairs form a bigger triangle in the upper-left corner and a tad bit smaller one in the lower-right corner; if we put them together, they add up to a square. Thus, the total sum of all numbers in the matrix is the same as sum of squares from $1$ to $(n-1)^2$. But there is a well-known formula for this sum: $\frac{1}{6}n(n-1)(2n-1)$. Dividing by $n(n-1)$ gives us the desired formula $\frac{1}{6}(2n-1)$ which yields $n=20$.

$\endgroup$
1
  • $\begingroup$ Thanks for detailed alternatives about how to ask questions one knows the answer for. I was relatively new to the math exchange back then and originally asked and answered the question rather as a puzzle where knowing the answer is common and hiding details in answer is trying to not spoil others ones efforts in advance. I apologize again for all that. $\endgroup$ Aug 7, 2022 at 11:04
0
$\begingroup$

$n = 20$

To calculate average distance between $a$ and $b$ there are a total amount of $n(n-1)$ pairs $(a,b)$ with: $0<=a<=n-1$ and $1<=b<=n-1$ so consider the $n*(n-1)$ matrix:

$\begin{bmatrix}|0-(n-1)| & .. & |(n-1)-(n-1)|\\: & |a-b| & :\\|0-1| & ... & |(n-1)-1|\end{bmatrix}$

The total of all distances between $a$ and $b$ is the total of the distances between all pairs in the square $n*n$ matrix:

$\begin{bmatrix}|0-(n-1)| & .. & |(n-1)-(n-1)|\\: & |a-b| & :\\|0-0| & ... & |(n-1)-0|\end{bmatrix}$

minus the total of the distances between all pairs from the excluded $n*1$ bottom row:

$\begin{bmatrix}|0-0| & .. & |a-b| & .. & |(n-1)-0|\end{bmatrix}$

giving (using standard formulas) : $$(n-1)n(n+1)/3 - (n-1)n/2$$ where the total amount of pairs $n(n-1)$ nicely cancels out in both terms and the average of the distance between $a$ and $b$ therefore is $$(n+1)/3 - 1/2 = (2n-1)/6$$ such gives $n=20$ for $\delta=6.5$

$\endgroup$
4
  • 2
    $\begingroup$ Do we need all these spoiler tags? This is a maths Q&A website. People know they would be "spoiled" when reading an answer. $\endgroup$
    – Taladris
    Dec 21, 2021 at 0:27
  • $\begingroup$ @Taladris ... I am very sorry and apologise ... I come from puzzling exchange where spoilers are 'part of the game' etiquette and the challenge is to find an answer rather than getting one. I will remove spoilers if you think that would help draw attention conform to math exchange policy. Again, sorry for clumsyness, I really wanted to show and have verified an IMO cool mathematical fact. $\endgroup$ Dec 21, 2021 at 0:36
  • $\begingroup$ All right :-) spoilers removed. Thanks for the constructive comments. $\delta = (2n-1)/6$ is (hopefully) the correct formula I humbly wanted to present... $\endgroup$ Dec 21, 2021 at 0:48
  • $\begingroup$ still sad :-( the simplicity of the result got negative votes, but, oh well :-) I enjoy this exchange $\endgroup$ Jul 12, 2022 at 1:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .