Chủ đề này có 3 trả lời

[NMD202]

Có bao nhiêu cách chọn từ 2018 số nguyên dương đầu tiên ra 1000 số nguyên đôi một khác nhau sao cho không có hai số nào là hai số nguyên liên tiếp?

[Vgdmctltccl4782]

bạn tìm hiểu bài toán xếp khách lucas đi

Bài viết đã được chỉnh sửa nội dung bởi Vgdmctltccl4782: 26-01-2018 - 19:40

[NMD202]

Vậy bài này thì mình gán bít 0 và 1 ntn ạ?

[YoLo]

Có bao nhiêu cách chọn từ 2018 số nguyên dương đầu tiên ra 1000 số nguyên đôi một khác nhau sao cho không có hai số nào là hai số nguyên liên tiếp?

ta sử dụng phương pháp song ánh

trước tiên ta gọi 1000 số đó

gs là a1 ,a2 ,a3,....,a1000

thay vì tìm số cách chọn ra thì ta sẽ đi tính số cách chèn 1018 số còn lại vào 999 khoảng (khoảng giữa 2 số gọi là 1 khoảng)

mỗi khoảng này sẽ chứa 1 hoặc nhiều hơn số nguyên dương

ngoài ra có thể chèn vào 2 vị trí trước a1 hoăc sau a1000 ( lượng số ở đây là số tự nhiên vì ko nhất thiết phải có

ta gọi 1001 khoảng này là b1, b2, b3, ..... , b1001 (với b1 , b1001 là số tự nhiên ,còn lại là số nguyên dương)

ta có b1 + b2 +b3+ .......+b1001 =1028

=> (b1 +1)+ b2+b3+b4+....+b1000+(b1001+1)=1030

như vậy pt trở thành pt với 1001 ẩn với nghiệm nguyên dương

=> AD bài toán chia kẹo Euler => có (1030-1)C(1001-1)= 1029C1000

Bài viết đã được chỉnh sửa nội dung bởi YoLo: 23-03-2018 - 22:00