Minimalist Flooring

Responding to Eli's challenge:

Since $\lfloor{x}\rfloor>x-1$ we have $\sum_{j=1}^{n}\left(\left\lfloor\frac{\sum_{k\ne{j}}x_k}{x_j}\right\rfloor\right)>\sum_{j=1}^{n}\left(\frac{\sum_{k\ne{j}}x_k}{x_j}\right)-n=\sum_{k\ne{j}}\frac{x_k}{x_j}-n\geq{n(n-1)-n}$ as the sum contains $\frac{n(n-1)}{2}$ terms of the form $\frac{x_k}{x_j}+\frac{x_j}{x_k}\geq{2}$ . Thus $\sum_{j=1}^{n}\left(\left\lfloor\frac{\sum_{k\ne{j}}x_k}{x_j}\right\rfloor\right)\geq{n(n-1)-n+1=(n-1)^2}$ As Eli points out, this lower bound is attained.

There is actually a nice generalization of this result with $n$ variables: $\min_{x_1,\ldots,x_n \in \mathbb{R^+}} \left(\sum_{i=1}^{n} \left\lfloor\frac{\sum_{k\ne i} x_k}{x_i}\right\rfloor\right) = (n-1)^2.$

A construction of such $x_i$ is $x_1=n$ and $x_2=x_3=\ldots=x_n = n+1.$ In this case, that would correspond to $a=4$ and $b=c=d=5.$

The crux of the proof that this is the minimum can be done with the Cauchy-Schwarz Inequality and a little creativity. Try to figure out how!

I found the lowest value with an evolutionary algorithm :

Python 3.4:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

from math import floor
from random import random, choice
from time import time
population_limit = 10000 # iteration ends when reached
keep_best = 100 # creatures you keep after each iteration
diversity = 10000 # spawns random members in [0, diversity]
radioactivity = 10 # controls degree of mutation
mutation_choices = list(range(-radioactivity, 2))
def fitness(creature):
    # closer to 0 = more fit
    a, b, c, d = creature
    return floor((b + c + d)/a) +\
        floor((a + c + d)/b) + \
        floor((a + b + d)/c) + \
        floor((a + b + c)/d)
def mutate(creature):
    a, b, c, d = creature
    event = random()
    add = choice((1, -1)) * random() * 10**choice(mutation_choices)
    if event < 0.25:
        if a + add > 0:
            a += add
    elif event < 0.5:
        if b + add > 0:
            b += add
    elif event < 0.75:
        if c + add > 0:
            c += add
    else:
        if d + add > 0:
            d += add
    return (a, b, c, d)
def random_creature():
    return (random()*radioactivity,
        random()*radioactivity,
        random()*radioactivity,
        random()*radioactivity)
population = []
for creature in range(population_limit):
    population.append(random_creature())
population = [(fitness(creature), creature) for creature in population]
population = [i[1] for i in sorted(population)]
best = population[:keep_best]
population = best[:]
end = time() + 1
while time() < end:
    while len(population) < population_limit:
        population.append(mutate(choice(best)))
    population = [(fitness(creature), creature) for creature in population]
    population = [i[1] for i in sorted(population)]
    best = population[:keep_best]
    population = best[:]
print ("Lowest possible value:", fitness(population[0]))