mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-08-02, 11:16   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

1E1E16 Posts
Default August 2019

http://www.research.ibm.com/haifa/po...ugust2019.html
Xyzzy is offline   Reply With Quote
Old 2019-08-03, 19:55   #2
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5·11 Posts
Default

Hello everybody.

Understanding the question is always the first difficulty of challange.
B> C Restriction.
Are we talking about variable or alphabetic chain to sort?
Kebbaj is offline   Reply With Quote
Old 2019-08-04, 05:19   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

223716 Posts
Default

That kind of means "ordered pair", or "totally ordered set", i.e. all the permutations in which B is after C are not accepted. Or viceversa, WLOG. You can read the operator as "after" or "before", or "ascents" or "descents", "B is after (or before) C", etc, or even completely eliminate the operator. I learned (most of) my (related) math without it, and only occasionally seen it in combinatorics or so, I mean you can just write "ABCD" instead of "A<B<C<D", and it is still clear in the context of total ordered sets. The dilemma (my dilemma) of "after" versus "before" comes from the fact that many authors use one or the other, with the meaning defined locally in their own texts. I had two professors in the uni and one of them used to write "A<B<C" and the other "A>B>C" for the same thing, the ordered triplet (A, B, C), or ABC, which was an eternal resource of fun and confusion. If you think deeper, both notations make sense, haha...

Last fiddled with by LaurV on 2019-08-04 at 05:24
LaurV is offline   Reply With Quote
Old 2019-08-05, 12:44   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,861 Posts
Default

I am struggling to come up with a small example that requires 3 permutations never mind 4 or more (4 may be easier as 2*2=4). Is this puzzle solvable with pen and paper?
henryzz is offline   Reply With Quote
Old 2019-08-05, 17:25   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×13×73 Posts
Default

I read this puzzle again everyday and everyday I understand the challenge a bit more than the day before.
At the current rate I should completely understand it in a couple of months, Max.
a1call is offline   Reply With Quote
Old 2019-08-05, 18:11   #6
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

3716 Posts
Smile

Quote:
Originally Posted by a1call View Post
I read this puzzle again everyday and everyday I understand the challenge a bit more than the day before.
At the current rate I should completely understand it in a couple of months, Max.

In two months you will understand Rachid.
I'm joking Rachid.
I do not understand too !!
We're getting old.
Kebbaj is offline   Reply With Quote
Old 2019-08-06, 07:56   #7
Dieter
 
Oct 2017

1318 Posts
Default

Quote:
Originally Posted by Kebbaj View Post
In two months you will understand Rachid.
I'm joking Rachid.
I do not understand too !!
We're getting old.
Sometimes it‘s helpful to hear the same in other words:
There are 9! possibilities to write abcdefghi ... ihgfedcba. We can interprete the first permutation as a<b<c...<i. Here is c<g and in the last permutation is g<c.
Counting only the permutations fulfilling B>C, C>D, and E>G (b has to be right of c and so on) we have only 30,240 permutations.
There are 36 pairs ab ac ... ai bc bd...bi...hi. In our exemple we have given relations between b,c and c,d and b,d and e,g. The other 32 relations aren‘t fixed, f.e. a<b and a>b is possible.
The permutations A<D<C<B<F<G<E<H<I and I<H<G<E<F<D<C<B<A are two of the 30240 permutations fulfilling the fixed conditions. Furthermore they contain („cover“) all 2*32 undefined relations, f.e. a<b (the first) and a>b (the second).
We have to search for conditions (restrictions) for which it isn‘t possible to find three permutations covering the fixed and the undetermined pairs. They have to be free of contradictions (feasible). This sentence has been additioned (the challenge has been changed at least one time). I suppose that someone has sent a<b and b<c and c<a to the puzzlemaster.
Dieter is offline   Reply With Quote
Old 2019-08-06, 08:31   #8
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

5×11 Posts
Default

Quote:
Originally Posted by Dieter View Post
Sometimes it‘s helpful to hear the same in other words:
There are 9! possibilities to write abcdefghi ... ihgfedcba. We can interprete the first permutation as a<b<c...<i. Here is c<g and in the last permutation is g<c.
Counting only the permutations fulfilling B>C, C>D, and E>G (b has to be right of c and so on) we have only 30,240 permutations.
There are 36 pairs ab ac ... ai bc bd...bi...hi. In our exemple we have given relations between b,c and c,d and b,d and e,g. The other 32 relations aren‘t fixed, f.e. a<b and a>b is possible.
The permutations A<D<C<B<F<G<E<H<I and I<H<G<E<F<D<C<B<A are two of the 30240 permutations fulfilling the fixed conditions. Furthermore they contain („cover“) all 2*32 undefined relations, f.e. a<b (the first) and a>b (the second).
We have to search for conditions (restrictions) for which it isn‘t possible to find three permutations covering the fixed and the undetermined pairs. They have to be free of contradictions (feasible). This sentence has been additioned (the challenge has been changed at least one time). I suppose that someone has sent a<b and b<c and c<a to the puzzlemaster.

Your explanations are very clear.

Thank you dieter,

"The weight carried by a group is a feather".
Kebbaj is offline   Reply With Quote
Old 2019-08-06, 10:46   #9
Bolero
 
Aug 2019
Marseille

48 Posts
Default

I still quite don't get it as from what I understand it shouldn't be an easy problem. Maybe I'm missing something here as I can't see why the simple solution to enforce a specific permutation shouldn't work here. For example

the restrictions A<B, B<C, C<D, D<E, E<F, F<G, G<H, H<I are fulfilled by just one permutation A<B<C<D<E<F<G<H<I
Bolero is offline   Reply With Quote
Old 2019-08-06, 14:07   #10
Dieter
 
Oct 2017

89 Posts
Default

Quote:
Originally Posted by Bolero View Post
I still quite don't get it as from what I understand it shouldn't be an easy problem. Maybe I'm missing something here as I can't see why the simple solution to enforce a specific permutation shouldn't work here. For example

the restrictions A<B, B<C, C<D, D<E, E<F, F<G, G<H, H<I are fulfilled by just one permutation A<B<C<D<E<F<G<H<I
... and so it's no solution, because we are searching for restrictions for which the pairs can NOT be covered by one or two or three permutations.
Dieter is offline   Reply With Quote
Old 2019-08-06, 14:43   #11
Bolero
 
Aug 2019
Marseille

1002 Posts
Default

Quote:
Originally Posted by Dieter View Post
... and so it's no solution, because we are searching for restrictions for which the pairs can NOT be covered by one or two or three permutations.
ok, so "no three permutations" means "more than three permutations"? (sorry, I'm not a native speaker and the problem is very strangely worded for me)
Bolero is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
August 2018 Xyzzy Puzzles 5 2018-09-05 02:11
August 2017 Batalov Puzzles 15 2017-09-05 03:47
August 2015 R. Gerbicz Puzzles 7 2015-09-04 13:18
August 2014 Xyzzy Puzzles 2 2014-11-02 19:04
August Progress Wacky NFSNET Discussion 0 2007-08-09 02:32

All times are UTC. The time now is 16:16.

Wed Sep 30 16:16:23 UTC 2020 up 20 days, 13:27, 0 users, load averages: 1.70, 2.05, 1.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.