Page 1 of 1
(b) (10 points) We are trying to fill a 10-by-10 board such that each row contains exactly one of each from {1,...,10} a
Posted: Mon May 09, 2022 2:38 pm
by answerhappygod
- B 10 Points We Are Trying To Fill A 10 By 10 Board Such That Each Row Contains Exactly One Of Each From 1 10 A 1 (67.49 KiB) Viewed 19 times
(b) (10 points) We are trying to fill a 10-by-10 board such that each row contains exactly one of each from {1,...,10} and each column contains at most one of each from the same set (Think Sudoku without the 3-by-3 block restraint). If the top 5-rows are already filled obeying this rule, prove that we can fill the next row so that this board satisfies the condition. (Hint : use Hall marriage theorem, in particular the Lemma introduced in class. Pick the left and right vertex set so the perfect matching here gives the way to fill the 5-th row correctly.)