解きました。フィードバックは大変なんでしょうね～。
最初に書いたコードでは、F（12）までとてもとてもまともな時間で計算できなかった。
想定時間30分で12のときまで解くのは結構ハードだと思う。

恥ずかしながら半日～1日くらい？？

【問題】

n 個のリール（数字が描かれている部分です）を持つスロットマシンを回します。

各リールには、0 から 9 のいずれかの数字がランダムに出ます。

このとき、「最も多く出現した数字の出現回数」に等しいドルが賞金として得られます。

例えば n = 6 のスロットマシンを考えましょう。

各リールに、左から順に 7 7 5 1 0 7 という数字が出たとします。

このとき、7 の数字が最も多く 3 回出現していますので、賞金は 3 ドルです。

リールの数字が 0 2 0 9 2 6 のとき、賞金は 2 ドルです。

リールの数字が 1 2 3 4 5 6 のとき、賞金は 1 ドルです。

リールの数字が 8 8 8 8 8 8 のとき、賞金は 6 ドルです。

このスロットマシンを 1 回まわしたときの賞金の期待値を F(n) とします。

例えば F(1) = 1，F(2) = 1.1，F(3) = 1.29 となることが確かめられます。

■ 第１問 （Normal）

F(6) の値を求めて下さい（四捨五入は不要です）。

■ 第２問 （Hard）

F(12) の値を求めて下さい（四捨五入は不要です）。

【方針】
○ nをn以下で10個までの自然数の和に分割する方法が何通りあるかを計算する。
（このとき、同時に賞金ごとに分類しておく）
○ 上で計算した分割方法ごとに、リールの数字が何通りあるかを計算し、期待値を求める。
○ たとえば、n=6で4点のときは、[4, 1, 1], [4, 2]　の2通りの分割があり、
それぞれ、 (10*9*8)*(6!/4!)/2!, (10*9)*(6!/4!/2!)/1!通りの組み合わせになる。
配列の長さmについて、(10からmとる順列)*(並べ方の数)/(配列中に同じ数字があれば割引く)通り。（うーん、我ながらわかりにくいか。）

【rubyの提出コード】

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
BASE=10 # スロットが10進数で回る。
def solve(n)
  score_sum=0 # スコアの総和
  count_sum=0 # （デバッグ用）スロットの並び方の総和
  make_array(n).each{|score, arrays|
    arrays.each{|arr| # nと賞金で決まる配列ごとにループ
      # 対称性を考慮して、並べ方の数を数える。
      # 配列の中の同じ数字があるかどうか。
      sym=(1..n).map{|i| arr.count(i)>1 ? arr.count(i) : nil }
        .compact.map{|i| facto(i)}.reduce(&:*) || 1
      # 上の対称性も考慮した、並べ方の数。
      part = facto(n)/arr.map{|i| facto(i)}.reduce(&:*) / sym
      # 配列の中の数字にそれぞれ0-9の数字を当てはめる
      count = permu(arr.length) * part
      count_sum += count
      score_sum += score*count
    }
  }
  #  print "count(#{n}) = #{count_sum}\n"
  score_sum.to_f / BASE**n
end
# 普通の階乗計算
def facto(n)
  $facto||=[1]
  $facto[n]||=n*facto(n-1)
end
# BASE個の中からn個とる順列
def permu(n)
  ((BASE + 1 -n)..BASE).reduce(&:*)
end
# nをBASE個までの整数の和に分割し、賞金ごとに分けたHashに配列の配列として格納。
# たとえば n=3 のとき、{1=>[[1, 1, 1]], 2=>[[2, 1]], 3=>[[3]]}を返す。
def make_array(n)
  ret = Hash.new{|h,k| h[k]=[] }
  min = 1 + (n-1)/BASE
  (min..n).map{|sc|
    tmp = rec(sc,n).reject{|arr| arr.length > BASE }
    ret[sc].push(*tmp)
  }
  ret
end
# nと賞金が決まった時の、可能な自然数への分割を配列の配列で返す。
def rec(sc,n,ret=[],all=[])
  sum = ret.reduce(&:+) || 0
  num = n-sum
  if n == sum
    all << ret
  elsif num == sc
    ret << sc
    all << ret
  elsif sc == 1
    num.times{ ret << 1 }
    all << ret
  elsif num > 0 && num >= sc
    ret << sc
    (1..[sc,n-sc].min).each{|_sc|
      rec(_sc,n,ret.dup,all) # 次の数は直前に格納した数字と同じか少ない。
    }
  else
    nil
  end
  all
end

(1..20).each{|i|
  print "F(#{i}) = #{solve(i)}\n"
}

問題はこちら
http://riverplus.net/codeiq/CutAndSquare.pdf

かいつまんで言うと、
[偶数 n に対して、先頭にゼロを持たない n 桁の整数で上 n/2 桁と下 n/2 桁とに分け、それぞれを 2 乗して和をとると、元の数に戻るような数で、n=6, n=10の場合を求めよ。]という感じ。
色々と回答があるようで、参考になったな～。

で、Rubyで書いた提出コードが下記。
sqrtの結果を整数に丸めるあたりが怪しい気がするが、まぁ、当たりでないときは外れるはずだからOKのはず。

ideone.comにも置きました。便利だね。
http://ideone.com/eMPnrv

【方針】
求めるN桁の数をnとし、 n = a * 10**(N/2) + b とする。
n = a**2 + b**2 (b>0, a>10**(N/2 – 1)) の条件を満たす整数a,bを見つける方針でとく。
１． n = a**2 + b**2 の1桁目に注目すると、aの1桁目の数字は0,2,8のみとなる。
　　　（Excelで100通りをすべてチェックしましたが、a,bの下1桁の値の組み合わせは8通りしかありません。）
２． 条件の式からbについて解くことができるので、各aについて、bが条件を満たす整数かどうかをチェックする。
　　　（bについてはループしなくて済む。）

N=10
Base2=10**(N/2)

result = []
((Base2/10)...Base2).select{|a| # aの下1桁を0, 2, 8に絞る。
  tmp = a%10
  tmp == 0 or tmp == 2 or tmp ==8
}.each{|a| # aについてのループ。
  # bは、aについて解いておく。（b>0なので、一意にさだまる。）
  b=(1 + Math.sqrt(1+4*Base2*a -4*a*a)).round/2
  n = a*Base2 + b
  result << n if a*a + b*b == n # 条件を満たすかどうかをチェック。
}
p result
p result.reduce(&:+)