数学研发论坛

 找回密码
 欢迎注册
查看: 151|回复: 2

[原创] 矩形染色问题

[复制链接]
发表于 2020-5-31 06:21:01 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
有一个m*n的矩形,要求每行有l1个格子染过色,每列l2个格子染过色,何时有满足条件的方案,如果有,有多少方案?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-5-31 11:36:50 | 显示全部楼层
第一问很简单,第二问太复杂。
m*l1=n*l2,
设(m,n)=d, m=d*m0, n=d*n0,于是得出l1=n0*h,l2=m0*h, 其中1<=h<=d。容易得出这是充分必要条件
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-6-1 18:34:27 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-6-1 22:55 编辑

猜测他的问题中L1和L2应该是Li和Rj,即每行每列个数不是固定的。比如10*10的矩形(总共57个染色格子),第一行至第十行的染色个数为(9,5,6,5,8,4,3,7,4,6),第一列至第十列染色个数为(9,9,4,2,5,7,6,5,4,6),是否存在这种状态?如果存在,有多少种?类似八皇后问题,采用回溯法。
dd.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-7-3 06:20 , Processed in 0.063193 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表