问题是这样的 (1977 年第 19 届 IMO)

在一个有限项的实数序列中，任意的相连 7 项之和 < 0，任意的相连 11 项之和 > 0。求这种序列最多有几项。

竞赛题解网上有，就不表了…… 这里用程序蛮力解决。

显然这些约束都可以写成线性规划约束，用单纯形法求解。

我们考虑小一个层级的问题：任意相连 2 项之和 < 0，任意相连 4 项 > 0，那这个问题写成 GMPL 程序会是这样：

var x0;
var x1;
var x2;
var x3;
s.t. c1: 1*x0 + 1*x1 + 0*x2 + 0*x3 <= -0.1;
s.t. c2: 0*x0 + 1*x1 + 1*x2 + 0*x3 <= -0.1;
s.t. c3: 0*x0 + 0*x1 + 1*x2 + 1*x3 <= -0.1;
s.t. c4: 1*x0 + 1*x1 + 1*x2 + 1*x3 >= 0.1;
solve;
display x0,x1,x2,x3;
end;

如果有解，那执行 glpsol --math problem.mod 输出里会显示一行 "OPTIMAL LP SOLUTION FOUND".

于是我们从长度为 11 的序列开始生成 GMPL 程序，解解看到多长以后没有解，就能得出答案了。

def feasible? vars, args
  problem = []
  vars.each do |v|
    problem << "var #{v};"
  end
  n = 0
  args.each do |(coe, rgt)|
    n += 1
    lft = coe.zip(vars).map{|(c, v)| "#{c}*#{v}" }.join " + "
    problem << "s.t. c#{n}: #{lft} #{rgt};"
  end
  problem << "solve;"
  problem << "display #{vars.join ','};"
  problem << "end;"

  File.open 'problem.mod', 'w' do |f|
    f.puts problem
  end
  res = `glpsol --math problem.mod`
  if $?.exitstatus != 0
    puts res
    raise "problem failed"
  end
  !!res['OPTIMAL LP SOLUTION FOUND']
end

long = 11
short = 7
last_feasible = nil

(long..).each do |i|
  vars = (0...i).to_a
  args = []

  # short consecutives: <= -0.1
  vars.each_cons short do |vs|
    row = Array.new i, 0
    vs.each do |j|
      row[j] = 1
    end
    args << [row,  '<= -0.1']
  end

  # positive long consecutives: >= 0.1
  vars.each_cons long do |vs|
    row = Array.new i, 0
    vs.each do |j|
      row[j] = 1
    end
    args << [row, '>= 0.1']
  end

  var_names = vars.map{|j| "x#{j}"}
  if feasible?(var_names, args)
    puts "Feasible: #{i}"
    last_feasible = i
  else
    break
  end
end
puts "Longest sequence: #{last_feasible}"

程序输出（秒解）：

Feasible: 11
Feasible: 12
Feasible: 13
Feasible: 14
Feasible: 15
Feasible: 16
Longest sequence: 16

所以满足题目条件的序列最多有 16 项。