Re: [其他] brilliant math puzzles

[Desperato (Farewell)]

※ 引述《artie0906 (Donut's Dad)》之銘言：
: 此題是去年9月份brilliant網站的其中一題
: ，覺得滿有趣的，但找不到一個可一般化的方式，想請教大家，這要往那個方向想，謝謝
: https://i.imgur.com/BFvzKz8.jpg


我自己想的 不知道答案對不對


首先有個方法可以算出點數上限

簡單看成有8列 每一列有8個點
組成長方形的條件是「其中兩列有同行的兩點」
換句話說，只要每列任選兩點都不會同行的兩點，就不會有長方形

          8
也就是問 sum C(x_i, 2) <= C(8, 2) = 28 的前提下
         i=1
     8
max sum x_i 就會是點數上限
    i=1

當然 實際上還會有排列的問題 但至少有個上限在那邊了

湊了一下之後這看起來是最多的
4 3 3 3 3 3 3 3  線27 點25

因此最多應該就是25個點了 現在就來試試吧

1 2 3 4 5 6 7 8
V V V V
V       V V
V           V V
  V     V   V
  V       V   V
    V   V     V
    V     V V
      V V

結果這個情況辦不到 只有24個點

所以我認為答案是24 \ow o/


(Lem) 如果最多點的一列有 4 個點，其他列都 3 點以下
      那最多只能有 6 列是 3 點
 (pf) 假設該列有 1, 2, 3, 4
      則其他列只能在 1, 2, 3, 4 中最多選一個
      因此有 3 點的列 必須在 5, 6, 7, 8 中選兩個
      可是 5, 6, 7, 8 只提供了 6 組不同的兩點組合

其他情況還蠻容易做的 我就懶得列了 答案應該是 24 無誤


--

嗯嗯ow o

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.182.197
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1519628805.A.38B.html
→ Desperato   : 對了 這實際上是圖論的題目
→ Desperato   : 8個點之間 拆成8個clique 計算總和最大值
※ 編輯: Desperato (101.12.182.197), 02/26/2018 15:17:56
推 artie0906   : 謝謝…24應該沒錯，但有辦法推到NxN個點嗎？
→ Desperato   : 用類似的推法 會有個上限 4(N-1)
→ Desperato   : 但改進就有困難了 可能需要其他方法