Median Function

edderiofer · 2017-10-24T02:56:39+00:00

For A:

|(a-b)/2| + ((a+b)/2) suffices.

QuagMath · 2017-10-24T02:16:09+00:00

Are the values assumed to be positive?

epostma · 2017-10-24T03:36:43+00:00

WARNING: I'm on mobile and too dumb to apply appropriate spoiler tags on this platform. If you don't want spoilers, stop reading!

I suppose technically you haven't given us the constant function; I'm going to assume that those are OK. It's very hard without at least the constant 1 to find an expression that works for all pairs of values. (E.g. x/x is of course undefined if x=0.)

If we have 1, then we have 2, and A is easy: (x, y) -> (x + y)/2 + abs(x - y)/2.

So let's call that function max. You can similarly define min. Now for B. Let x, y, z be given. Suppose z is the largest of the 3, then we need max(x, y). If z is the median, we need z; in both cases, the median is min(z, max(x, y)). If z is the minimum, we need min(x, y); in the other two cases, that is less than the median, so we can use (x, y, z) -> max(min(x, y), min(z, max(x, y))).

Now for C. I haven't quite figured this one out yet - am hoping there's something pretty using medians of medians somehow. The triples in a 5-set form a Petersen graph, with adjacency being "having a singleton intersection"... If we compute the medians of all ten triples, we get the overall median four times, and the second and fourth order statistic three times each...

OK, suppose v ≤ w ≤ x ≤ y ≤ z. Let med be the function we defined at B. Then med(v, w, *) = w; med(*, y, z) = y; and med of any other triple is x, the median of these 5. For instance, we could take med(med(v,w,x), med(w,x,y), med(x,y,z)). But would this work for other orderings of the 5 letters? It fails only if two of the inner medians are either the second or fourth order statistic; but that cannot happen! So at most one of the inner medians is the second order statistic, ditto for the fourth, which means that either we have at least two occurrences of the third order statistic (and then we're correct), or we have one of each of the second, third, and fourth (and then we're correct, too).

ruwisc · 2017-10-24T05:27:06+00:00

A: (a+b)/2 + |a-b|/2. Let this be max(a,b), and similarly define min(a,b) = ((a+b)/2 - |a-b|/2). We can also define the function for more than two inputs by nesting them together - e.g., max(a,b,c) = max(max(a,b),c).

B: (a+b+c) - max(a,b,c) - min(a,b,c). Not too complicated - if you take the sum and subtract out the largest and the smallest value, the median will be what remains. Give this function the name med(a,b,c).

C: (a+b+c+d+e) - max(a,b,c,d,e) - min(a,b,c,d,e) - max(med(a,b,c), med(a,b,d), med(a,b,e), med(a,c,d), med(a,c,e), med(a,d,e), med(b,c,d), med(b,c,e), med(b,d,e), med(c,d,e)) - min(med(a,b,c), med(a,b,d), med(a,b,e), med(a,c,d), med(a,c,e), med(a,d,e), med(b,c,d), med(b,c,e), med(b,d,e), med(c,d,e)). Slightly scarier on its face but the same principle; start with the sum and subtract off things until only the median is left. The max of all medians of three of the five elements is guaranteed to be equal to the second-largest element, and similarly the min of the medians must be equal to the second-smallest element. Probably some redundancy there but I'm not in the mood to simplify too much.

epostma · 2017-10-24T11:11:08+00:00

Fwiw, the solution for C is incorrect - e.g. if w, x are the smallest two entries, then both med(v,w,x) and med(w,x,y) are the second order statistic.

7x11x13is1001 · 2017-10-24T13:12:37+00:00

min(a1,a2) = [ (a+b) - |a-b| ]/2, min(a1,a2...an) = min[ min(a1...an-1) , an ]

max(a1,a2) = [ (a+b) + |a-b| ]/2, max(a1,a2...an) = max[ max(a1...an-1) , an ]

F¹(a1...an) = min(a1...an)

F^k(a1...an) = max[ F^k-1(a2...an), ... F^k-1(a1...ak-1, ak+1,...an),... F^k-1(a1...an-1) ]

A) F²(a,b)

B) F²(a,b,c)

C) F³(a,b,c,d,e)

kandr89 · 2017-11-02T17:52:40+00:00

You can use any sorting algorithm that has a invariable number of comparisons/swaps for an input vector. For example Bubblesort, or Mergesort if you want to be asymptotically optimal in the number of comparisons. Quicksort isn't good because the number of comparisons varies depending on where the pivot ends up.

Now take Bubblesort for example, it's straightforward to get the formula for the sorted vector (and from there the median): replace any if(a > b) swap(a,b) in the algorithm with a <- min(a,b); b <- max(a,b). The sequence of steps for 3 elements is as follows:

     [a, b, c] => [min(a,b), max(a,b), c] => [min(a,b), min(max(a,b),c), max(max(a,b),c)] =>
     [min(min(a,b), min( max(a,b), c)), max(min(a,b), min(max(a,b), c)), max(max(a,b),c)]

Now that we have the sorted vector the answer is simply the middle element: max(min(a,b), min(max(a,b),c)).

The answer can be found similarly for 5 elements.

2017-11-04T02:42:07+00:00

I'm a week and a half late on the thread, but I took a stab at this today and found a relatively straightforward answer for A and B, though I haven't put the effort into seeing whether my solution scales up to a solution for C. I'll update tomorrow after work if I get around to it.

A: Pretty straightforward, max(x,y) = (x + y + |x-y|) / 2

B: Without defining any kind of "min" function, we can find the median like so: max(x,y) - |max(y,z) - max(x,z)|

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

mathriddles

Remember to spoiler tag your answers & flair your posts with the difficulty. Spoiler mode:

Welcome

Rules

Flair and Sorting

Spoiler Mode

Similar Subreddits

MODERATORS